iterators - list iterator c++

¿Cómo implementar correctamente iteradores personalizados y const_iterators?

Question

Tengo una clase de contenedor personalizada para la que me gustaría escribir el iterator y const_iterator clases const_iterator .

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 de qué debería ser consciente?

También me gustaría evitar la duplicación de código (creo que const_iterator e const_iterator comparten muchas cosas, ¿una de las subclases debería ser 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.

Answer 1

A menudo olvidan que const_iterator debe convertir a const_iterator pero no al revés. Aquí hay una manera de hacerlo:

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 IntrusiveSlistIterator<T> convierte a IntrusiveSlistIterator<T const> . Si T ya está const esta conversión nunca se usa.

Answer 2

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

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

Lo que es muy interesante es el Ejemplo 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 mencionado, es utilizar una sola implementación de plantilla y typedef .

Answer 3

Hay muchas buenas respuestas, pero utilizo un encabezado de plantilla 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 se 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.

Answer 4

No sé si Boost tiene algo que pueda ayudar.

Mi patrón preferido es simple: tomar un argumento de plantilla que sea igual a value_type , ya sea const calificado o no. Si es necesario, también un tipo de nodo. Entonces, bueno, todo cae en su lugar.

Solo recuerde parametrizar (template-ize) todo lo que necesita ser incluido el constructor de copias y el operator== . En su mayor parte, la semántica de const creará 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;

Answer 5

Voy a mostrarte cómo puedes definir fácilmente iteradores para tus contenedores personalizados, pero solo en caso de que haya creado una biblioteca de c ++ 11 que te permita crear fácilmente iteradores personalizados con comportamiento personalizado para cualquier tipo de contenedor, contiguo o no constiguo

Puede encontrarlo en github en https://github.com/navyenzo/blIteratorAPI

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

1. Crea tu clase de "iterador personalizado".
2. Defina typedefs en su clase "contenedor personalizado".
   • Por ejemplo: typedef blRawIterator< Type > iterator;
   • Por ejemplo: typedef blRawIterator< const Type > const_iterator;
3. Definir funciones "iniciales" "final"
   • Por ejemplo: iterator begin(){return iterator(&m_data[0]);};
   • Por ejemplo: const_iterator cbegin()const{return const_iterator(&m_data[0]);};
4. ¡Hemos terminado!

Finalmente, en la definición de nuestras clases de iterador personalizadas:

NOTA: Cuando definimos iteradores personalizados, derivamos de las categorías de iteradores estándar para que los algoritmos AWL sepan 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 std::iterator<std::random_access_iterator_tag,
                                           blDataType,
                                           ptrdiff_t,
                                           blDataType*,
                                           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 ptrdiff_t& movement){m_ptr += movement;return (*this);}
    blRawIterator<blDataType>&                  operator-=(const ptrdiff_t& movement){m_ptr -= movement;return (*this);}
    blRawIterator<blDataType>&                  operator++(){++m_ptr;return (*this);}
    blRawIterator<blDataType>&                  operator--(){--m_ptr;return (*this);}
    blRawIterator<blDataType>                   operator++(ptrdiff_t){auto temp(*this);++m_ptr;return temp;}
    blRawIterator<blDataType>                   operator--(ptrdiff_t){auto temp(*this);--m_ptr;return temp;}
    blRawIterator<blDataType>                   operator+(const ptrdiff_t& movement){auto oldPtr = m_ptr;m_ptr+=movement;auto temp(*this);m_ptr = oldPtr;return temp;}
    blRawIterator<blDataType>                   operator-(const ptrdiff_t& movement){auto oldPtr = m_ptr;m_ptr-=movement;auto temp(*this);m_ptr = oldPtr;return temp;}

    ptrdiff_t                                   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 ptrdiff_t& movement){this->m_ptr -= movement;return (*this);}
    blRawReverseIterator<blDataType>&           operator-=(const ptrdiff_t& 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++(ptrdiff_t){auto temp(*this);--this->m_ptr;return temp;}
    blRawReverseIterator<blDataType>            operator--(ptrdiff_t){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;}

    ptrdiff_t                                   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 tu 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]);}

                            .
                            .
                            .
};

¡¡¡BUENA SUERTE!!!

Answer 6

• Elija el tipo de iterador que se ajuste a su contenedor: entrada, salida, avance, etc.
• Use las clases de iterador base de la biblioteca estándar. Por ejemplo, std::iterator random_access_iterator_tag con random_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 parametrizarse 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;

  Observe las definiciones de tipo const_iterator_type y const_iterator_type : son tipos para sus iteradores no const y const.

Ver también: referencia de biblioteca estándar