¿Cómo implementar correctamente iteradores personalizados y const_iterators?

240

Tengo una clase de contenedor personalizada para la que me gustaría escribir iteratoryconst_iterator clases .

Nunca hice esto antes y no pude encontrar un procedimiento apropiado. ¿Cuáles son las pautas con respecto a la creación de iteradores y qué debo tener en cuenta?

También me gustaría evitar la duplicación de código (siento que const_iteratoryiterator comparto muchas cosas; ¿debería una subclase a la otra?).

Nota al pie: estoy bastante seguro de que Boost tiene algo para aliviar esto, pero no puedo usarlo aquí, por muchas razones estúpidas.

ereOn
fuente
¿Se está considerando el patrón de iterador GoF?
DumbCoder
3
@DumbCoder: en C ++ a menudo es deseable tener iteradores que sean compatibles con STL, porque funcionarán bien con todos los contenedores y algoritmos existentes proporcionados por STL. Aunque el concepto es similar, existen algunas diferencias con el patrón propuesto por el GoF.
Björn Pollex
He publicado una muestra de iterador personalizado aquí
Valdemar_Rudolfovich
1
La complejidad de estas respuestas sugiere que C ++ es un lenguaje indigno de cualquier otra cosa que no sean tareas para estudiantes de pregrado salteados, o las respuestas son demasiado complicadas y erróneas. Debe haber una manera más fácil en Cpp? Al igual que CMake y Automake antes de su creación, el C sin procesar hervido de un prototipo de Python parece mucho más fácil que esto.
Christopher

Respuestas:

157
  • Elija el tipo de iterador que se ajuste a su contenedor: entrada, salida, reenvío, etc.
  • Utilice las clases de iterador base de la biblioteca estándar. Por ejemplo, std::iteratorconrandom_access_iterator_tag . Estas clases base definen todas las definiciones de tipo requeridas por STL y hacen otro trabajo.
  • Para evitar la duplicación de código, la clase de iterador debe ser una clase de plantilla y debe estar parametrizada por "tipo de valor", "tipo de puntero", "tipo de referencia" o todos ellos (depende de la implementación). Por ejemplo:

    // iterator class is parametrized by pointer type
    template <typename PointerType> class MyIterator {
        // iterator class definition goes here
    };
    
    typedef MyIterator<int*> iterator_type;
    typedef MyIterator<const int*> const_iterator_type;

    Aviso iterator_typey const_iterator_typedefiniciones de tipo: son tipos para sus iteradores no constantes y constantes.

Ver también: referencia de biblioteca estándar

EDITAR: std::iterator está en desuso desde C ++ 17. Vea una discusión relacionada aquí .

Andrey
fuente
8
@Potatoswatter: No he votado a favor de esto, pero, oye, random_access_iteratorno está en el estándar y la respuesta no maneja la conversión de mutable a constante. Probablemente quieras heredar de, por ejemplo std::iterator<random_access_iterator_tag, value_type, ... optional arguments ...>.
Yakov Galka
2
Sí, no estoy muy seguro de cómo funciona esto. Si tengo el método RefType operator*() { ... }, estoy un paso más cerca, pero no ayuda, porque todavía lo necesito RefType operator*() const { ... }.
Autumnsault
31
std::iteratorse propone desaprobar en C ++ 17 .
TypeIA
20
std::iterator ha quedado en desuso
diapir
55
Si esto está en desuso, ¿cuál es la forma "nueva" adecuada de hacerlo?
SasQ
56

Voy a mostrarle cómo puede definir fácilmente iteradores para sus contenedores personalizados, pero en caso de que haya creado una biblioteca de c ++ 11 que le permita crear fácilmente iteradores personalizados con comportamiento personalizado para cualquier tipo de contenedor, contiguo o no contiguo

Puedes encontrarlo en Github

Estos son los pasos simples para crear y usar iteradores personalizados:

  1. Crea tu clase de "iterador personalizado".
  2. Defina typedefs en su clase de "contenedor personalizado".
    • p.ej typedef blRawIterator< Type > iterator;
    • p.ej typedef blRawIterator< const Type > const_iterator;
  3. Definir las funciones "comenzar" y "finalizar"
    • p.ej iterator begin(){return iterator(&m_data[0]);};
    • p.ej const_iterator cbegin()const{return const_iterator(&m_data[0]);};
  4. Ya hemos terminado!

Finalmente, al definir nuestras clases de iterador personalizadas:

NOTA: Al definir iteradores personalizados, derivamos de las categorías de iteradores estándar para que los algoritmos STL conozcan el tipo de iterador que hemos creado.

En este ejemplo, defino un iterador de acceso aleatorio y un iterador de acceso aleatorio inverso:

  1. //-------------------------------------------------------------------
    // Raw iterator with random access
    //-------------------------------------------------------------------
    template<typename blDataType>
    class blRawIterator
    {
    public:
    
        using iterator_category = std::random_access_iterator_tag;
        using value_type = blDataType;
        using difference_type = std::ptrdiff_t;
        using pointer = blDataType*;
        using reference = blDataType&;
    
    public:
    
        blRawIterator(blDataType* ptr = nullptr){m_ptr = ptr;}
        blRawIterator(const blRawIterator<blDataType>& rawIterator) = default;
        ~blRawIterator(){}
    
        blRawIterator<blDataType>&                  operator=(const blRawIterator<blDataType>& rawIterator) = default;
        blRawIterator<blDataType>&                  operator=(blDataType* ptr){m_ptr = ptr;return (*this);}
    
        operator                                    bool()const
        {
            if(m_ptr)
                return true;
            else
                return false;
        }
    
        bool                                        operator==(const blRawIterator<blDataType>& rawIterator)const{return (m_ptr == rawIterator.getConstPtr());}
        bool                                        operator!=(const blRawIterator<blDataType>& rawIterator)const{return (m_ptr != rawIterator.getConstPtr());}
    
        blRawIterator<blDataType>&                  operator+=(const difference_type& movement){m_ptr += movement;return (*this);}
        blRawIterator<blDataType>&                  operator-=(const difference_type& movement){m_ptr -= movement;return (*this);}
        blRawIterator<blDataType>&                  operator++(){++m_ptr;return (*this);}
        blRawIterator<blDataType>&                  operator--(){--m_ptr;return (*this);}
        blRawIterator<blDataType>                   operator++(int){auto temp(*this);++m_ptr;return temp;}
        blRawIterator<blDataType>                   operator--(int){auto temp(*this);--m_ptr;return temp;}
        blRawIterator<blDataType>                   operator+(const difference_type& movement){auto oldPtr = m_ptr;m_ptr+=movement;auto temp(*this);m_ptr = oldPtr;return temp;}
        blRawIterator<blDataType>                   operator-(const difference_type& movement){auto oldPtr = m_ptr;m_ptr-=movement;auto temp(*this);m_ptr = oldPtr;return temp;}
    
        difference_type                             operator-(const blRawIterator<blDataType>& rawIterator){return std::distance(rawIterator.getPtr(),this->getPtr());}
    
        blDataType&                                 operator*(){return *m_ptr;}
        const blDataType&                           operator*()const{return *m_ptr;}
        blDataType*                                 operator->(){return m_ptr;}
    
        blDataType*                                 getPtr()const{return m_ptr;}
        const blDataType*                           getConstPtr()const{return m_ptr;}
    
    protected:
    
        blDataType*                                 m_ptr;
    };
    //-------------------------------------------------------------------
  2. //-------------------------------------------------------------------
    // Raw reverse iterator with random access
    //-------------------------------------------------------------------
    template<typename blDataType>
    class blRawReverseIterator : public blRawIterator<blDataType>
    {
    public:
    
        blRawReverseIterator(blDataType* ptr = nullptr):blRawIterator<blDataType>(ptr){}
        blRawReverseIterator(const blRawIterator<blDataType>& rawIterator){this->m_ptr = rawIterator.getPtr();}
        blRawReverseIterator(const blRawReverseIterator<blDataType>& rawReverseIterator) = default;
        ~blRawReverseIterator(){}
    
        blRawReverseIterator<blDataType>&           operator=(const blRawReverseIterator<blDataType>& rawReverseIterator) = default;
        blRawReverseIterator<blDataType>&           operator=(const blRawIterator<blDataType>& rawIterator){this->m_ptr = rawIterator.getPtr();return (*this);}
        blRawReverseIterator<blDataType>&           operator=(blDataType* ptr){this->setPtr(ptr);return (*this);}
    
        blRawReverseIterator<blDataType>&           operator+=(const difference_type& movement){this->m_ptr -= movement;return (*this);}
        blRawReverseIterator<blDataType>&           operator-=(const difference_type& movement){this->m_ptr += movement;return (*this);}
        blRawReverseIterator<blDataType>&           operator++(){--this->m_ptr;return (*this);}
        blRawReverseIterator<blDataType>&           operator--(){++this->m_ptr;return (*this);}
        blRawReverseIterator<blDataType>            operator++(int){auto temp(*this);--this->m_ptr;return temp;}
        blRawReverseIterator<blDataType>            operator--(int){auto temp(*this);++this->m_ptr;return temp;}
        blRawReverseIterator<blDataType>            operator+(const int& movement){auto oldPtr = this->m_ptr;this->m_ptr-=movement;auto temp(*this);this->m_ptr = oldPtr;return temp;}
        blRawReverseIterator<blDataType>            operator-(const int& movement){auto oldPtr = this->m_ptr;this->m_ptr+=movement;auto temp(*this);this->m_ptr = oldPtr;return temp;}
    
        difference_type                             operator-(const blRawReverseIterator<blDataType>& rawReverseIterator){return std::distance(this->getPtr(),rawReverseIterator.getPtr());}
    
        blRawIterator<blDataType>                   base(){blRawIterator<blDataType> forwardIterator(this->m_ptr); ++forwardIterator; return forwardIterator;}
    };
    //-------------------------------------------------------------------

Ahora en algún lugar de su clase de contenedor personalizado:

template<typename blDataType>
class blCustomContainer
{
public: // The typedefs

    typedef blRawIterator<blDataType>              iterator;
    typedef blRawIterator<const blDataType>        const_iterator;

    typedef blRawReverseIterator<blDataType>       reverse_iterator;
    typedef blRawReverseIterator<const blDataType> const_reverse_iterator;

                            .
                            .
                            .

public:  // The begin/end functions

    iterator                                       begin(){return iterator(&m_data[0]);}
    iterator                                       end(){return iterator(&m_data[m_size]);}

    const_iterator                                 cbegin(){return const_iterator(&m_data[0]);}
    const_iterator                                 cend(){return const_iterator(&m_data[m_size]);}

    reverse_iterator                               rbegin(){return reverse_iterator(&m_data[m_size - 1]);}
    reverse_iterator                               rend(){return reverse_iterator(&m_data[-1]);}

    const_reverse_iterator                         crbegin(){return const_reverse_iterator(&m_data[m_size - 1]);}
    const_reverse_iterator                         crend(){return const_reverse_iterator(&m_data[-1]);}

                            .
                            .
                            .
    // This is the pointer to the
    // beginning of the data
    // This allows the container
    // to either "view" data owned
    // by other containers or to
    // own its own data
    // You would implement a "create"
    // method for owning the data
    // and a "wrap" method for viewing
    // data owned by other containers

    blDataType*                                    m_data;
};
Enzo
fuente
Creo que el operador + y el operador pueden tener las operaciones al revés. Parece que operador + está restando movimiento del puntero que no agrega y operador- lo está agregando. Esto parece al revés
Beached
Es para el iterador inverso, operador + debería ir hacia atrás y operador- debería avanzar
Enzo
2
Increíble. La respuesta aceptada es demasiado alto. Esto es asombroso Gracias Enzo
FernandoZ
Necesitas editar tu respuesta. Suponiendo que m_data se haya asignado con elementos m_size, obtendrá Comportamiento indefinido: m_data[m_size]es UB. Simplemente puede solucionarlo reemplazándolo por m_data+m_size. Para iteradores inversa, tanto m_data[-1]y m_data-1son incorrectos (UB). Para arreglar reverse_iterators necesitará usar los "punteros al siguiente truco del elemento".
Arnaud
Arnaud, acabo de agregar el miembro puntero a la clase de contenedor personalizado que muestra mejor lo que quise decir.
Enzo
24

A menudo olvidan que iteratordeben convertirse const_iteratorpero no al revés. Aquí hay una manera de hacer eso:

template<class T, class Tag = void>
class IntrusiveSlistIterator
   : public std::iterator<std::forward_iterator_tag, T>
{
    typedef SlistNode<Tag> Node;
    Node* node_;

public:
    IntrusiveSlistIterator(Node* node);

    T& operator*() const;
    T* operator->() const;

    IntrusiveSlistIterator& operator++();
    IntrusiveSlistIterator operator++(int);

    friend bool operator==(IntrusiveSlistIterator a, IntrusiveSlistIterator b);
    friend bool operator!=(IntrusiveSlistIterator a, IntrusiveSlistIterator b);

    // one way conversion: iterator -> const_iterator
    operator IntrusiveSlistIterator<T const, Tag>() const;
};

En el aviso anterior, cómo se IntrusiveSlistIterator<T>convierte a IntrusiveSlistIterator<T const>. Si Tya es así, constesta conversión nunca se usa.

Maxim Egorushkin
fuente
En realidad, también puede hacerlo al revés definiendo un constructor de copia que sea plantilla, no se compilará si intenta convertir el tipo subyacente de constno a const.
Matthieu M.
¿No terminarás con un inválido IntrusiveSlistIterator<T const, void>::operator IntrusiveSlistIterator<T const, void>() const?
Potatoswatter
Ah, es válido, pero Comeau da una advertencia y sospecho que muchos otros también lo harán. Una enable_ifpodría arreglarlo, pero ...
Potatoswatter
No me molesté con enable_if porque el compilador lo deshabilita de todos modos, aunque algunos compiladores dan una advertencia (g ++ ser un buen chico no advierte).
Maxim Egorushkin
1
@Matthieu: si uno va con un constructor de plantillas, al convertir const_iterator en iterador, el compilador produce un error dentro del constructor, lo que hace que el usuario se rasque la cabeza en confusión y pronuncie wtf. Con el operador de conversión que publiqué, el compilador simplemente dice que no hay una conversión adecuada de const_iterator a iterator, lo cual, en mi opinión, es más claro.
Maxim Egorushkin
23

Boost tiene algo para ayudar: la biblioteca Boost.Iterator.

Más precisamente esta página: boost :: iterator_adaptor .

Lo que es muy interesante es el Ejemplo de tutorial que muestra una implementación completa, desde cero, para un tipo personalizado.

template <class Value>
class node_iter
  : public boost::iterator_adaptor<
        node_iter<Value>                // Derived
      , Value*                          // Base
      , boost::use_default              // Value
      , boost::forward_traversal_tag    // CategoryOrTraversal
    >
{
 private:
    struct enabler {};  // a private type avoids misuse

 public:
    node_iter()
      : node_iter::iterator_adaptor_(0) {}

    explicit node_iter(Value* p)
      : node_iter::iterator_adaptor_(p) {}

    // iterator convertible to const_iterator, not vice-versa
    template <class OtherValue>
    node_iter(
        node_iter<OtherValue> const& other
      , typename boost::enable_if<
            boost::is_convertible<OtherValue*,Value*>
          , enabler
        >::type = enabler()
    )
      : node_iter::iterator_adaptor_(other.base()) {}

 private:
    friend class boost::iterator_core_access;
    void increment() { this->base_reference() = this->base()->next(); }
};

El punto principal, como ya se ha citado, es utilizar una implementación de plantilla única y typedefesta.

Matthieu M.
fuente
¿Puedes explicar el significado de este comentario? // a private type avoids misuse
kevinarpe
@kevinarpe: enablerla persona que llama nunca tiene la intención de ser proveedor, por lo que supongo que lo hacen privado para evitar que las personas intenten pasarlo accidentalmente. No creo, de ninguna manera, que pueda crear ningún problema para pasarlo, ya que la protección radica en enable_if.
Matthieu M.
16

No sé si Boost tiene algo que pueda ayudar.

Mi patrón preferido es simple: tome un argumento de plantilla que sea igual a value_type, calificado o no const. Si es necesario, también un tipo de nodo. Entonces, bueno, todo se acomoda.

Solo recuerde parametrizar (template-ize) todo lo que debe ser, incluido el constructor de copia y operator==. En su mayor parte, la semántica de constcreará un comportamiento correcto.

template< class ValueType, class NodeType >
struct my_iterator
 : std::iterator< std::bidirectional_iterator_tag, T > {
    ValueType &operator*() { return cur->payload; }

    template< class VT2, class NT2 >
    friend bool operator==
        ( my_iterator const &lhs, my_iterator< VT2, NT2 > const &rhs );

    // etc.

private:
    NodeType *cur;

    friend class my_container;
    my_iterator( NodeType * ); // private constructor for begin, end
};

typedef my_iterator< T, my_node< T > > iterator;
typedef my_iterator< T const, my_node< T > const > const_iterator;
Agua de patata
fuente
Nota: parece que sus conversiones iterator-> const_iterator y back están rotas.
Maxim Egorushkin
@Maxim: Sí, en realidad no puedo encontrar ningún ejemplo de uso de mi técnica: vP. No estoy seguro de qué quiere decir que las conversiones están rotas, ya que simplemente no las curilustré , pero podría haber un problema al acceder desde el iterador de constidad opuesta. La solución que viene a mi mente es friend my_container::const_iterator; friend my_container::iterator;, pero no creo que sea así como lo hice antes ... de todos modos este esquema general funciona.
Potatoswatter
1
* hacer eso friend classen ambos casos.
Potatoswatter
Ha pasado algún tiempo, pero ahora recuerdo que las conversiones deberían basarse (por SFINAE) en la buena formación de las inicializaciones de miembros subyacentes. Esto sigue el patrón SCARY (pero esta publicación es anterior a esa terminología).
Potatoswatter
13

Hay muchas buenas respuestas, pero creé un encabezado de plantilla que uso que es bastante conciso y fácil de usar.

Para agregar un iterador a su clase, solo es necesario escribir una clase pequeña para representar el estado del iterador con 7 funciones pequeñas, de las cuales 2 son opcionales:

#include <iostream>
#include <vector>
#include "iterator_tpl.h"

struct myClass {
  std::vector<float> vec;

  // Add some sane typedefs for STL compliance:
  STL_TYPEDEFS(float);

  struct it_state {
    int pos;
    inline void begin(const myClass* ref) { pos = 0; }
    inline void next(const myClass* ref) { ++pos; }
    inline void end(const myClass* ref) { pos = ref->vec.size(); }
    inline float& get(myClass* ref) { return ref->vec[pos]; }
    inline bool cmp(const it_state& s) const { return pos != s.pos; }

    // Optional to allow operator--() and reverse iterators:
    inline void prev(const myClass* ref) { --pos; }
    // Optional to allow `const_iterator`:
    inline const float& get(const myClass* ref) const { return ref->vec[pos]; }
  };
  // Declare typedef ... iterator;, begin() and end() functions:
  SETUP_ITERATORS(myClass, float&, it_state);
  // Declare typedef ... reverse_iterator;, rbegin() and rend() functions:
  SETUP_REVERSE_ITERATORS(myClass, float&, it_state);
};

Entonces puede usarlo como esperaría de un iterador STL:

int main() {
  myClass c1;
  c1.vec.push_back(1.0);
  c1.vec.push_back(2.0);
  c1.vec.push_back(3.0);

  std::cout << "iterator:" << std::endl;
  for (float& val : c1) {
    std::cout << val << " "; // 1.0 2.0 3.0
  }

  std::cout << "reverse iterator:" << std::endl;
  for (auto it = c1.rbegin(); it != c1.rend(); ++it) {
    std::cout << *it << " "; // 3.0 2.0 1.0
  }
}

Espero que ayude.

VinGarcia
fuente
1
¡Este archivo de plantilla resolvió todos mis problemas de iterador!
Perrykipkerrie