выполнить бинарный поиск на карте элементов

Question

У меня есть map<double, unique_ptr<Item>>. Я хотел бы найти эту карту, чтобы найти элемент, где вычисленное значение ближе всего к значению поиска. Вычисленное значение может быть сгенерировано Item::compute, которое является вычислением длины, которое я бы хотел избежать для всех элементов. Можно предположить, что эта карта уже упорядочена по результатам вычислительной функции.

Так что я думал, что могу сделать двоичный поиск, но проблема в том, что я не могу прыгнуть к n-му элементу на карте, так как это карта, а не вектор. В частности, мне нужно будет получить средний элемент между двумя произвольными элементами на карте. Это возможно? Есть ли способ эффективный способ выполнения бинарного поиска на карте?

Answer 1

Используйте либо lower_bound(), либо методы upper_bound()std::map. См. Документацию std::map для обоих этих методов, которые найдут существующий ключ, ближайший к ключу поиска, если он не существует. Вам не нужно кодировать бинарный поиск самостоятельно, эти методы делают это за вас.

Хотя использование double как карта ключ is problematic, of course, я думаю, что с помощью lower_bound() или upper_bound() может производить разумные результаты, в данном прецеденте.