В C ++ начало / конец / rbegin / rend выполняется в постоянное время для std :: set, std :: map и т. Д.?

Question

Для типов данных, таких как std :: set и std :: map, где поиск происходит в логарифмическом времени, требуется ли реализация для поддержки начального и конечного итераторов? Предполагает ли доступ начало и конец поиска, который может произойти в логарифмическом времени?

Я всегда предполагал, что начало и конец всегда происходят в постоянное время, однако я не могу найти никакого подтверждения этому в Йосуттисе. Теперь, когда я работаю над чем-то, что мне нужно для анализа производительности, я хочу быть уверенным в том, что я расскажу о своих базах.

Спасибо

Answer 1

Они происходят в постоянное время. Я смотрю на страницу 466 стандарта ИСО / МЭК 14882: 2003:

Таблица 65 - Требования к контейнерам

a.begin (); (постоянная сложность)

a.end (); (постоянная сложность)

Таблица 66 - Требования к обратимым контейнерам

a.rbegin (); (постоянная сложность)

* * 1 022 a.rend (); (постоянная сложность)

Answer 2

Да, согласно http://www.cplusplus.com/reference/stl/, begin (), end () и т. Д. - все O (1).

Answer 3

В стандарте C ++ таблицы 65 в 23.1 (Требования к контейнерам) списки begin () и end () требуют постоянного времени. Если ваша реализация нарушает это, это не соответствует.

Answer 4

Просто посмотрите на код, здесь вы можете увидеть итераторы в std :: map в GNU libstdc ++

std::map

вы увидите, что все end rend cend ... все реализованы в постоянном времени.

Answer 5

Будьте осторожны с hash_map. begin () не является константой.

Answer 6

Для стандартного набора: набор

начало: константа, конец: константа, рбегин: постоянный, Ренд: постоянный,

Для стандартного отображения :: карта

они также постоянны (все они)

если у вас есть какие-либо сомнения, просто проверьте www.cplusplus.com