Как найти элемент в указанном диапазоне в std :: map?

Question

Есть ли эквивалентная версия std::find(first, last), но для std::map?Т.е. существует ли версия метода std::map find, который ищет элемент в map, но ограничивает поиск только указанным диапазоном [first, last)?В идеале решение должно быть логарифмическим в размере [first, last).

Из того, что я видел , std::map::find само по себе не поддерживает эту функцию (оно всегда ищет веськарта).

Answer 1

Если я правильно понял вопрос, std::map::lower_bound - это именно то, что вы ищете - он дает вам элемент, который не меньше, чем ключ.И есть upper_bound для другого конца.

Answer 2

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

Из std::lower_bound документации

Количество выполненных сравнений является логарифмическим по расстоянию между первым и последним (не болееlog 2 (последний - первый) + O (1) сравнений).Однако, для не-LegacyRandomAccessIterators, число приращений итераторов является линейным .

Акцент мой.