Jak poprawnie zaimplementować niestandardowe iteratory i const_iterators?

240

Mam niestandardową klasę kontenera, dla której chciałbym napisać klasy iteratori const_iterator.

Nigdy wcześniej tego nie robiłem i nie znalazłem odpowiedniego poradnika. Jakie są wytyczne dotyczące tworzenia iteratorów i o czym powinienem wiedzieć?

Chciałbym również uniknąć powielania kodu (czuję to const_iteratori iteratordzielę się wieloma rzeczami; czy jedna z nich należy podklasować?

Uwaga: Jestem całkiem pewien, że Boost ma coś na to, ale nie mogę tego tutaj użyć z wielu głupich powodów.

ereOn
źródło
Czy wzorzec iteratora GoF jest w ogóle brany pod uwagę?
DumbCoder
3
@DumbCoder: W C ++ często jest pożądane, aby iteratory były zgodne z STL, ponieważ będą działać dobrze ze wszystkimi istniejącymi kontenerami i algorytmami dostarczonymi przez STL. Chociaż koncepcja jest podobna, istnieją pewne różnice w schemacie zaproponowanym przez GoF.
Björn Pollex
Tutaj
Valdemar_Rudolfovich,
1
Złożoność tych odpowiedzi sugeruje, że C ++ jest albo językiem niegodnym niczego poza zadaniami domowymi dla podskakujących studentów, albo odpowiedzi są nadmiernie skomplikowane i błędne. Musi być prostszy sposób w Cpp? Podobnie jak CMake i Automake przed względnym stworzeniem, surowe C gotowane z prototypu python wydaje się znacznie łatwiejsze.
Christopher

Odpowiedzi:

157
  • Wybierz typ iteratora, który pasuje do Twojego kontenera: wejście, wyjście, przesyłanie dalej itp.
  • Użyj podstawowych klas iteratorów ze standardowej biblioteki. Na przykład za std::iteratorpomocą random_access_iterator_tag. Te klasy podstawowe definiują wszystkie definicje typów wymagane przez STL i wykonują inną pracę.
  • Aby uniknąć powielania kodu, klasa iteratora powinna być klasą szablonu i powinna być sparametryzowana według „typu wartości”, „typu wskaźnika”, „typu odniesienia” lub wszystkich (zależnie od implementacji). Na przykład:

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

    Uwaga iterator_typei const_iterator_typedefinicje typów: są to typy dla iteratorów non-const i const.

Zobacz także: standardowe odwołanie do biblioteki

EDYCJA: std::iterator jest przestarzała od C ++ 17. Zobacz odpowiednią dyskusję tutaj .

Andrey
źródło
8
@Potatoswatter: Nie zanegowałem tej oceny, ale, hej, random_access_iteratornie ma jej w standardzie, a odpowiedź nie obsługuje konwersji zmiennej na stałą . Prawdopodobnie chcesz dziedziczyć, na przykład std::iterator<random_access_iterator_tag, value_type, ... optional arguments ...>.
Yakov Galka
2
Tak, nie jestem pewien, jak to działa. Jeśli mam tę metodę RefType operator*() { ... }, jestem o krok bliżej - ale to nie pomaga, ponieważ wciąż potrzebuję RefType operator*() const { ... }.
Autumnsault
31
std::iteratorjest proponowane do wycofania w C ++ 17 .
TypeIA
20
std::iterator jest przestarzałe
diapir
5
Jeśli jest to przestarzałe, jaki jest właściwy „nowy” sposób na zrobienie tego?
SasQ,
56

Pokażę ci, jak łatwo zdefiniować iteratory dla niestandardowych kontenerów, ale na wszelki wypadek utworzyłem bibliotekę c ++ 11, która pozwala łatwo tworzyć niestandardowe iteratory z niestandardowym zachowaniem dla dowolnego typu kontenera, ciągłego lub niesąsiadujące.

Możesz go znaleźć na Github

Oto proste kroki tworzenia i używania niestandardowych iteratorów:

  1. Utwórz klasę „niestandardowego iteratora”.
  2. Zdefiniuj typedefs w swojej klasie „niestandardowego kontenera”.
    • na przykład typedef blRawIterator< Type > iterator;
    • na przykład typedef blRawIterator< const Type > const_iterator;
  3. Zdefiniuj funkcje „początek” i „koniec”
    • na przykład iterator begin(){return iterator(&m_data[0]);};
    • na przykład const_iterator cbegin()const{return const_iterator(&m_data[0]);};
  4. Gotowe !!!

Wreszcie, aby zdefiniować nasze niestandardowe klasy iteratorów:

UWAGA: Definiując niestandardowe iteratory, wywodzimy się ze standardowych kategorii iteratorów, aby algorytmy STL znały rodzaj iteratora, który stworzyliśmy.

W tym przykładzie definiuję iterator losowego dostępu i odwrotny iterator losowego dostępu:

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

Teraz gdzieś w niestandardowej klasie kontenera:

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
źródło
Myślę, że operator + i operator- mogą mieć operacje wstecz. Wygląda na to, że operator + odejmuje ruch od wskaźnika, który się nie dodaje, a operator- go dodaje. Wydaje się to
odwrócone
To jest dla iteratora wstecznego, operator + powinien cofnąć się, a operator powinien iść do przodu
Enzo
2
Niesamowite. Akceptowana odpowiedź jest zbyt wysoka. To jest niesamowite. Dziękuję Enzo.
FernandoZ,
Musisz edytować swoją odpowiedź. Zakładając, że m_data została przypisana do elementów m_size, otrzymasz niezdefiniowane zachowanie: m_data[m_size]to UB. Możesz to po prostu naprawić, zastępując go m_data+m_size. Na odwrotnej iteratorami, jak m_data[-1]i m_data-1nie są poprawne (UB). Aby naprawić reverse_iterators, musisz użyć „wskaźników do następnego elementu trick”.
Arnaud
Arnaud, właśnie dodałem element wskaźnika do niestandardowej klasy kontenera, która lepiej pokazuje, co miałem na myśli.
Enzo
24

Często zapominają, że iteratormuszą przejść na, const_iteratorale nie na odwrót. Oto sposób, aby to zrobić:

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

W powyższym ogłoszeniu IntrusiveSlistIterator<T>konwertuje się na IntrusiveSlistIterator<T const>. Jeśli Tjest już, constta konwersja nigdy nie zostanie wykorzystana.

Maxim Egorushkin
źródło
W rzeczywistości możesz to zrobić na odwrót, definiując konstruktor kopii, który jest szablonem, nie skompiluje się, jeśli spróbujesz rzutować typ bazowy z constna non- const.
Matthieu M.,
Czy nie skończysz z nieważnym IntrusiveSlistIterator<T const, void>::operator IntrusiveSlistIterator<T const, void>() const?
Potatoswatter
Ach, to ważne, ale Comeau daje ostrzeżenie i podejrzewam, że wielu innych również. enable_ifMoże go naprawić, ale ...
Potatoswatter
Nie przejmowałem się funkcją enable_if, ponieważ kompilator i tak ją wyłącza, chociaż niektóre kompilatory dają ostrzeżenie (g ++ jako dobry chłopiec nie ostrzega).
Maxim Egorushkin
1
@ Matthieu: Jeśli ktoś korzysta z konstruktora szablonów, podczas konwersji const_iterator na iterator kompilator generuje błąd wewnątrz konstruktora, co powoduje, że użytkownik drapie się po głowie i mówi wtf. Za pomocą operatora konwersji, który opublikowałem, kompilator po prostu mówi, że nie ma odpowiedniej konwersji z const_iterator na iterator, co, IMO, jest bardziej przejrzyste.
Maxim Egorushkin
23

Boost ma coś, co może pomóc: bibliotekę Boost.Iterator.

Dokładniej ta strona: boost :: iterator_adaptor .

Bardzo interesujący jest samouczek, który pokazuje kompletną implementację od zera dla niestandardowego typu.

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

Najważniejszym punktem, jak już wspomniano, jest użycie implementacji jednego szablonu i typedefto.

Matthieu M.
źródło
Czy możesz wyjaśnić znaczenie tego komentarza? // a private type avoids misuse
kevinarpe
@kevinarpe: enablernigdy nie ma być dostawcą przez dzwoniącego, więc domyślam się, że zapewniają prywatność, aby uniknąć przypadkowej próby przekazania go przez osoby. Nie sądzę, że może to stworzyć jakikolwiek problem, aby go przekazać, ponieważ polega na ochronie enable_if.
Matthieu M.
16

Nie wiem, czy Boost ma coś, co by pomogło.

Mój preferowany wzorzec jest prosty: weź argument szablonu, który jest równy value_typealbo const kwalifikowany, albo nie. W razie potrzeby także typ węzła. No cóż, wszystko wpada na miejsce.

Pamiętaj tylko, aby sparametryzować (szablon-ize) wszystko, co musi być, w tym konstruktor kopii i operator==. W większości semantyka constspowoduje prawidłowe zachowanie.

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
źródło
Uwaga: wygląda na to, że twoje konwersje iterator-> const_iterator i wstecz są zepsute.
Maxim Egorushkin
@ Maxim: Tak, nie mogę znaleźć żadnych przykładów użycia mojej techniki: vP. Nie jestem pewien, co masz na myśli mówiąc, że konwersje są zepsute, ponieważ po prostu ich nie zilustrowałem, ale może istnieć problem curz dostępem z iteratora przeciwnej ciągłości. Przychodzi mi na myśl rozwiązanie friend my_container::const_iterator; friend my_container::iterator;, ale nie sądzę, że tak to robiłem wcześniej… w każdym razie ten ogólny zarys działa.
Potatoswatter
1
* zrób to friend classw obu przypadkach.
Potatoswatter
Minęło trochę czasu, ale przypominam sobie teraz, że konwersje powinny opierać się (przez SFINAE) na dobrze uformowanych bazowych inicjalizacjach elementów. Jest to zgodne ze schematem SCARY (ale ten post poprzedza tę terminologię).
Potatoswatter
13

Istnieje wiele dobrych odpowiedzi, ale utworzyłem nagłówek szablonu, którego używam, który jest dość zwięzły i łatwy w użyciu.

Aby dodać iterator do swojej klasy, wystarczy napisać małą klasę reprezentującą stan iteratora za pomocą 7 małych funkcji, z których 2 są opcjonalne:

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

Następnie możesz użyć go tak, jak można oczekiwać od iteratora 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
  }
}

Mam nadzieję, że to pomoże.

VinGarcia
źródło
1
Ten plik szablonu rozwiązał wszystkie moje problemy z iteratorem!
Perrykipkerrie