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

Может я что-то упускаю, но почему std::map::lower_bound вам не нравится?

Вы можете уточнить свой пример std::find(v.begin(), v.end()), чтобы не звонить begin и end, а что-то вроде std::find(subrange_first, subrange_last);. Вы хотите что-то в O(log(distance(subrange_first, subrange_last))) не O(log(size(map))) и не O(distance(subrange_first, subrange_last))

@Калет Я согласен; это сбивало с толку. Я отредактировал его сейчас, пытаясь сделать его более ясным.

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

@MaxLanghof Нет, ты ошибаешься. std::find даст вам элемент, если он есть на карте, в то время как lower_bound даст вам элемент только в том случае, если он не меньше, чем указанный в lower_bound. Вы должны пересмотреть свой отрицательный голос. Так что это точно так же, как std::find с границей.

Ни то, ни другое не входит в вопрос. Опять же, речь идет об ограничении диапазона поиска, а не о том, как найти элемент на всей карте.

Диапазон поиска @MaxLanghof и фильтрация результатов сортировки не могут быть различимы для стороннего наблюдателя. Наблюдаемое поведение такое же, метод поиска — деталь реализации.

Сложность разная. Если у меня есть 2^N элементов на карте, то поиск всех из них занимает O(N). Если я знаю, что мой элемент находится в диапазоне [first, last) с std::distance(first, last) == N, то поиск должен быть выполним в O(log(N)). Как объясняется в ответе Славы, std::lower_bound (и друзья) позволяет вам делать это в O(log(N)) сравнениях, но O(N) увеличивается итератор.

@MaxLanghof Я совершенно не понимаю тебя. Поиск карты - O (log N).

То же самое и с поиском в отсортированном диапазоне (из которого состоит std::map). Дело в том, что N карты и N диапазона для поиска могут (сильно) отличаться. Пожалуйста, взгляните на мой пример еще раз, где первое — 2^N, а второе — N.

@MaxLanghof это все еще намного лучше, чем ответ с наибольшим количеством голосов со сложностью O (N), поэтому с точки зрения производительности это лучшее, на что может надеяться ОП, и с точки зрения поведения это именно то, что им нужно. Я стою за своим ответом.

Позвольте мне перефразировать. У меня есть карта с 1e20 элементами. Но я знаю, что элемент, который я ищу, находится в первых трех. Как я могу указать карте искать мой элемент в этом крошечном диапазоне без (двоичного) поиска по всем 1e20? Ваш ответ — O(log(elements_in_map)) (сравнения), тогда как принятый ответ — O(length_of_range) (приращения итератора). Нетрудно заметить, что есть случаи, когда length_of_range <= log(elements_in_map) (оба моих примера подробно описывают такие случаи). Не говоря уже о том, что приращения и сравнения итераторов могут иметь очень разные реальные затраты.

@MaxLanghof, если у вас есть элементы 2 ^ Н на карте, то поиск среди них всех (т. Е. std::map::lower_bound) занимает НА), правильно. Однако, если вы ограничите поиск только элементами Н из этих 2 ^ Н, std::lower_bound/std::upper_bound сможет нет сделать это в журнал (N), потому что итераторы std::map — это нетитераторы произвольного доступа.

@ElProfesor Я никогда не говорил обратного? Я четко указал O(log(N)) сравнения и O(N) итератор увеличивает при использовании std::lower_bound и т. д., при этом теоретический оптимум равно O(log(N)) для обоих. Я не совсем уверен в этом теоретическом оптимуме, но я никогда не говорил, что std::lower_bound было O(log(N)) вообще.

@MaxLanghof Ну, на первый взгляд не так ясно: тогда поиск должен быть выполним в O(log(N)), но вы правы, поскольку объяснили это сразу после этого предложения. Прости.