C++ выполняет begin / end / rbegin / rend в постоянное время для std :: set, std :: map и т. д.?
Для таких типов данных, как std :: set и std :: map, где поиск выполняется за логарифмическое время, требуется ли реализация для поддержки начального и конечного итераторов? Подразумевает ли доступ begin и end поиск, который может происходить за логарифмическое время?
Я всегда предполагал, что начало и конец всегда происходят в постоянное время, однако я не могу найти этому подтверждения в Йосуттисе. Теперь, когда я работаю над чем-то, в чем мне нужно серьезно относиться к производительности, я хочу убедиться, что охватил свои основы.
Спасибо
Ответы 6
Да, согласно http://www.cplusplus.com/reference/stl/, begin (), end () и т. д. - все O (1).
В стандарте C++ таблица 65 в 23.1 (Требования к контейнерам) перечисляет begin () и end () как требующие постоянного времени. Если ваша реализация нарушает это, значит, она не соответствует.
Для std :: set
начало: константа, конец: константа, rbegin: константа, rend: постоянный,
Для std :: map
они также постоянны (все они)
если есть сомнения, просто проверьте www.cplusplus.com
Они происходят в постоянное время. Я смотрю страницу 466 стандарта ISO / IEC 14882: 2003:
Таблица 65 - Требования к контейнерам
a.begin (); (постоянная сложность)
a.end (); (постоянная сложность)
Таблица 66 - Требования к двусторонним контейнерам
a.rbegin (); (постоянная сложность)
a.rend (); (постоянная сложность)
Однако будьте осторожны с hash_map. begin () не является постоянным.
Не полагайтесь слишком на cplusplus.com