La clase std :: map C++ STL implementa la búsqueda O (log (n)) usando un árbol binario. Pero con los árboles, no es inmediatamente obvio cómo funcionaría un iterador. ¿Qué significa realmente el operador ++ en una estructura de árbol? Mientras que el concepto de "próximo elemento" tiene una implementación obvia en una matriz, para mí no es tan obvio en un árbol. ¿Cómo se implementaría un iterador de árbol?¿Cómo funciona el iterador std :: map?
Para un recorrido en el interior (probablemente también funciona para otros), si tiene un puntero principal en los nodos, puede hacer un recorrido no recursivo. Debería ser posible almacenar dos punteros en su iterador: necesita una indicación de dónde se encuentra, y probablemente (no estoy investigando ahora) necesita algo así como un puntero "anterior" para que pueda averiguar su dirección de movimiento actual (es decir, ¿necesito ir al subárbol izquierdo, o acabo de regresar de él).
"anterior" se probablemente ser algo así como "padre", si hemos acaba de entrar en el nodo; "left" si volvemos del subárbol izquierdo, "right" si regresamos del subárbol derecho, y "self" si el último nodo que devolvimos es el nuestro.
Una implementación puede saber que los punteros de nodo están alineados con palabras y abusan de los bits inferiores del puntero de nodo para almacenar el estado, en lugar de usar un segundo puntero. – MSalters
Creo que esto es lo que necesitaba. Básicamente, estoy tratando de crear un iterador para una clase de árbol genérica y esto parece funcionar para árboles no ordenados n-arios. – Avi
Considere el conjunto de todos los elementos en el mapa que no son menores que el elemento actual que tampoco son el elemento actual. El "siguiente elemento" es el elemento de ese conjunto de elementos que es menor que todos los demás elementos en ese conjunto.
Para utilizar un mapa, debe tener una clave. Y esa clave debe implementar una operación "menor que". Esto determina la forma en que se forma el mapa, de modo que las operaciones de buscar, agregar, eliminar, incrementar y disminuir sean eficientes.
En general, el mapa utiliza internamente un árbol de algún tipo.
Puede echar un vistazo a la fuente como punto de partida: http://www.sgi.com/tech/stl/stl_map.h – amit
Observe un árbol de búsqueda binaria autoequilibrante típico (http: // en.wikipedia.org/wiki/Red%E2%80%93black_tree). Es fácil ver un algoritmo que pasa de un nodo determinado al siguiente más grande mirando a los niños correctos o yendo arriba y abajo del árbol. Ocasionalmente tiene que saltar varias veces, pero todavía se amortiza a tiempo constante (ya que la altura del árbol es el logaritmo de la cantidad de elementos). –
Este artículo de la wikipedia puede responder algunas de sus preguntas: [Tree traversal] (http://en.wikipedia.org/wiki/Tree_traversal). Básicamente, el elemento "siguiente" puede ser diferente según el tipo de recorrido que utilice. En el caso de 'std :: map', el árbol se recorre en orden (del elemento más pequeño al más grande). –