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

Question

Ich habe eine Sammlung, für die ich eine STL-Stil, zufälligen Zugriff Iterator bereitstellen möchten. Ich habe nach einer Beispielimplementierung eines Iterators gesucht, aber ich habe keine gefunden. Ich weiß um die Notwendigkeit von const-Überladungen von [] y * Betreiber. Welche Anforderungen muss ein Iterator erfüllen, um "STL-ähnlich" zu sein, und welche anderen Fallstricke gilt es zu vermeiden (falls vorhanden)?

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

Answer 1

En iterator_facade Dokumentation von Boost.Iterator bietet etwas, das wie ein nettes Tutorial zur Implementierung von Iteratoren für eine verknüpfte Liste aussieht. Könnten Sie das als Ausgangspunkt für den Aufbau eines Iterators mit wahlfreiem Zugriff über Ihren Container verwenden?

Zumindest können Sie einen Blick auf die Mitgliedsfunktionen und Typendefinitionen werfen, die von iterator_facade und verwenden Sie sie als Ausgangspunkt für den Aufbau Ihrer eigenen Website.

Answer 2

Hier ein Beispiel für einen rohen Zeiger-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; }

Umgehung der Schleife auf Basis des Rohzeigerbereichs. Bitte korrigieren Sie mich, wenn es einen besseren Weg, um Bereich basierte Schleife aus rohen Zeiger zu machen.

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

Answer 3

Thomas Becker schrieb einen nützlichen Artikel zu diesem Thema aquí .

Es gab auch diesen (vielleicht einfacheren) Ansatz, der zuvor in SO. erschien: Wie implementiert man korrekt benutzerdefinierte Iteratoren und const_iterators?

Answer 4

Zunächst einmal können Sie sich aquí für eine Liste der verschiedenen Operationen, die die einzelnen Iterator-Typen unterstützen müssen.

Wenn Sie nun Ihre Iterator-Klasse erstellt haben, müssen Sie entweder die std::iterator_traits für sie und stellen einige notwendige typedef s (wie iterator_category ou value_type ) oder leiten Sie es alternativ von std::iterator die die erforderlichen typedef s für Sie und kann daher mit dem Standard std::iterator_traits .

Haftungsausschluss: Ich weiß, dass einige Leute es nicht mögen cplusplus.com so viel, aber

Answer 5

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

Wie auch immer, ich habe mir EASTL . Abgesehen davon, dass ich eine Menge über Container gelernt habe, die ich nie gelernt habe, habe ich die ganze Zeit die stl Containern oder durch meine Studiengänge. Der Hauptgrund ist, dass EASTL ist besser lesbar als die stl Gegenstück (ich fand dies ist einfach wegen des Fehlens aller Makros und geradlinige Kodierung Stil). Es gibt einige unangenehme Dinge (wie #ifdefs für Ausnahmen), aber nichts, was Sie überwältigen könnte.

Wie bereits von anderen erwähnt, sollten Sie sich die Referenz von cplusplus.com zu Iteratoren und Containern ansehen.