Скорость цикла begin() end() STL контейнеров

Быстрее, чем за 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).