Асимптотика итератора set

[БалаШагаЛ]

Собственно, вопрос: с какой асимптотикой работает ++I, где set<int>::iterator I;.
Я так понимаю, что в худшем случае нужно подняться на с самого нижнего уровня до верхнего - это даёт O(log(N)). Но при общем переборе всех вершин (именно это и требуется) от каждой вершины подъём будет ровно один раз и вход (снизу и сверху) не более трёх раз, что даёт в сумме O(N) (то есть O(1) на каждую вершину).
Но не знаю, применена ли там какая-то оптимизация для итератора (может, список указателей упорядоченный).
Верны ли мои предположения?