Wie das Iterieren über ein std :: set sortierte Ergebnisse liefert

Question

Der Container std :: set (oder std :: map) ist eine Datenstruktur, die STL bereitstellt. In fast allen Compilern ist es als ein R & B-Baum mit garantierter log (n) -Einfügung, Such- und Entfernungszeit implementiert.

https://en.wikipedia.org/wiki/Red%E2%80%93black_tree

in einem roten und schwarzen Baum werden die Elemente auf der Basis des „weniger“ Operator des gespeicherten Elements sortiert. Also, im Grunde, wenn eine Wurzel N + 1 ist, wird N auf dem linken Unterbaum sein, während N + 2 auf dem rechten Unterbaum sein wird und diese Ordnung wird durch den weniger Operator entschieden werden.

Meine Frage ist, wenn Sie den folgenden Code ausführen:

set<unsigned long>::iterator it; 
for (it = myset.begin(); it != myset.end(); it++) { 
    cout << *it; 
} 

die Elemente in einer sortierten Reihenfolge zurückgegeben werden. Wie kann dies angesichts der Tatsache, dass die zugrunde liegende Datenstruktur ein rot-schwarzer Baum ist, möglich sein? Gibt es eine separate verknüpfte Liste, die gespeichert werden kann, um vom äußersten linken Teilbaum zum am weitesten rechts liegenden Teilbaum zu iterieren? Wenn nicht, was ist der Mechanismus hinter dieser Implementierung unter Verwendung eines R & B-Baumes?

Answer 1

Wir können eine endgültige Antwort finden, indem wir uns den Quellcode ansehen (in diesem Fall libstdC++ 5.2.1). Dies ist, wie ein Baumknoten wie folgt aussieht:

// <libstdc++>/include/bits/stl_tree.h 
struct _Rb_tree_node_base { 
    typedef _Rb_tree_node_base* _Base_ptr; 

    _Rb_tree_color _M_color; 
    _Base_ptr  _M_parent; 
    _Base_ptr  _M_left; 
    _Base_ptr  _M_right; 

    // ... 
} 

So jeder Knoten eine Farbe enthält, und Zeiger auf seine Eltern und seinen linken und rechten Kinder. Incrementieren implementiert als:

// <libstdc++>/include/bits/stl_tree.h 
struct _Rb_tree_iterator { 
    _Self& operator++() { 
    _M_node = _Rb_tree_increment(_M_node); 
    return *this; 
    } 

// ... 

private: 
    _Base_ptr _M_node; 
}; 

Der tatsächliche Zuwachs ist nicht in den öffentlichen Header mehr, aber in dem kompilierten Teil der Bibliothek:

// <libstdc++>/src/c++98/tree.cc 
static _Rb_tree_node_base* local_Rb_tree_increment(_Rb_tree_node_base* __x) throw() 
{ 
    if (__x->_M_right != 0) { 
     __x = __x->_M_right; 
     while (__x->_M_left != 0) 
      __x = __x->_M_left; 
    } else { 
     _Rb_tree_node_base* __y = __x->_M_parent; 
     while (__x == __y->_M_right) { 
      __x = __y; 
      __y = __y->_M_parent; 
     } 
     if (__x->_M_right != __y) 
      __x = __y; 
    } 
    return __x; 
} 

Also, schließlich ist es ein Lehrbuch Implementierung von Baumdurchlauf : Der Iterator hält einen Zeiger auf den "aktuellen" Knoten, und um zum nächsten Knoten zu gelangen, geht er in den Baum hinein, solange er vom rechten Kind kommt. Wenn es vom linken Kind kommt, wird es zum ganz linken Kindknoten des rechten Kindes absteigen.

Answer 2

Der Iterator führt eine [In-Order-Depth-First-Tree-Traversierung] durch. 1 Dies wird normalerweise in einem rekursiven Algorithmus implementiert. Da die Iterator-Verwendung nicht rekursiv implementiert werden kann, behält der Iterator intern einen Stapel von dem, wo er gewesen ist, so dass er wieder in den Baum gehen kann.

Update: Danke an Chris Dodd für den Hinweis, dass RB-Tree-Knoten Zeiger auf ihre Eltern haben, so dass der Iterator ihnen einfach bis zum nächsten Element folgen kann.