Directrices para una clase Iterator

Question

Tengo un árbol rojo implementado en C++. Es compatible con la funcionalidad de un mapa STL. Los nodos de árbol contienen claves y los valores asignados. Quiero escribir una clase de iterador para esto, pero estoy atascado con cómo hacerlo. ¿Debería convertirlo en clase interna de la clase Tree? ¿Alguien puede darme algunas pautas sobre cómo escribir + algunos recursos?

¡Gracias!

Answer 1

Claro, lea este buen artículo sobre la escritura de iteradores STL, lo que podría dar la visión general necesaria:

http://www.drdobbs.com/184401417

En general, sí, una clase interna es buena, ya que el iterador necesita acceder a su implementación de los nodos del árbol específicos:

struct container { ... 
public: 
    struct iterator { 
    // these typedefs are needed if you want to be STL compatible 
    typedef std::forward_iterator_tag iterator_category; 
    typedef T   value_type; 
    typedef T*  pointer; 
    typedef T&  reference; 
    typedef size_t size_type; 
    typedef ptrdiff_t difference_type; 

    // the element points to your implementation node 
    iterator(element* init = 0) : current(init) {} 
    T& operator*() { return current->data; } // dereference 
    const T& operator*() const { return current->data; } 
    iterator& operator++() { // prefix 
     if (current) current = current->next; 
     return *this; 
    } 
    iterator operator++(int) { // postfix 
     iterator temp = *this; 
     ++*this; 
     return temp; 
    } 
    bool operator==(const iterator& x) const { return current == x.current; } 
    bool operator!=(const iterator& x) const { return current != x.current; } 

    private: 
    // the element points to your implementation node 
    element* current; 
    } 
    ... 

lo bueno aquí es que mientras que el iterador es público, el elemento todavía puede permanecer :) privado. ¡Y sí, el código anterior también es compilador de STL!

Answer 2

La clase de iterador debe ser una clase anidada, o al menos un typedef que alias your_map::iterator a algún tipo que esté definido en otro lugar. Sin embargo, una clase anidada suele ser la más limpia/más fácil.

En lo que respecta a los recursos, una posible fuente de ayuda sería la biblioteca Boost::iterator, que incluye componentes destinados a facilitar la implementación de los iteradores.

Answer 3

Pensé en agregar mi propio montón de consejos.

Lo primero que me gustaría señalar es que es muy probable que iterator y const_iterator tengan mucha implementación en común. Sin embargo, a pesar de que su código es similar, no es exactamente idéntico. Esto pide plantillas.

Lo segundo que me gustaría señalar es que un const_iterator debería ser construible desde un iterator (implícitamente), pero no al revés.

La tercera cosa que me gustaría señalar es que si desea tener una interfaz de tipo map, debe proporcionar un reverse_iterator y const_reverse_iterator también.

Desde un punto de vista de estilo, tiendo a no poner la implementación del iterator directamente en la clase. Encuentro que no se puede leer cuando la implementación de la clase está llena de tanto código que le cuesta ver los tipos y métodos disponibles. Por esta razón, recomendaría poner la implementación fuera de la clase.

Finalmente, definitivamente recomiendo Boost.Iterator. No puede usarlo, pero lea el material, ¡le dará información sobre cómo escribir el código una vez y lo usará para los 4 tipos!

ilustración rápida:

namespace detail { 
    template <class Value> class base_iterator; 
} 

template <class Value> 
class container 
{ 
public: 
    typedef detail::base_iterator<Value> iterator; 
    typedef detail::base_iterator<Value const> const_iterator; 

    typedef boost::reverse_iterator<iterator> reverse_iterator; 
    typedef boost::reverse_iterator<const_iterator> const_reverse_iterator; 
}; 

no sé ustedes, pero me siento bien cuando lo haga sólo una cuarta parte de la obra y aprovecha un compilador/biblioteca para rellenar el resto para mí :)