Pautas para una clase de iterador

Question

Tengo un rojo Árbol negro implementado en C ++. Admite la funcionalidad de un mapa STL. Los nodos de los árboles contienen claves y los valores mapeados. Quiero escribir un clase de iterador Para esto, pero estoy atrapado con cómo hacerlo. ¿Debo hacerlo un clase interior de la clase de árbol? ¿Alguien puede darme algunas pautas sobre cómo escribirlo + algunos recursos?

¡¡Gracias!!

Answer 1

Claro, lea este bonito artículo sobre la escritura de iteradores STL, podría darle la descripción general necesaria:

http://www.drdobbs.com/184401417

En general, sí, una clase interna es buena, porque el iterador necesita acceso a su implementación de nodos de árboles 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, si bien el iterador es público, el elemento aún puede permanecer privado :). Y sí, ¡el código anterior también es compilante STL!

Answer 2

Pensé que agregaría mi propio lote de consejos.

Lo primero que me gustaría tener en cuenta es que iterator y const_iterator Es muy probable que tenga gran parte de su implementación en común. Sin embargo, a pesar de que su código es similar, no es exactamente idéntico. Esto pide plantillas.

La segunda cosa que me gustaría tener en cuenta es que un const_iterator debe ser construible a partir de un iterator (implícitamente), pero no al revés.

La tercera cosa que me gustaría tener en cuenta es que si desea tener un map-meco interfaz, luego necesitas 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 en sí mismo en la clase. Me parece ilegible cuando la implementación de la clase está abarrotada con tanto código que tiene dificultades para 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. Es posible que no lo use, pero lea el material, ¡notablemente le dará una idea de cómo escribir el código una vez y usarlo 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é sobre ti, pero me siento bien cuando solo hago una cuarta parte del trabajo y aprovecha un compilador/biblioteca para completar el resto para mí :)

Answer 3

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

En cuanto a los recursos, una posible fuente de ayuda sería la Impulso :: iterador Biblioteca, que incluye componentes destinados a hacer que los iteradores sean más fáciles de implementar.