Сложность времени std :: multimap :: equal_range

Question

Добрый день, мне интересно, какова временная сложность std::multimap::equal_range?Это Big-O (n) или BIG-0 (log n).Я помню, как читал, что временная сложность std::multimap::erase «является логарифмическим плюс линейное время для длины удаляемой последовательности».<<a href="http://frank.mtsu.edu/~csjudy/STL/Multimap.html" rel="nofollow">http://frank.mtsu.edu/~csjudy/STL/Multimap.html>

Answer 1

Стандарт

C ++ 03, таблица 69 («Требования к ассоциативным контейнерам») в 23.1.2 гласит, что equal_range имеет логарифмическую сложность.

Answer 2

equal_range - это операция O (log n), возвращающая пару lower_bound и upper_bound.

Это означает, что он вернет диапазон итератора, начиная с первого ключа, который больше чемили равно ключу поиска и заканчивается первым ключом, который больше ключа поиска.

Answer 3

Я никогда не находил лучшего источника для такой информации, чем Руководство программиста SGI STL .В этом случае интересующая вас страница представляет собой концептуальную страницу Sorted Associate Container , в которой в разделе «Гарантии сложности» указано:

Нижняя граница, верхняя граница и равный диапазонлогарифмическая.[1]

...

[1] Это гораздо более сильная гарантия, чем та, которую предоставляет Ассоциативный Контейнер.Гарантии в Ассоциативном контейнере относятся только к средней сложности;В худшем случае сложность может быть больше.Однако отсортированный ассоциативный контейнер обеспечивает верхний предел сложности наихудшего случая.