Como implementar corretamente os iteradores e const_iterators personalizados?

Eu tenho uma class de contêiner personalizado para o qual eu gostaria de escrever as classs iterator e const_iterator .

Eu nunca fiz isso antes e não consegui encontrar um apropriado como fazer. Quais são as diretrizes sobre a criação do iterador e o que devo saber?

Eu também gostaria de evitar a duplicação de código (eu sinto que const_iterator e iterator compartilham muitas coisas; deveria uma subclass a outra?).

Nota de rodapé: Tenho certeza que o Boost tem algo para aliviar isso, mas não posso usá-lo aqui, por muitas razões estúpidas.

  • Escolha o tipo de iterador que se adapta ao seu contêiner: input, saída, encaminhamento etc.
  • Use as classs do iterador base da biblioteca padrão. Por exemplo, std::iterator com random_access_iterator_tag . Essas classs base definem todas as definições de tipo exigidas pelo STL e fazem outro trabalho.
  • Para evitar duplicação de código, a class iterator deve ser uma class de modelo e ser parametrizada por “tipo de valor”, “tipo de ponteiro”, “tipo de referência” ou todos eles (depende da implementação). Por exemplo:

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

    Observe as definições do tipo iterator_type e const_iterator_type : elas são tipos para seus iteradores non-const e const.

Consulte também: referência da biblioteca padrão

Vou mostrar como é fácil definir iteradores para seus contêineres personalizados, mas caso eu tenha criado uma biblioteca c ++ 11 que permita criar facilmente iteradores personalizados com comportamento personalizado para qualquer tipo de contêiner, contíguo ou não-constante.

Você pode encontrá-lo no github em https://github.com/navyenzo/blIteratorAPI

Aqui estão os passos simples para criar e usar iteradores personalizados:

  1. Crie sua class “iterador personalizado”.
  2. Defina typedefs em sua class “contêiner personalizado”.
    • Para ex: typedef blRawIterator< Type > iterator;
    • Por exemplo: typedef blRawIterator< const Type > const_iterator;
  3. Definir funções “begin” “end”
    • Por ex: iterator begin(){return iterator(&m_data[0]);};
    • Por exemplo: const_iterator cbegin()const{return const_iterator(&m_data[0]);};
  4. Foram realizadas!!!

Finalmente, para definir nossas classs de iterador customizadas:

NOTA: Ao definir os iteradores personalizados, derivamos das categorias padrão do iterador para permitir que os algoritmos STL saibam o tipo de iterador que fizemos

Neste exemplo, eu defino um iterador de access random e um iterador de access random reverso:

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

Agora, em algum lugar da sua class de contêiner personalizada:

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

BOA SORTE!!!

Boost tem algo para ajudar: a biblioteca Boost.Iterator.

Mais precisamente esta página: boost :: iterator_adaptor .

O que é muito interessante é o exemplo de tutorial, que mostra uma implementação completa, do zero, para um tipo personalizado.

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

O ponto principal, como já foi citado, é usar uma implementação de modelo único e typedef lo.

Eles geralmente esquecem que o iterator deve converter para const_iterator mas não o contrário. Aqui está uma maneira de fazer isso:

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

No aviso acima, como IntrusiveSlistIterator converte para IntrusiveSlistIterator . Se T já é const esta conversão nunca é usada.

Eu não sei se o Boost tem algo que possa ajudar.

Meu padrão preferido é simples: pegue um argumento de modelo que seja igual a value_type , seja const qualificado ou não. Se necessário, também um tipo de nó. Então, bem, tudo se encheckbox.

Apenas lembre-se de parametrizar (template-ize) tudo o que precisa ser, incluindo o construtor de cópias e o operator== . Na maior parte, a semântica do const criará o comportamento correto.

 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; 

Há muitas boas respostas, mas tenho um header de modelo que uso bastante conciso e fácil de usar.

Para adicionar um iterador à sua class, é necessário apenas escrever uma pequena class para representar o estado do iterador com 7 pequenas funções, das quais 2 são opcionais:

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

Então você pode usá-lo como você esperaria de um 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 ajude.