Richtlinien zu einer Iterator Klasse

Question

Ich habe eine rote Black Tree in C++ implementiert. Es unterstützt die Funktionalität einer STL-Map. Baumknoten enthalten Schlüssel und die zugeordneten Werte. Ich möchte eine Iterator-Klasse dafür schreiben, aber ich bin dabei, wie es geht. Soll ich eine innere Klasse der Tree-Klasse machen? Kann jemand mir einige Richtlinien geben, wie man es schreibt + einige Ressourcen?

Danke !!

Answer 1

Sicher, diese schönen Artikel lesen STL Iteratoren auf das Schreiben, es könnte Ihnen den nötigen Überblick:

http://www.drdobbs.com/184401417

Im Allgemeinen ja, eine innere Klasse ist gut, weil der Iterator Zugang muss Ihr implementierungsspezifische Baumknoten:

struct container { ... 
public: 
    struct iterator { 
    // these typedefs are needed if you want to be STL compatible 
    typedef std::forward_iterator_tag iterator_category; 
    typedef T   value_type; 
    typedef T*  pointer; 
    typedef T&  reference; 
    typedef size_t size_type; 
    typedef ptrdiff_t difference_type; 

    // the element points to your implementation node 
    iterator(element* init = 0) : current(init) {} 
    T& operator*() { return current->data; } // dereference 
    const T& operator*() const { return current->data; } 
    iterator& operator++() { // prefix 
     if (current) current = current->next; 
     return *this; 
    } 
    iterator operator++(int) { // postfix 
     iterator temp = *this; 
     ++*this; 
     return temp; 
    } 
    bool operator==(const iterator& x) const { return current == x.current; } 
    bool operator!=(const iterator& x) const { return current != x.current; } 

    private: 
    // the element points to your implementation node 
    element* current; 
    } 
    ... 

Die gute Sache hier ist, dass, während der Iterator öffentlich ist, das Element immer noch privat bleiben kann. Und ja, der obige Code ist auch STL-kompiliert!

Answer 2

Die Iterator-Klasse muss entweder eine geschachtelte Klasse oder mindestens eine typedef sein, die your_map::iterator mit einem anderen Typ typisiert. Eine verschachtelte Klasse ist normalerweise die sauberste/einfachste Route.

Was Ressourcen angeht, wäre eine mögliche Quelle der Hilfe die Boost::iterator Bibliothek, die Komponenten enthält, die Iteratoren leichter implementieren lassen.

Answer 3

Ich dachte, ich würde meinen eigenen kleinen Ratschlag hinzufügen.

Als erstes möchte ich bemerken, dass iterator und const_iterator sehr wahrscheinlich einen Großteil ihrer Implementierung gemeinsam haben. Obwohl der Code ähnlich ist, ist er nicht exakt identisch. Dies bittet um Vorlagen.

Die zweite Sache, die ich gerne beachten würde ist, dass eine const_iterator (iterator) (implizit) konstruierbar sein sollte, aber nicht umgekehrt.

Die dritte Sache, die ich gerne beachten möchte, ist, dass, wenn Sie eine map-ähnliche Schnittstelle haben möchten, dann müssen Sie auch eine reverse_iterator und const_reverse_iterator bereitstellen.

Aus der Sicht des Stils, tendiere ich nicht, die Implementierung der iterator selbst in der Klasse zu setzen. Ich finde es nicht lesbar, wenn die Klassenimplementierung mit so viel Code vollgestopft ist, dass man Mühe hat, die verfügbaren Typen und Methoden zu sehen. Aus diesem Grund würde ich empfehlen, die Implementierung außerhalb der Klasse zu platzieren.

Endlich, ich empfehle definitiv Boost.Iterator. Sie dürfen es nicht benutzen, aber lesen Sie das Material, es wird Ihnen vor allem Einblick geben, wie Sie den Code einmal schreiben und für die 4 Arten verwenden!

Schnell Illustration:

namespace detail { 
    template <class Value> class base_iterator; 
} 

template <class Value> 
class container 
{ 
public: 
    typedef detail::base_iterator<Value> iterator; 
    typedef detail::base_iterator<Value const> const_iterator; 

    typedef boost::reverse_iterator<iterator> reverse_iterator; 
    typedef boost::reverse_iterator<const_iterator> const_reverse_iterator; 
}; 

Ich weiß nicht, über Sie, aber ich fühle mich gut, wenn ich nur ein Viertel der Arbeit zu tun und nutzt einen Compiler/Bibliothek in den Rest für mich zu füllen :)