Wie implementiert man einen Iterator im STL-Stil und vermeidet häufige Fallstricke?

Ich habe eine Sammlung erstellt, für die ich einen Iterator mit wahlfreiem Zugriff im STL-Stil bereitstellen möchte. Ich habe nach einer Beispielimplementierung eines Iterators gesucht, aber keine gefunden. Ich weiß um die Notwendigkeit von konstanten Überladungen von [] und * Betreiber. Was sind die Anforderungen für einen Iterator im „STL-Stil“ und welche anderen Fallstricke sind zu vermeiden (falls vorhanden)?

Zusätzlicher Kontext: Dies ist für eine Bibliothek und ich möchte keine Abhängigkeit davon einführen, es sei denn, ich muss es wirklich. Ich schreibe meine eigene Sammlung, um die Binärkompatibilität zwischen C++03 und C++11 mit demselben Compiler bereitzustellen (also keine STL, die wahrscheinlich kaputt gehen würde).

http://www.cplusplus.com/reference/std/iterator/ hat ein praktisches Diagramm, das die Spezifikationen von § 24.2.2 des C++11-Standards beschreibt. Grundsätzlich haben die Iteratoren Tags, die die gültigen Operationen beschreiben, und die Tags haben eine Hierarchie. Unten ist rein symbolisch, diese Klassen existieren eigentlich nicht als solche.

iterator {
    iterator(const iterator&);
    ~iterator();
    iterator& operator=(const iterator&);
    iterator& operator++(); //prefix increment
    reference operator*() const;
    friend void swap(iterator& lhs, iterator& rhs); //C++11 I think
};

input_iterator : public virtual iterator {
    iterator operator++(int); //postfix increment
    value_type operator*() const;
    pointer operator->() const;
    friend bool operator==(const iterator&, const iterator&);
    friend bool operator!=(const iterator&, const iterator&); 
};
//once an input iterator has been dereferenced, it is 
//undefined to dereference one before that.

output_iterator : public virtual iterator {
    reference operator*() const;
    iterator operator++(int); //postfix increment
};
//dereferences may only be on the left side of an assignment
//once an output iterator has been dereferenced, it is 
//undefined to dereference one before that.

forward_iterator : input_iterator, output_iterator {
    forward_iterator();
};
//multiple passes allowed

bidirectional_iterator : forward_iterator {
    iterator& operator--(); //prefix decrement
    iterator operator--(int); //postfix decrement
};

random_access_iterator : bidirectional_iterator {
    friend bool operator<(const iterator&, const iterator&);
    friend bool operator>(const iterator&, const iterator&);
    friend bool operator<=(const iterator&, const iterator&);
    friend bool operator>=(const iterator&, const iterator&);

    iterator& operator+=(size_type);
    friend iterator operator+(const iterator&, size_type);
    friend iterator operator+(size_type, const iterator&);
    iterator& operator-=(size_type);  
    friend iterator operator-(const iterator&, size_type);
    friend difference_type operator-(iterator, iterator);

    reference operator[](size_type) const;
};

contiguous_iterator : random_access_iterator { //C++17
}; //elements are stored contiguously in memory.

Sie können sich entweder spezialisieren std::iterator_traits<youriterator>oder fügen Sie dieselben Typedefs in den Iterator selbst ein oder erben Sie von std::iterator (die diese typedefs hat). Ich bevorzuge die zweite Option, um Änderungen in der zu vermeiden std Namespace und für die Lesbarkeit, aber die meisten Leute erben von std::iterator.

struct std::iterator_traits<youriterator> {        
    typedef ???? difference_type; //almost always ptrdiff_t
    typedef ???? value_type; //almost always T
    typedef ???? reference; //almost always T& or const T&
    typedef ???? pointer; //almost always T* or const T*
    typedef ???? iterator_category;  //usually std::forward_iterator_tag or similar
};

Beachten Sie, dass die iterator_category eine von sein sollte std::input_iterator_tag, std::output_iterator_tag, std::forward_iterator_tag, std::bidirectional_iterator_tagoder std::random_access_iterator_tag, je nachdem welche Anforderungen Ihr Iterator erfüllt. Abhängig von Ihrem Iterator können Sie sich spezialisieren std::next, std::prev, std::advanceund std::distance auch, aber das wird selten benötigt. Im sehr selten Fälle, in denen Sie sich spezialisieren möchten std::begin und std::end.

Ihr Container sollte wahrscheinlich auch eine haben const_iteratorder ein (möglicherweise veränderlicher) Iterator für konstante Daten ist, die Ihren ähnlich sind iterator außer es sollte implizit aus a konstruierbar sein iterator und Benutzer sollten nicht in der Lage sein, die Daten zu ändern. Es ist üblich, dass sein interner Zeiger ein Zeiger auf nicht konstante Daten ist und hat iterator geerbt von const_iterator um die Codeduplizierung zu minimieren.

Mein Beitrag zum Schreiben Ihres eigenen STL-Containers enthält einen vollständigeren Container-/Iterator-Prototyp.

Die iterator_facade-Dokumentation von Boost.Iterator bietet ein scheinbar nettes Tutorial zur Implementierung von Iteratoren für eine verknüpfte Liste. Könnten Sie das als Ausgangspunkt für die Erstellung eines Iterators mit wahlfreiem Zugriff über Ihren Container verwenden?

Wenn nichts anderes, können Sie sich die Member-Funktionen und Typedefs ansehen, die von bereitgestellt werden iterator_facade und verwenden Sie es als Ausgangspunkt für den Aufbau Ihrer eigenen.

Hier ist ein Beispiel für einen Rohzeiger-Iterator.

Sie sollten die Iterator-Klasse nicht verwenden, um mit rohen Zeigern zu arbeiten!

#include <iostream>
#include <vector>
#include <list>
#include <iterator>
#include <assert.h>

template<typename T>
class ptr_iterator
    : public std::iterator<std::forward_iterator_tag, T>
{
    typedef ptr_iterator<T>  iterator;
    pointer pos_;
public:
    ptr_iterator() : pos_(nullptr) {}
    ptr_iterator(T* v) : pos_(v) {}
    ~ptr_iterator() {}

    iterator  operator++(int) /* postfix */         { return pos_++; }
    iterator& operator++()    /* prefix */          { ++pos_; return *this; }
    reference operator* () const                    { return *pos_; }
    pointer   operator->() const                    { return pos_; }
    iterator  operator+ (difference_type v)   const { return pos_ + v; }
    bool      operator==(const iterator& rhs) const { return pos_ == rhs.pos_; }
    bool      operator!=(const iterator& rhs) const { return pos_ != rhs.pos_; }
};

template<typename T>
ptr_iterator<T> begin(T *val) { return ptr_iterator<T>(val); }


template<typename T, typename Tsize>
ptr_iterator<T> end(T *val, Tsize size) { return ptr_iterator<T>(val) + size; }

Problemumgehung für eine auf dem Rohzeigerbereich basierende Schleife. Bitte korrigieren Sie mich, wenn es einen besseren Weg gibt, eine bereichsbasierte Schleife aus einem Rohzeiger zu erstellen.

template<typename T>
class ptr_range
{
    T* begin_;
    T* end_;
public:
    ptr_range(T* ptr, size_t length) : begin_(ptr), end_(ptr + length) { assert(begin_ <= end_); }
    T* begin() const { return begin_; }
    T* end() const { return end_; }
};

template<typename T>
ptr_range<T> range(T* ptr, size_t length) { return ptr_range<T>(ptr, length); }

Und einfacher Test

void DoIteratorTest()
{
    const static size_t size = 10;
    uint8_t *data = new uint8_t[size];
    {
        // Only for iterator test
        uint8_t n = '0';
        auto first = begin(data);
        auto last = end(data, size);
        for (auto it = first; it != last; ++it)
        {
            *it = n++;
        }

        // It's prefer to use the following way:
        for (const auto& n : range(data, size))
        {
            std::cout << " char: " << static_cast<char>(n) << std::endl;
        }
    }
    {
        // Only for iterator test
        ptr_iterator<uint8_t> first(data);
        ptr_iterator<uint8_t> last(first + size);
        std::vector<uint8_t> v1(first, last);

        // It's prefer to use the following way:
        std::vector<uint8_t> v2(data, data + size);
    }
    {
        std::list<std::vector<uint8_t>> queue_;
        queue_.emplace_back(begin(data), end(data, size));
        queue_.emplace_back(data, data + size);
    }
}

Thomas Becker hat einen nützlichen Artikel zu diesem Thema geschrieben Hier.

Es gab auch diesen (vielleicht einfacheren) Ansatz, der zuvor auf SO erschienen ist: Wie implementiert man benutzerdefinierte Iteratoren und const_iterators korrekt?

Erstmal kann man schauen Hier für eine Liste der verschiedenen Operationen, die die einzelnen Iteratortypen unterstützen müssen.

Als nächstes, wenn Sie Ihre Iteratorklasse erstellt haben, müssen Sie sich entweder spezialisieren std::iterator_traits dafür und stellen einige notwendige bereit typedefs (wie iterator_category oder value_type) oder alternativ davon ableiten std::iteratordie das Erforderliche definiert typedefs für Sie und kann daher mit der Voreinstellung verwendet werden std::iterator_traits.

Haftungsausschluss: Ich weiß, dass manche Leute es nicht mögen cplusplus.com so viel, aber sie bieten einige wirklich nützliche Informationen dazu.

Ich war/bin aus unterschiedlichen Gründen (teils erzieherisch, teils Zwänge) im selben Boot wie du. Ich musste alle Container der Standardbibliothek neu schreiben und die Container mussten dem Standard entsprechen. Das heißt, wenn ich meinen Container mit dem tausche stl Version, würde der Code gleich funktionieren. Das bedeutete auch, dass ich die Iteratoren neu schreiben musste.

Jedenfalls habe ich nachgeschaut OST. Abgesehen davon, dass ich eine Menge über Container gelernt habe, die ich die ganze Zeit über nie gelernt habe stl Container oder über meine Bachelor-Studiengänge. Der Hauptgrund ist das OST ist besser lesbar als die stl Gegenstück (ich fand, dass dies einfach am Fehlen aller Makros und des einfachen Codierungsstils liegt). Es gibt einige eklige Dinge darin (wie #ifdefs für Ausnahmen), aber nichts, was Sie überwältigen könnte.

Sehen Sie sich, wie bereits erwähnt, die Referenz von cplusplus.com zu Iteratoren und Containern an.

Ich habe versucht, das Problem zu lösen, mehrere verschiedene Textarrays durchlaufen zu können, die alle in einer großen speicherresidenten Datenbank gespeichert sind struct.

Folgendes wurde mit Visual Studio 2017 Community Edition auf einer MFC-Testanwendung ausgearbeitet. Ich füge dies als Beispiel hinzu, da dieser Beitrag einer von mehreren war, auf die ich stieß, die etwas Hilfe boten, aber immer noch nicht für meine Bedürfnisse ausreichten.

Die struct mit den speicherresidenten Daten sah etwa wie folgt aus. Ich habe die meisten Elemente der Kürze halber entfernt und auch die verwendeten Präprozessordefinitionen nicht aufgenommen (das verwendete SDK ist sowohl für C als auch für C++ und ist alt).

Was mich interessierte, war, Iteratoren für die verschiedenen zu haben WCHAR zweidimensionale Arrays, die Textzeichenfolgen für mnemonische Zeichen enthielten.

typedef struct  tagUNINTRAM {
    // stuff deleted ...
    WCHAR   ParaTransMnemo[MAX_TRANSM_NO][PARA_TRANSMNEMO_LEN]; /* prog #20 */
    WCHAR   ParaLeadThru[MAX_LEAD_NO][PARA_LEADTHRU_LEN];   /* prog #21 */
    WCHAR   ParaReportName[MAX_REPO_NO][PARA_REPORTNAME_LEN];   /* prog #22 */
    WCHAR   ParaSpeMnemo[MAX_SPEM_NO][PARA_SPEMNEMO_LEN];   /* prog #23 */
    WCHAR   ParaPCIF[MAX_PCIF_SIZE];            /* prog #39 */
    WCHAR   ParaAdjMnemo[MAX_ADJM_NO][PARA_ADJMNEMO_LEN];   /* prog #46 */
    WCHAR   ParaPrtModi[MAX_PRTMODI_NO][PARA_PRTMODI_LEN];  /* prog #47 */
    WCHAR   ParaMajorDEPT[MAX_MDEPT_NO][PARA_MAJORDEPT_LEN];    /* prog #48 */
    //  ... stuff deleted
} UNINIRAM;

Der aktuelle Ansatz besteht darin, eine Vorlage zu verwenden, um eine Proxy-Klasse für jedes der Arrays zu definieren, und dann eine einzelne Iteratorklasse zu haben, die verwendet werden kann, um über ein bestimmtes Array zu iterieren, indem ein Proxy-Objekt verwendet wird, das das Array darstellt.

Eine Kopie der speicherresidenten Daten wird in einem Objekt gespeichert, das das Lesen und Schreiben der speicherresidenten Daten von/auf die Platte handhabt. Diese Klasse, CFilePara enthält die auf Vorlagen basierende Proxy-Klasse (MnemonicIteratorDimSize und die Unterklasse, von der es abgeleitet ist, MnemonicIteratorDimSizeBase) und die Iteratorklasse, MnemonicIterator.

Das erzeugte Proxy-Objekt wird an ein Iterator-Objekt angehängt, das auf die notwendigen Informationen über eine Schnittstelle zugreift, die durch eine Basisklasse beschrieben wird, von der alle Proxy-Klassen abgeleitet sind. Das Ergebnis besteht darin, einen einzigen Iteratorklassentyp zu haben, der mit mehreren unterschiedlichen Proxy-Klassen verwendet werden kann, da die unterschiedlichen Proxy-Klassen alle dieselbe Schnittstelle, die Schnittstelle der Proxy-Basisklasse, offen legen.

Als Erstes musste ein Satz von Identifikatoren erstellt werden, die einer Klassenfabrik bereitgestellt wurden, um das spezifische Proxy-Objekt für diese Art von Mnemonik zu generieren. Diese Identifikatoren werden als Teil der Benutzerschnittstelle verwendet, um die bestimmten Bereitstellungsdaten zu identifizieren, die der Benutzer sehen und möglicherweise modifizieren möchte.

const static DWORD_PTR dwId_TransactionMnemonic = 1;
const static DWORD_PTR dwId_ReportMnemonic = 2;
const static DWORD_PTR dwId_SpecialMnemonic = 3;
const static DWORD_PTR dwId_LeadThroughMnemonic = 4;

Die Proxy-Klasse

Die Vorlagen-Proxy-Klasse und ihre Basisklasse sind wie folgt. Ich musste mehrere verschiedene Arten von unterbringen wchar_t Text-String-Arrays. Die zweidimensionalen Arrays hatten je nach Art (Zweck) der Mnemonik unterschiedliche Anzahlen von Mnemoniken, und die verschiedenen Arten von Mnemoniken hatten unterschiedliche maximale Längen, die zwischen fünf Textzeichen und zwanzig Textzeichen variierten. Vorlagen für die abgeleitete Proxy-Klasse passten natürlich zu der Vorlage, die die maximale Anzahl von Zeichen in jeder Mnemonik erforderte. Nachdem das Proxy-Objekt erstellt wurde, verwenden wir dann die SetRange() -Methode, um das eigentliche mnemonische Array und seinen Bereich anzugeben.

// proxy object which represents a particular subsection of the
// memory resident database each of which is an array of wchar_t
// text arrays though the number of array elements may vary.
class MnemonicIteratorDimSizeBase
{
    DWORD_PTR  m_Type;

public:
    MnemonicIteratorDimSizeBase(DWORD_PTR x) { }
    virtual ~MnemonicIteratorDimSizeBase() { }

    virtual wchar_t *begin() = 0;
    virtual wchar_t *end() = 0;
    virtual wchar_t *get(int i) = 0;
    virtual int ItemSize() = 0;
    virtual int ItemCount() = 0;

    virtual DWORD_PTR ItemType() { return m_Type; }
};

template <size_t sDimSize>
class MnemonicIteratorDimSize : public MnemonicIteratorDimSizeBase
{
    wchar_t    (*m_begin)[sDimSize];
    wchar_t    (*m_end)[sDimSize];

public:
    MnemonicIteratorDimSize(DWORD_PTR x) : MnemonicIteratorDimSizeBase(x), m_begin(0), m_end(0) { }
    virtual ~MnemonicIteratorDimSize() { }

    virtual wchar_t *begin() { return m_begin[0]; }
    virtual wchar_t *end() { return m_end[0]; }
    virtual wchar_t *get(int i) { return m_begin[i]; }

    virtual int ItemSize() { return sDimSize; }
    virtual int ItemCount() { return m_end - m_begin; }

    void SetRange(wchar_t (*begin)[sDimSize], wchar_t (*end)[sDimSize]) {
        m_begin = begin; m_end = end;
    }

};

Die Iterator-Klasse

Die Iterator-Klasse selbst ist wie folgt. Diese Klasse bietet nur grundlegende Vorwärts-Iterator-Funktionalität, die zu diesem Zeitpunkt alles ist, was benötigt wird. Ich gehe jedoch davon aus, dass sich dies ändern oder erweitern wird, wenn ich etwas Zusätzliches davon benötige.

class MnemonicIterator
{
private:
    MnemonicIteratorDimSizeBase   *m_p;  // we do not own this pointer. we just use it to access current item.
    int      m_index;                    // zero based index of item.
    wchar_t  *m_item;                    // value to be returned.

public:
    MnemonicIterator(MnemonicIteratorDimSizeBase *p) : m_p(p) { }
    ~MnemonicIterator() { }

    // a ranged for needs begin() and end() to determine the range.
    // the range is up to but not including what end() returns.
    MnemonicIterator & begin() { m_item = m_p->get(m_index = 0); return *this; }                 // begining of range of values for ranged for. first item
    MnemonicIterator & end() { m_item = m_p->get(m_index = m_p->ItemCount()); return *this; }    // end of range of values for ranged for. item after last item.
    MnemonicIterator & operator ++ () { m_item = m_p->get(++m_index); return *this; }            // prefix increment, ++p
    MnemonicIterator & operator ++ (int i) { m_item = m_p->get(m_index++); return *this; }       // postfix increment, p++
    bool operator != (MnemonicIterator &p) { return **this != *p; }                              // minimum logical operator is not equal to
    wchar_t * operator *() const { return m_item; }                                              // dereference iterator to get what is pointed to
};

Die Proxy-Objekt-Fabrik bestimmt, welches Objekt basierend auf der mnemonischen Kennung erstellt werden soll. Das Proxy-Objekt wird erzeugt und der zurückgegebene Zeiger ist der Standard-Basisklassentyp, um eine einheitliche Schnittstelle zu haben, unabhängig davon, auf welche der verschiedenen mnemonischen Abschnitte zugegriffen wird. Die SetRange() -Methode wird verwendet, um dem Proxy-Objekt die spezifischen Array-Elemente, die der Proxy darstellt, und den Bereich der Array-Elemente anzugeben.

CFilePara::MnemonicIteratorDimSizeBase * CFilePara::MakeIterator(DWORD_PTR x)
{
    CFilePara::MnemonicIteratorDimSizeBase  *mi = nullptr;

    switch (x) {
    case dwId_TransactionMnemonic:
        {
            CFilePara::MnemonicIteratorDimSize<PARA_TRANSMNEMO_LEN> *mk = new CFilePara::MnemonicIteratorDimSize<PARA_TRANSMNEMO_LEN>(x);
            mk->SetRange(&m_Para.ParaTransMnemo[0], &m_Para.ParaTransMnemo[MAX_TRANSM_NO]);
            mi = mk;
        }
        break;
    case dwId_ReportMnemonic:
        {
            CFilePara::MnemonicIteratorDimSize<PARA_REPORTNAME_LEN> *mk = new CFilePara::MnemonicIteratorDimSize<PARA_REPORTNAME_LEN>(x);
            mk->SetRange(&m_Para.ParaReportName[0], &m_Para.ParaReportName[MAX_REPO_NO]);
            mi = mk;
        }
        break;
    case dwId_SpecialMnemonic:
        {
            CFilePara::MnemonicIteratorDimSize<PARA_SPEMNEMO_LEN> *mk = new CFilePara::MnemonicIteratorDimSize<PARA_SPEMNEMO_LEN>(x);
            mk->SetRange(&m_Para.ParaSpeMnemo[0], &m_Para.ParaSpeMnemo[MAX_SPEM_NO]);
            mi = mk;
        }
        break;
    case dwId_LeadThroughMnemonic:
        {
            CFilePara::MnemonicIteratorDimSize<PARA_LEADTHRU_LEN> *mk = new CFilePara::MnemonicIteratorDimSize<PARA_LEADTHRU_LEN>(x);
            mk->SetRange(&m_Para.ParaLeadThru[0], &m_Para.ParaLeadThru[MAX_LEAD_NO]);
            mi = mk;
        }
        break;
    }

    return mi;
}

Verwenden der Proxy-Klasse und des Iterators

Die Proxy-Klasse und ihr Iterator werden wie in der folgenden Schleife gezeigt verwendet, um a auszufüllen CListCtrl Objekt mit einer Liste von Mnemoniken. ich benutze std::unique_ptr damit wenn ich die Proxy-Klasse nicht mehr brauche und die std::unique_ptr den Gültigkeitsbereich verlässt, wird der Speicher bereinigt.

Dieser Quellcode erstellt ein Proxy-Objekt für das Array innerhalb der struct die der angegebenen mnemonischen Kennung entspricht. Es erstellt dann einen Iterator für dieses Objekt und verwendet einen Bereich for zum ausfüllen CListCtrl kontrollieren und dann aufräumen. Diese sind alle roh wchar_t Textstrings, die genau die Anzahl der Array-Elemente sein können, also kopieren wir den String in einen temporären Puffer, um sicherzustellen, dass der Text nullterminiert ist.

    std::unique_ptr<CFilePara::MnemonicIteratorDimSizeBase> pObj(pFile->MakeIterator(m_IteratorType));
    CFilePara::MnemonicIterator pIter(pObj.get());  // provide the raw pointer to the iterator who doesn't own it.

    int i = 0;    // CListCtrl index for zero based position to insert mnemonic.
    for (auto x : pIter)
    {
        WCHAR szText[32] = { 0 };     // Temporary buffer.

        wcsncpy_s(szText, 32, x, pObj->ItemSize());
        m_mnemonicList.InsertItem(i, szText);  i++;
    }