Есть ли стандартная реализация для таблицы поиска?

Question

Я хочу получить свойство материала из таблицы поиска с линейной интерполяцией. Есть ли стандартная реализация, которая делает что-то подобное?

Иначе я бы реализовал это самостоятельно, используя два вектора x и y. Найти правильную позицию в x с помощью lower_bound, а затем интерполировать с помощью x. Могу ли я сделать лучше?

Answer 1

Вы можете использовать упорядоченный std:: map. Так для данного числа n, получить запись карты под ней (с lower_bound) и запись карты над ней (с upper_bound, или просто увеличивая итератор, заданный lower_bound), затем интерполируйте.

Вы также можете использовать простой вектор или массив пар, которые вы бы отсортировали по их ключам, а затем кодировать дихотомический доступ (бинарный поиск). Это, вероятно, быстрее, чем std::map (например, из-за локальности кэша).