Есть где-нибудь таблица или информация об этом?
Не могу что-то найти, нужно точно знать, будет ли сложность N, log N, C и т.д. для цикла прохода:
for(auto IT = cont.begin(); IT != cont.end(); IT++){}
List
Deque
Vector
set
multiset
map
multimap
stack
queue
priority_queue
slist
Вот примерно как тут: https://www.unetti.com/blog/wp-content/uploads/2013/03/Screen-Shot-2013-03-21-at-11.31.09-AM.png
Быстрее, чем за O(N) никак не получится. Никак. В любом случае нужно перебирать все элементы. Поэтому конечная сложность будет O(N) * (сложность инкремента итератора).
Обсудим сложность инкремента итератора.
stack, queue, priority_queue - для этих контейнеров нет смысла обсуждать сложность - у них нет нужного итератора.
vector - тут все просто. так как вектор храниться единым массивом, то процедура инкремента итератора - это просто приплюсовать число.
list - обычно реализовывается как цепочка с блоков, которые указывают на следующий. Поэтому в прямом направлении проход быстрый (это просто взятие указателя, чуточку медленнее, чем приплюсовать число, так как нужно читать с памяти). Сложность инкремента итератора - константная.
deque - может быть реализовано на базе vector или list. Соответственно, на это и нужно ориентироваться.
slist - в стандартной библиотеке такого класса нет. Но обычно он реализуется либо на базе вектора, либо списка. Поэтому, скорее всего сложность инкремента итератора будет константной.
set, multiset, map, multimap - с этими типами нужно копать глубже в конкретную реализацию конкретного компилятора. Тут я написал простенький код, который просто считал время итерирования и делил на общее кол-во элементов. (я тестил на gcc version 4.9.2 20141101 (Red Hat 4.9.2-1) (GCC), fedora 21). У меня получилось, что время инкрементирования итератора приблизительно константно.
Итого, для stack, queue, priority_queue указанный в вопросе цикл не работает (у них нет подходящих итераторов), для slist нужно смотреть в конкретную реализацию. Для всех остальных сложность, как не удивительно O(N).
