Асимптотика одно операции ++ итератора set C++

перерыл весь интернет, ответа не нашёл. Вопрос: За какой время работает ++ итератора сета в С++? (пример:

set <int> st;
st.insert(1);
st.insert(2);
set <int>::iterator it=st.begin();
it++;

)

Я понимаю, что проход по set будет работать за линейное время (т. к. по каждому из n-1 рёбер мы пройдём один раз - суммарное кол-во переходов будет O(n)), но какое максимальное время одной операции? Мне кажется O(log(n)), т. к. иногда нам нужно подняться вверх по дереву, чтобы найти следующее число. Подскажите, пожалуйста, ++ итератора работает за O(1) или за O(log(n))?

P. S. Я не знаю точно как работает set, так что, пожалуйста, не кидайтесь гнилыми помидорами сразу?.

Заранее спасибо.