Comment implémenter correctement les iterators personnalisés et const_iterators?

J’ai une classe de conteneur personnalisée pour laquelle j’aimerais écrire les classes iterator et const_iterator .

Je ne l’ai jamais fait auparavant et je n’ai pas réussi à trouver une méthode appropriée. Quelles sont les lignes direcsortingces concernant la création d’iterators et à quoi dois-je être conscient?

Je voudrais également éviter la duplication de code (j’estime que const_iterator et iterator partagent beaucoup de choses; faut-il en sous- const_iterator une autre?).

Note de bas de page: Je suis presque sûr que Boost a quelque chose à faire pour remédier à cela, mais je ne peux pas l’utiliser ici pour de nombreuses raisons stupides.

  • Choisissez le type d’iterator correspondant à votre conteneur: entrée, sortie, transfert, etc.
  • Utilisez les classes d’iterators 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 requirejses par STL et random_access_iterator_tag autres tâches.
  • Pour éviter la duplication de code, la classe d’iterator 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 tous (dépend de l’implémentation). Par exemple:

     // iterator class is paramesortingzed by pointer type template  class MyIterator { // iterator class definition goes here }; typedef MyIterator iterator_type; typedef MyIterator const_iterator_type; 

    Remarquez les définitions de type iterator_type et const_iterator_type : ce sont des types pour vos iterators non const et const.

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

Je vais vous montrer comment vous pouvez facilement définir des iterators 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 iterators personnalisés avec un comportement personnalisé pour tout type de conteneur, contigu ou non constantes.

Vous pouvez le trouver sur github sur https://github.com/navyenzo/blIteratorAPI

Voici les étapes simples à suivre pour créer et utiliser des iterators personnalisés:

  1. Créez votre classe “iterator 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 “begin” “end”
    • 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, sur la définition de nos classes d’iterators personnalisées:

REMARQUE: Lors de la définition d’iterators personnalisés, nous dérivons des catégories d’iterators standard pour permettre aux algorithmes STL de connaître le type d’iterator que nous avons créé.

Dans cet exemple, je définis un iterator à access aléatoire et un iterator à access aléatoire inversé:

1.

 //------------------------------------------------------------------- // Raw iterator with random access //------------------------------------------------------------------- template class blRawIterator : public std::iterator { public: blRawIterator(blDataType* ptr = nullptr){m_ptr = ptr;} blRawIterator(const blRawIterator& rawIterator) = default; ~blRawIterator(){} blRawIterator& operator=(const blRawIterator& rawIterator) = default; blRawIterator& operator=(blDataType* ptr){m_ptr = ptr;return (*this);} operator bool()const { if(m_ptr) return true; else return false; } bool operator==(const blRawIterator& rawIterator)const{return (m_ptr == rawIterator.getConstPtr());} bool operator!=(const blRawIterator& rawIterator)const{return (m_ptr != rawIterator.getConstPtr());} blRawIterator& operator+=(const ptrdiff_t& movement){m_ptr += movement;return (*this);} blRawIterator& operator-=(const ptrdiff_t& movement){m_ptr -= movement;return (*this);} blRawIterator& operator++(){++m_ptr;return (*this);} blRawIterator& operator--(){--m_ptr;return (*this);} blRawIterator operator++(ptrdiff_t){auto temp(*this);++m_ptr;return temp;} blRawIterator operator--(ptrdiff_t){auto temp(*this);--m_ptr;return temp;} blRawIterator operator+(const ptrdiff_t& movement){auto oldPtr = m_ptr;m_ptr+=movement;auto temp(*this);m_ptr = oldPtr;return temp;} blRawIterator 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& 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 class blRawReverseIterator : public blRawIterator { public: blRawReverseIterator(blDataType* ptr = nullptr):blRawIterator(ptr){} blRawReverseIterator(const blRawIterator& rawIterator){this->m_ptr = rawIterator.getPtr();} blRawReverseIterator(const blRawReverseIterator& rawReverseIterator) = default; ~blRawReverseIterator(){} blRawReverseIterator& operator=(const blRawReverseIterator& rawReverseIterator) = default; blRawReverseIterator& operator=(const blRawIterator& rawIterator){this->m_ptr = rawIterator.getPtr();return (*this);} blRawReverseIterator& operator=(blDataType* ptr){this->setPtr(ptr);return (*this);} blRawReverseIterator& operator+=(const ptrdiff_t& movement){this->m_ptr -= movement;return (*this);} blRawReverseIterator& operator-=(const ptrdiff_t& movement){this->m_ptr += movement;return (*this);} blRawReverseIterator& operator++(){--this->m_ptr;return (*this);} blRawReverseIterator& operator--(){++this->m_ptr;return (*this);} blRawReverseIterator operator++(ptrdiff_t){auto temp(*this);--this->m_ptr;return temp;} blRawReverseIterator operator--(ptrdiff_t){auto temp(*this);++this->m_ptr;return temp;} blRawReverseIterator operator+(const int& movement){auto oldPtr = this->m_ptr;this->m_ptr-=movement;auto temp(*this);this->m_ptr = oldPtr;return temp;} blRawReverseIterator 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& rawReverseIterator){return std::distance(this->getPtr(),rawReverseIterator.getPtr());} blRawIterator base(){blRawIterator forwardIterator(this->m_ptr); ++forwardIterator; return forwardIterator;} }; //------------------------------------------------------------------- 

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

 template class blCustomContainer { public: // The typedefs typedef blRawIterator iterator; typedef blRawIterator const_iterator; typedef blRawReverseIterator reverse_iterator; typedef blRawReverseIterator 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; }; 

BONNE CHANCE!!!

Boost a quelque chose à 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 tutoriel qui montre une implémentation complète, à partir de rien, pour un type personnalisé.

 template  class node_iter : public boost::iterator_adaptor< node_iter // 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  node_iter( node_iter const& other , typename boost::enable_if< boost::is_convertible , 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é, consiste à utiliser une implémentation de modèle unique et à la typedef .

Ils oublient souvent que l’ iterator doit être converti en const_iterator mais pas l’inverse. Voici un moyen de le faire:

 template class IntrusiveSlistIterator : public std::iterator { typedef SlistNode 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() const; }; 

Dans la remarque ci-dessus, comment IntrusiveSlistIterator converti en IntrusiveSlistIterator . Si T est déjà const cette conversion n’est jamais utilisée.

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

Mon modèle préféré est simple: prenez un argument de template qui est égal à value_type , soit qualifié ou non. Si nécessaire, également un type de noeud. Alors, tout tombe en place.

Rappelez-vous juste de paramétrer (template-ize) tout ce qui doit être, y compris le constructeur de copie et l’ operator== . La plupart du temps, 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; 

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

Pour append un iterator à votre classe, il suffit d’écrire une petite classe pour représenter l’état de l’iterator avec 7 petites fonctions, dont 2 sont facultatives:

 #include  #include  #include "iterator_tpl.h" struct myClass { std::vector 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 l’attendez d’un iterator 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.