С++ выполняет начало/конец/rbegin/rend в постоянное время для std::set, std::map и т.д.?
https://stackoverflow.com/questions/83640
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Для таких типов данных, как std::set и std::map, где поиск происходит в логарифмическом времени, требуется ли реализация для поддержки начального и конечного итераторов?Означает ли доступ к началу и концу поиск, который может происходить за логарифмическое время?
Я всегда предполагал, что начало и конец всегда происходят в постоянном времени, однако не могу найти этому подтверждения у Джосуттиса.Теперь, когда я работаю над чем-то, где мне нужно внимательно следить за производительностью, я хочу обязательно покрыть свои основы.
Спасибо
Решение
Они происходят в постоянное время.Я смотрю на страницу 466 стандарта ISO/IEC 14882:2003:
Таблица 65 – Требования к контейнерам
а.начать(); (постоянная сложность)
а.конец(); (постоянная сложность)
Таблица 66. Требования к двустороннему контейнеру
а.rbegin(); (постоянная сложность)
а.ренд(); (постоянная сложность)
Другие советы
Да, согласно http://www.cplusplus.com/reference/stl/, Begin(), End() и т.д. - все O(1).
В стандарте C++ таблица 65 в разделе 23.1 (Требования к контейнеру) указывает, что методы Begin() и End() требуют постоянного времени.Если ваша реализация нарушает это, она не соответствует.
Просто посмотрите на код, здесь вы можете увидеть итераторы в std::map в GNU libstdc++.
ты увидишь, что все кончится ренд сенд...все они реализуются в постоянное время.
Однако будьте осторожны с hash_map.Begin() не является константой.
Для станд::set
начинать:константа, конец:постоянная, rbegin:Постоянный, Ренд:постоянный,
Для std::map
они также постоянны (все они)
если у тебя есть сомнения, просто проверь www.cplusplus.com
