¿Cuál es la complejidad de la operación iterator ++ para stl RB-Tree (set o map)? Siempre pensé que usarían índices, por lo tanto, la respuesta debería ser O (1), pero recientemente leí la implementación de vc10 y descubrí que no lo hacían. Para encontrar el siguiente elemento en un árbol RB ordenado, llevaría tiempo buscar el elemento más pequeño en el subárbol derecho, o si el nodo es un elemento secundario izquierdo y no tiene elemento secundario derecho, el elemento más pequeño en el hermano derecho. Esto introduce un proceso recursivo y creo que el operador ++ toma tiempo O (lgn). Estoy en lo cierto? ¿Y es este el caso para todas las implementaciones stl o solo C ++ visual?

¿Es realmente difícil mantener índices para un árbol RB? Por lo que veo, manteniendo dos punteros adicionales en la estructura de nodos podemos mantener una lista doblemente vinculada siempre que el árbol RB. ¿Por qué no hacen eso?