Wie implementiere ich benutzerdefinierte Iteratoren und const_iterators korrekt?

240

Ich habe eine benutzerdefinierte Containerklasse, für die ich die Klassen iteratorund schreiben möchte const_iterator.

Ich habe das noch nie gemacht und keine passende Anleitung gefunden. Was sind die Richtlinien für die Erstellung von Iteratoren und worauf sollte ich achten?

Ich möchte auch Code-Duplikate vermeiden (ich fühle das const_iteratorund iteratorteile viele Dinge; sollte eine Unterklasse die andere sein?).

Fußnote: Ich bin mir ziemlich sicher, dass Boost etwas hat, um dies zu erleichtern, aber ich kann es hier aus vielen dummen Gründen nicht verwenden.

ereOn
quelle
Wird das GoF-Iteratormuster überhaupt berücksichtigt?
DumbCoder
3
@DumbCoder: In C ++ ist es häufig wünschenswert, Iteratoren zu haben, die STL-kompatibel sind, da sie mit allen vorhandenen Containern und Algorithmen, die von der STL bereitgestellt werden, gut funktionieren. Obwohl das Konzept ähnlich ist, gibt es einige Unterschiede zu dem vom GoF vorgeschlagenen Muster.
Björn Pollex
Ich habe Probe von benutzerdefinierten Iterator gepostet hier
Valdemar_Rudolfovich
1
Die Komplexität dieser Antworten lässt darauf schließen, dass C ++ entweder eine Sprache ist, die nichts anderes als Hausaufgaben für hochspringende Studenten wert ist, oder dass die Antworten überkompliziert und falsch sind. Es muss einen einfacheren Weg in Cpp geben? Wie CMake und Automake vor der Herstellung scheint rohes C, das aus einem Python-Prototyp gekocht wurde, viel einfacher zu sein.
Christopher

Antworten:

156
  • Wählen Sie den Typ Ihres Iterators, der zu Ihrem Container passt: Eingabe, Ausgabe, Weiterleitung usw.
  • Verwenden Sie Basisiteratorklassen aus der Standardbibliothek. Zum Beispiel std::iteratormit random_access_iterator_tag.Diese Basisklassen alle Typdefinitionen von STL erforderlich definieren und anderer Arbeit verrichten.
  • Um eine Codeduplizierung zu vermeiden, sollte die Iteratorklasse eine Vorlagenklasse sein und durch "Werttyp", "Zeigertyp", "Referenztyp" oder alle (abhängig von der Implementierung) parametrisiert werden. Beispielsweise:

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

    Hinweis- iterator_typeund const_iterator_typeTypdefinitionen: Dies sind Typen für Ihre Nicht-Konstanten- und Konstanten-Iteratoren.

Siehe auch: Standardbibliotheksreferenz

BEARBEITEN: std::iterator ist seit C ++ 17 veraltet. Eine entsprechende Diskussion finden Sie hier .

Andrey
quelle
8
@Potatoswatter: Habe dies nicht herabgestimmt, aber hey, random_access_iteratorist nicht im Standard und die Antwort behandelt nicht die Konvertierung von Mutable zu Const . Sie möchten wahrscheinlich von erben, z std::iterator<random_access_iterator_tag, value_type, ... optional arguments ...>.
Yakov Galka
2
Ja, ich bin mir nicht ganz sicher, wie das funktioniert. Wenn ich die Methode habe RefType operator*() { ... }, bin ich einen Schritt näher - aber es hilft nicht, weil ich noch brauche RefType operator*() const { ... }.
Autumnsault
31
std::iteratorwird in C ++ 17 zur Verwerfung vorgeschlagen .
TypeIA
20
std::iterator wurde veraltet
Diapir
5
Wenn dies veraltet ist, wie wird es stattdessen "richtig" gemacht?
SasQ
55

Ich werde Ihnen zeigen, wie Sie Iteratoren für Ihre benutzerdefinierten Container einfach definieren können, aber nur für den Fall, dass ich eine C ++ 11-Bibliothek erstellt habe, mit der Sie problemlos benutzerdefinierte Iteratoren mit benutzerdefiniertem Verhalten für jeden Containertyp erstellen können, unabhängig davon nicht zusammenhängend.

Sie finden es auf Github

Hier sind die einfachen Schritte zum Erstellen und Verwenden von benutzerdefinierten Iteratoren:

  1. Erstellen Sie Ihre "benutzerdefinierte Iterator" -Klasse.
  2. Definieren Sie typedefs in Ihrer Klasse "Benutzerdefinierter Container".
    • z.B typedef blRawIterator< Type > iterator;
    • z.B typedef blRawIterator< const Type > const_iterator;
  3. Definieren Sie die Funktionen "Anfang" und "Ende"
    • z.B iterator begin(){return iterator(&m_data[0]);};
    • z.B const_iterator cbegin()const{return const_iterator(&m_data[0]);};
  4. Wir sind fertig!!!

Schließlich zur Definition unserer benutzerdefinierten Iteratorklassen:

ANMERKUNG: Bei der Definition von benutzerdefinierten Iteratoren leiten wir die Standard-Iteratorkategorien ab, um STL-Algorithmen über den von uns erstellten Iteratortyp zu informieren.

In diesem Beispiel definiere ich einen Iterator mit wahlfreiem Zugriff und einen Iterator mit umgekehrtem wahlfreiem Zugriff:

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

Jetzt irgendwo in Ihrer benutzerdefinierten Containerklasse:

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
quelle
Ich denke, der Operator + und der Operator- können die Operationen rückwärts haben. Es sieht so aus, als würde Operator + die Bewegung von dem nicht addierenden Zeiger subtrahieren und der Operator wird sie addieren. Dies scheint rückwärts
Beached
Es ist für den umgekehrten Iterator, Operator + sollte rückwärts gehen und Operator- sollte vorwärts gehen
Enzo
2
Genial. Die akzeptierte Antwort ist zu hoch. Das ist fantastisch. Danke Enzo.
FernandoZ
Sie müssen Ihre Antwort bearbeiten. Angenommen, m_data wurde mit m_size-Elementen zugewiesen, erhalten Sie undefiniertes Verhalten: m_data[m_size]ist UB. Sie können es einfach beheben, indem Sie es durch ersetzen m_data+m_size. Bei Reverse-Iteratoren sind beide m_data[-1]und m_data-1falsch (UB). Um reverse_iterators zu reparieren, müssen Sie den "Zeiger auf den nächsten Elementtrick" verwenden.
Arnaud
Arnaud, ich habe gerade das Zeigerelement zur benutzerdefinierten Containerklasse hinzugefügt, das besser zeigt, was ich meinte.
Enzo
24

Sie vergessen oft, dass iteratordas konvertieren muss, const_iteratoraber nicht umgekehrt. Hier ist ein Weg, dies zu tun:

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

In der obigen Anmerkung, wie IntrusiveSlistIterator<T>konvertiert zu IntrusiveSlistIterator<T const>. Wenn dies Tbereits der Fall ist, wird constdiese Konvertierung nie verwendet.

Maxim Egorushkin
quelle
Sie können dies auch umgekehrt tun, indem Sie einen Kopierkonstruktor definieren, der eine Vorlage ist. Er wird nicht kompiliert, wenn Sie versuchen, den zugrunde liegenden Typ von constin nicht zu konvertieren const.
Matthieu M.
Wirst du nicht mit einem Invaliden enden IntrusiveSlistIterator<T const, void>::operator IntrusiveSlistIterator<T const, void>() const?
Potatoswatter
Ah, es ist gültig, aber Comeau warnt und ich vermute, dass es auch viele andere tun werden. Ein enable_ifkönnte es beheben, aber ...
Potatoswatter
Ich habe mich nicht mit enable_if beschäftigt, weil der Compiler es trotzdem deaktiviert, obwohl einige Compiler eine Warnung geben (g ++, ein guter Junge zu sein, warnt nicht).
Maxim Egorushkin
1
@Matthieu: Wenn man mit einem Vorlagenkonstruktor arbeitet, erzeugt der Compiler beim Konvertieren von const_iterator in einen Iterator einen Fehler im Konstruktor, der den Benutzer verwirrt und völlig wtf am Kopf kratzen lässt. Mit dem Konvertierungsoperator, den ich gepostet habe, sagt der Compiler nur, dass es keine geeignete Konvertierung von const_iterator zu Iterator gibt, was, IMO, klarer ist.
Maxim Egorushkin
23

Boost hat etwas zu helfen: die Boost.Iterator-Bibliothek.

Genauer gesagt diese Seite: boost :: iterator_adaptor .

Sehr interessant ist das Tutorial-Beispiel, das eine vollständige Implementierung eines benutzerdefinierten Typs von Grund auf zeigt.

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

Der Hauptpunkt ist, wie bereits erwähnt, die Verwendung einer einzelnen Vorlagenimplementierung und typedefdieser.

Matthieu M.
quelle
Können Sie die Bedeutung dieses Kommentars erklären? // a private type avoids misuse
Kevinarpe
@kevinarpe: enablerist niemals als Anbieter durch den Anrufer gedacht, daher vermute ich, dass sie es privat machen, um zu vermeiden, dass Leute versehentlich versuchen, es weiterzugeben. Ich glaube nicht, dass es ein Problem schaffen könnte, es tatsächlich zu bestehen, da der Schutz darin liegt enable_if.
Matthieu M.
16

Ich weiß nicht, ob Boost etwas hat, das helfen würde.

Mein bevorzugtes Muster ist einfach: Nehmen Sie ein Vorlagenargument value_type, das entweder const qualifiziert ist oder nicht. Bei Bedarf auch ein Knotentyp. Dann passt alles zusammen.

Denken Sie daran, alles zu parametrisieren (template-ize), was erforderlich ist, einschließlich des Kopierkonstruktors und operator==. Zum größten Teil erzeugt die Semantik von constkorrektes Verhalten.

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;
Kartoffelklatsche
quelle
Hinweis: Es sieht so aus, als ob Ihre Konvertierungen iterator-> const_iterator und back fehlerhaft sind.
Maxim Egorushkin
@Maxim: Ja, ich kann keine Beispiele für die Verwendung meiner Technik finden: vP. Ich bin mir nicht sicher, was Sie damit meinen, dass die Konvertierungen curfehlerhaft sind, da ich sie einfach nicht illustriert habe, aber es könnte ein Problem geben, auf das vom Iterator mit entgegengesetzter Konstanz zugegriffen wird. Die Lösung, die mir in den Sinn kommt, ist friend my_container::const_iterator; friend my_container::iterator;, aber ich glaube nicht, dass ich es vorher so gemacht habe ... trotzdem funktioniert diese allgemeine Gliederung.
Potatoswatter
1
* mach das friend classin beiden Fällen.
Potatoswatter
Es ist einige Zeit her, aber ich erinnere mich jetzt, dass die Konvertierungen (von SFINAE) auf der Form der zugrunde liegenden Elementinitialisierungen basieren sollten. Dies folgt dem SCARY-Muster (aber dieser Beitrag ist älter als diese Terminologie).
Potatoswatter
12

Es gibt viele gute Antworten, aber ich habe einen von mir verwendeten Vorlagen-Header erstellt , der sehr präzise und einfach zu verwenden ist.

Um Ihrer Klasse einen Iterator hinzuzufügen, muss nur eine kleine Klasse geschrieben werden, um den Status des Iterators mit 7 kleinen Funktionen darzustellen, von denen 2 optional sind:

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

Dann können Sie es so verwenden, wie Sie es von einem STL-Iterator erwarten würden:

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

Ich hoffe, es hilft.

VinGarcia
quelle
1
Diese Vorlagendatei hat alle meine Iteratorprobleme gelöst!
Perrykipkerrie