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

240

J'ai une classe de conteneur personnalisée pour laquelle j'aimerais écrire le iteratoretconst_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 que dois-je savoir?

Je voudrais également éviter la duplication de code (je le ressens const_iteratoret iteratorpartage beaucoup de choses; doit-on 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.

ereOn
la source
Le modèle d'itérateur du GoF est-il envisagé?
DumbCoder
3
@DumbCoder: En C ++, il est souvent souhaitable d'avoir des itérateurs qui sont conformes à la STL, car ils fonctionneront bien avec tous les conteneurs et algorithmes existants fournis par la STL. Bien que le concept soit similaire, il existe quelques différences par rapport au modèle proposé par le GoF.
Björn Pollex
J'ai posté un échantillon de l'itérateur personnalisé ici
Valdemar_Rudolfovich
1
La complexité de ces réponses suggère que le C ++ est soit un langage indigne de quoi que ce soit d'autre que les devoirs pour les étudiants de premier cycle, ou que les réponses sont trop compliquées et erronées. Il doit y avoir un moyen plus simple dans Cpp? Comme CMake et Automake avant de le faire, le C brut extrait d'un prototype de python semble beaucoup plus facile que cela.
Christopher

Réponses:

157
  • Choisissez le type d'itérateur qui correspond à votre conteneur: entrée, sortie, transfert, etc.
  • Utilisez les classes d'itérateur de base de la bibliothèque standard. Par exemple, std::iteratoravec random_access_iterator_tag. Ces classes de base définissent toutes les définitions de type requises par STL et effectuent d'autres travaux.
  • Pour éviter la duplication de code, la classe d'itérateur doit être une classe de modèle et être paramétrée par "type de valeur", "type de pointeur", "type de référence" ou toutes (dépend de 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;

    Remarquez iterator_typeet const_iterator_typedéfinissez les types: ce sont des types pour vos itérateurs non const et const.

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

EDIT: std::iterator est obsolète depuis C ++ 17. Voir une discussion connexe ici .

Andrey
la source
8
@Potatoswatter: Je n'ai pas rétrogradé cela, mais, hé, ce random_access_iteratorn'est pas dans la norme et la réponse ne gère pas la conversion mutable en const. Vous voulez probablement hériter de, par exemple std::iterator<random_access_iterator_tag, value_type, ... optional arguments ...>.
Yakov Galka,
2
Ouais, je ne sais pas trop comment ça marche. Si j'ai la méthode RefType operator*() { ... }, je suis un pas de plus - mais cela n'aide pas, car j'ai encore besoin RefType operator*() const { ... }.
Autumnsault
31
std::iteratorest proposé pour dépréciation en C ++ 17 .
TypeIA
20
std::iterator est obsolète
diapir
5
Si cela est déconseillé, quelle est la "nouvelle" façon appropriée de le faire à la place?
SasQ
56

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 "conteneur personnalisé".
    • 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. Avaient fini!!!

Enfin, pour définir nos classes d'itérateurs personnalisées:

REMARQUE: lors de la définition d'itérateurs personnalisés, nous dérivons des catégories d'itérateurs standard pour indiquer aux algorithmes STL 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é:

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
la source
Je pense que l'opérateur + et l'opérateur- peuvent avoir les opérations à l'envers. Il semble que l'opérateur + soustrait le mouvement du pointeur ne l'ajoute pas et l'opérateur- l'ajoute. Cela semble à l'envers
Beached
C'est pour l'itérateur inversé, l'opérateur + devrait reculer et l'opérateur- devrait avancer
Enzo
2
Impressionnant. La réponse acceptée est de trop haut niveau. C'est génial. Merci Enzo.
FernandoZ
Vous devez modifier votre réponse. En supposant que m_data a été alloué avec des éléments m_size, vous obtenez un comportement indéfini: m_data[m_size]est UB. Vous pouvez simplement le réparer en le remplaçant par m_data+m_size. Pour les itérateurs inversés, les deux m_data[-1]et m_data-1sont incorrects (UB). Pour corriger les reverse_iterators, vous devrez utiliser les "pointeurs vers le prochain élément".
Arnaud
Arnaud, je viens d'ajouter le membre du pointeur à la classe de conteneur personnalisé qui montre mieux ce que je voulais dire.
Enzo
24

Ils oublient souvent que cela iteratordoit se convertir const_iteratormais pas l'inverse. Voici une façon de procéder:

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 la remarque ci-dessus, comment se IntrusiveSlistIterator<T>convertit IntrusiveSlistIterator<T const>. Si Test déjà constcette conversion n'est jamais utilisée.

Maxim Egorushkin
la source
En fait, vous pouvez également le faire dans l'autre sens en définissant un constructeur de copie qui est un modèle, il ne sera pas compilé si vous essayez de convertir le type sous-jacent de constnon const.
Matthieu M.
Ne vous retrouverez-vous pas avec un invalide IntrusiveSlistIterator<T const, void>::operator IntrusiveSlistIterator<T const, void>() const?
Potatoswatter
Ah, c'est valable, mais Comeau donne un avertissement et je soupçonne que beaucoup d'autres le seront aussi. Un enable_ifproblème pourrait être
résolu
Je n'ai pas pris la peine d'utiliser enable_if car le compilateur le désactive de toute façon, bien que certains compilateurs donnent un avertissement (g ++ étant un bon garçon ne l'avertit pas).
Maxim Egorushkin
1
@Matthieu: Si l'on va avec un constructeur de modèle, lors de la conversion de const_iterator en itérateur, le compilateur produit une erreur à l'intérieur du constructeur, ce qui oblige l'utilisateur à se gratter la tête dans la confusion et à prononcer wtf. Avec l'opérateur de conversion que j'ai publié, le compilateur dit simplement qu'il n'y a pas de conversion appropriée de const_iterator en itérateur, ce qui, IMO, est plus clair.
Maxim Egorushkin
23

Boost a quelque chose à 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 l' exemple de didacticiel 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é mentionné, est d'utiliser une seule implémentation de modèle et typedefcela.

Matthieu M.
la source
Pouvez-vous expliquer le sens de ce commentaire? // a private type avoids misuse
kevinarpe
@kevinarpe: enablern'est jamais destiné à être fournisseur par l'appelant, donc je suppose qu'ils le rendent privé pour éviter que des personnes tentent accidentellement de le transmettre. Je ne pense pas, à première vue, que cela pourrait créer un problème pour le passer, car la protection réside enable_if.
Matthieu M.
16

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

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

N'oubliez pas de paramétrer (template-ize) tout ce qui doit être, y compris le constructeur de copie et operator==. Pour la plupart, la sémantique de constcré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;
Potatoswatter
la source
Remarque: il semble que votre itérateur de conversions-> const_iterator et retour soient cassés.
Maxim Egorushkin
@Maxim: Oui, je ne trouve aucun exemple d'utilisation de ma technique: vP. Je ne sais pas ce que vous voulez dire, les conversions sont rompues, car je ne les ai tout simplement pas illustrées, mais il peut y avoir un problème d'accès à curpartir de l'itérateur de constance opposée. La solution qui me vient à l'esprit est friend my_container::const_iterator; friend my_container::iterator;, mais je ne pense pas que ce soit comme ça que je l'ai fait avant… de toute façon ce schéma général fonctionne.
Potatoswatter
1
* faites cela friend classdans les deux cas.
Potatoswatter
Cela fait un certain temps, mais je me souviens maintenant que les conversions devraient être fondées (par SFINAE) sur la bonne forme des initialisations des membres sous-jacents. Cela suit le modèle SCARY (mais ce post est antérieur à cette terminologie).
Potatoswatter
13

Il y a plein de bonnes réponses mais j'ai créé un en- tête de modèle que j'utilise qui est assez concis et facile à utiliser.

Pour ajouter un itérateur à votre classe, il suffit d'écrire une petite classe pour représenter l'état de l'itérateur avec 7 petites fonctions, dont 2 facultatives:

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

Ensuite, vous pouvez l'utiliser comme vous vous attendez d'un itérateur 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
  }
}

J'espère que ça aide.

VinGarcia
la source
1
Ce fichier de modèle a résolu tous mes problèmes d'itérateur!
Perrykipkerrie