К вопросу о C++, как operator++ работает в std::map? Ведь обход двоичного (красно-черного)
дерева требует стека и рекурсии в общем случае. А если в итераторе только ссылка на один текущий узел,
то поиск следующего по порядку превращается в нетривиальную задачу для "листьев" дерева: нужно подняться
наверх до узла имеющего "правого" наследника и спуститься вниз. Не быстро.
Вот тут какой-то треш с циклами:
https://stackoverflow.com/questions/17150544/what-is-the-definition-of-rb-tree-increment-in-bits-stl-tree-h/17150988#17150988
Для решения подобной проблемы известны прошитые деревья, но почему STL их не использует?
Для различения указателей и прошивки можно использовать раскрашенные указатели, благо у узла выравнивания явно чётное.