Como implementar corretamente iteradores e const_iterators personalizados?

240

Eu tenho uma classe de contêiner personalizada para a qual gostaria de escrever as classes iteratore const_iterator.

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

Eu também gostaria de evitar a duplicação de código (sinto isso const_iteratore iteratorcompartilho muitas coisas; uma deve subclassificar a outra?).

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

ereOn
fonte
O padrão de iterador do GoF está sendo considerado?
DumbCoder
3
@DumbCoder: em C ++, geralmente é desejável ter iteradores compatíveis com STL, porque eles funcionarão bem com todos os contêineres e algoritmos existentes fornecidos pelo STL. Embora o conceito seja semelhante, existem algumas diferenças no padrão proposto pelo GoF.
Björn Pollex
Eu publiquei uma amostra do iterador personalizado aqui
Valdemar_Rudolfovich
1
A complexidade dessas respostas sugere que o C ++ é uma linguagem indigna de qualquer coisa que não seja a tarefa de casa para alunos de graduação mais avançados, ou as respostas são complicadas demais e incorretas. Deve haver uma maneira mais fácil no Cpp? Como o CMake e o Automake, antes que parecesse ser produzido, o C bruto, produzido a partir de um protótipo de python, parece muito mais fácil do que isso.
Christopher

Respostas:

156
  • Escolha o tipo de iterador adequado ao seu contêiner: entrada, saída, encaminhamento etc.
  • Use as classes do iterador base da biblioteca padrão. Por exemplo, std::iteratorcom random_access_iterator_tag. Essas classes base definem todas as definições de tipo exigidas pelo STL e fazem outro trabalho.
  • Para evitar a duplicação de código, a classe do iterador deve ser uma classe 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 <typename PointerType> class MyIterator {
        // iterator class definition goes here
    };
    
    typedef MyIterator<int*> iterator_type;
    typedef MyIterator<const int*> const_iterator_type;

    Definições de aviso iterator_typee const_iterator_typetipo: são tipos para seus iteradores não const e const.

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

EDIT: std::iterator está obsoleto desde C ++ 17. Veja uma discussão relacionada aqui .

Andrey
fonte
8
@ Potatoswatter: Não diminuiu o voto, mas, ei, random_access_iteratornão está no padrão e a resposta não lida com a conversão mutable para const. Você provavelmente deseja herdar, por exemplo std::iterator<random_access_iterator_tag, value_type, ... optional arguments ...>.
Yakov Galka
2
Sim, não tenho muita certeza de como isso funciona. Se eu tiver o método RefType operator*() { ... }, estou um passo mais perto - mas não ajuda, porque ainda preciso RefType operator*() const { ... }.
Autumnsault 5/09/13
31
std::iteratoré proposto para descontinuação em C ++ 17 .
TypeIA
20
std::iterator foi descontinuado
diapir 14/02
5
Se isso for descontinuado, qual é a maneira "nova" apropriada de fazer isso?
SasQ 24/09/19
55

Vou mostrar como você pode definir facilmente iteradores para seus contêineres personalizados, mas, no caso de eu ter criado uma biblioteca c ++ 11, você pode criar facilmente iteradores personalizados com comportamento personalizado para qualquer tipo de contêiner, contíguo ou não contíguo.

Você pode encontrá-lo no Github

Aqui estão as etapas simples para criar e usar iteradores personalizados:

  1. Crie sua classe "iterador personalizado".
  2. Defina typedefs na sua classe "container personalizado".
    • por exemplo typedef blRawIterator< Type > iterator;
    • por exemplo typedef blRawIterator< const Type > const_iterator;
  3. Defina as funções "iniciar" e "terminar"
    • por exemplo iterator begin(){return iterator(&m_data[0]);};
    • por exemplo const_iterator cbegin()const{return const_iterator(&m_data[0]);};
  4. Foram realizadas!!!

Por fim, para definir nossas classes de iteradores personalizados:

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

Neste exemplo, defino um iterador de acesso aleatório e um iterador de acesso aleatório reverso:

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

Agora em algum lugar da sua classe de contêiner 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]);}

                            .
                            .
                            .
    // 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
fonte
Eu acho que o operador + e operator- podem ter as operações ao contrário. Parece que o operador + está subtraindo o movimento do ponteiro que não está adicionando e o operador- está adicionando. Isso parece ao contrário
encalhado
É para o iterador reverso, operador + deve retroceder e operador- deve avançar
Enzo
2
Impressionante. A resposta aceita é um nível muito alto. Isso é incrível. Obrigado Enzo.
FernandoZ
Você precisa editar sua resposta. Supondo que m_data foi alocado com elementos m_size, você obtém Comportamento indefinido: m_data[m_size]é UB. Você pode simplesmente consertá-lo substituindo-o por m_data+m_size. Para iteradores reversos, ambos m_data[-1]e m_data-1estão incorretos (UB). Para consertar reverse_iterators, você precisará usar o "ponteiros para o próximo elemento".
Arnaud
Arnaud, acabei de adicionar o membro ponteiro à classe de contêiner personalizado que mostra melhor o que eu quis dizer.
Enzo
24

Muitas vezes esquecem que isso iteratordeve ser convertido, const_iteratormas não o contrário. Aqui está uma maneira de fazer isso:

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

No aviso acima, como se IntrusiveSlistIterator<T>converte em IntrusiveSlistIterator<T const>. Se Tjá estiver, constessa conversão nunca será usada.

Maxim Egorushkin
fonte
Na verdade, você também pode fazer o contrário, definindo um construtor de cópia que é modelo, que não será compilado se você tentar converter o tipo subjacente de constpara não const.
Matthieu M.
Você não vai acabar com um inválido IntrusiveSlistIterator<T const, void>::operator IntrusiveSlistIterator<T const, void>() const?
Potatoswatter 27/08/10
Ah, é válido, mas Comeau dá um aviso e eu suspeito que muitos outros também. Um enable_ifpode consertá-lo, mas ...
Potatoswatter 27/08/10
Eu não me incomodei com enable_if porque o compilador o desativa de qualquer maneira, embora alguns compiladores dêem um aviso (g ++ ser um bom garoto não avisa).
Maxim Egorushkin
1
@ Matthieu: Se alguém vai com um construtor de modelos, ao converter const_iterator em iterador, o compilador produz um erro dentro do construtor, fazendo com que o usuário coça a cabeça com confusão e total wtf. Com o operador de conversão que eu postei, o compilador apenas diz que não há conversão adequada de const_iterator para iterador, o que, na IMO, é mais claro.
Maxim Egorushkin
23

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

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

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

Matthieu M.
fonte
Você pode explicar o significado desse comentário? // a private type avoids misuse
Kevinarpe
@ kevinarpe: enablernunca pretende ser provedor pelo chamador, então meu palpite é que eles o tornam privado para evitar que as pessoas tentem passar por ele acidentalmente. Não acho, de imediato, que isso possa criar qualquer problema para ser realmente aprovado, já que a proteção está dentro enable_if.
Matthieu M.
16

Não sei se o Boost tem algo que ajudaria.

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

Lembre-se de parametrizar (template-ize) tudo o que precisa ser, incluindo o construtor copy e operator==. Na maioria das vezes, a semântica de constcriará 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;
Potatoswatter
fonte
Nota: parece que suas conversões iterator-> const_iterator e back estão com problemas.
Maxim Egorushkin
@ Maxim: Sim, na verdade não consigo encontrar nenhum exemplo de como usar minha técnica: vP. Não sei ao certo o que você quer dizer com as conversões quebradas, pois simplesmente não as ilustrei, mas pode haver um problema ao acessar a curpartir do iterador de constância oposta. A solução que vem à mente é friend my_container::const_iterator; friend my_container::iterator;, mas não acho que tenha sido assim antes ... de qualquer maneira, esse esboço geral funciona.
Potatoswatter 27/08/10
1
* faça isso friend classnos dois casos.
Potatoswatter 27/08/10
Já faz algum tempo, mas lembro-me agora que as conversões devem ser baseadas (pela SFINAE) na boa formação das inicializações dos membros subjacentes. Isso segue o padrão SCARY (mas esta publicação antecede essa terminologia).
Potatoswatter
12

Existem muitas boas respostas, mas eu criei um cabeçalho de modelo que é bastante conciso e fácil de usar.

Para adicionar um iterador à sua classe, basta escrever uma classe pequena para representar o estado do iterador com 7 pequenas funções, das quais 2 são opcionais:

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

Em seguida, você pode usá-lo como seria de esperar 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.

VinGarcia
fonte
1
Este arquivo de modelo resolveu todos os meus problemas do iterador!
Perrykipkerrie 18/03