Comment implémenter correctement les itérateurs et const_iterators personnalisés ?

Question

J'ai une classe de conteneur personnalisée pour laquelle j'aimerais écrire l'adresse de l'utilisateur. iterator y const_iterator classes.

Je n'ai jamais fait cela auparavant et je n'ai pas réussi à trouver un mode d'emploi approprié. Quelles sont les directives concernant la création d'itérateurs, et à quoi dois-je faire attention ?

J'aimerais également éviter la duplication du code (j'ai le sentiment que const_iterator y iterator partagent beaucoup de choses ; l'un doit-il sous-classer l'autre ?).

Note de bas de page : Je suis presque sûr que Boost a quelque chose pour faciliter cela mais je ne peux pas l'utiliser ici, pour de nombreuses raisons stupides.

Answer 1

• Choisissez le type d'itérateur qui convient à votre conteneur : entrée, sortie, avant, etc.
• Utiliser les classes d'itérateurs de base de la bibliothèque standard. Par exemple, std::iterator avec random_access_iterator_tag Ces classes de base définissent toutes les définitions de type requises par la STL et effectuent d'autres tâches.

• Pour éviter la duplication du code, la classe d'itérateur devrait être une classe modèle et être paramétrée par "type de valeur", "type de pointeur", "type de référence" ou tous ces éléments (selon l'implémentation). Par exemple :

  // 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;

  Avis iterator_type y const_iterator_type les définitions de type : il s'agit de types pour vos itérateurs non-const et const.

Voir aussi : référence de la bibliothèque standard

EDITAR: std::iterator est déprécié depuis C++17. Voir une discussion à ce sujet. aquí .

Answer 2

Je vais vous montrer comment vous pouvez facilement définir des itérateurs pour vos conteneurs personnalisés, mais juste au cas où, j'ai créé une bibliothèque c++11 qui vous permet de créer facilement des itérateurs personnalisés avec un comportement personnalisé pour tout type de conteneur, contigu ou non contigu.

Vous pouvez le trouver sur Github

Voici les étapes simples pour créer et utiliser des itérateurs personnalisés :

1. Créez votre classe "itérateur personnalisé".
2. Définissez les typedefs dans votre classe "custom container".
   • par exemple typedef blRawIterator< Type > iterator;
   • par exemple typedef blRawIterator< const Type > const_iterator;
3. Définir les fonctions "début" et "fin".
   • par exemple iterator begin(){return iterator(&m_data[0]);};
   • par exemple const_iterator cbegin()const{return const_iterator(&m_data[0]);};
4. C'est fait ! !!

Enfin, nous allons définir nos classes d'itérateurs personnalisés :

NOTE : Lorsque nous définissons des itérateurs personnalisés, nous dérivons des catégories d'itérateurs standard pour permettre aux algorithmes de la STL de connaître le type d'itérateur que nous avons créé.

Dans cet exemple, je définis un itérateur d'accès aléatoire et un itérateur d'accès aléatoire inverse :

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;}
   };
   //-------------------------------------------------------------------

Maintenant, quelque part dans votre classe de conteneur personnalisée :

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;
};

Answer 3

Ils oublient souvent que iterator doit être converti en const_iterator mais pas dans l'autre sens. Voici un moyen de le faire :

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;
};

Dans l'exemple ci-dessus, remarquez comment IntrusiveSlistIterator<T> se convertit en IntrusiveSlistIterator<T const> . Si T est déjà const cette conversion n'est jamais utilisée.

Answer 4

Boost a quelque chose pour vous aider : la bibliothèque Boost.Iterator.

Plus précisément cette page : boost::iterator_adaptor .

Ce qui est très intéressant, c'est que Exemple de tutoriel qui montre une implémentation complète, à partir de zéro, pour un type personnalisé.

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(); }
};

Le point principal, comme cela a déjà été cité, est d'utiliser une seule implémentation de modèle et de typedef il.

Answer 5

Je ne sais pas si Boost a quelque chose qui pourrait aider.

Mon modèle préféré est simple : prendre un argument de modèle qui est égal à value_type , qu'il soit qualifié de const ou non. Si nécessaire, également un type de nœud. Ensuite, tout se met en place, en quelque sorte.

N'oubliez pas de paramétrer (template-ize) tout ce qui doit l'être, y compris le constructeur de copie et le module operator== . Pour l'essentiel, la sémantique de const créera un comportement correct.

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;