Come iterating su un oggetto std :: set restituisce risultati ordinati

Question

Il contenitore std :: set (o std :: map) è una struttura dati fornita da STL. In quasi tutti i compilatori è implementato come albero R & B con un registro (n) garantito, il tempo di ricerca e di rimozione.

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

In un albero rosso e nero gli elementi sono ordinati in base all'operatore "meno" dell'elemento memorizzato. Quindi in pratica se una radice è N + 1, N sarà nella sottoalbero di sinistra mentre N + 2 sarà nella sottostruttura di destra e questo ordine sarà deciso dal meno operatore.

La mia domanda è quando si esegue il codice qui sotto:

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

gli elementi vengono restituiti in un modo ordinato. Come può essere possibile considerando il fatto che la struttura dati sottostante è un albero rosso e nero? Esiste una lista collegata separata memorizzata per poter iterare dal sub-albero più a sinistra al sotto-albero più a destra? In caso contrario, qual è il meccanismo alla base di questa implementazione utilizzando un albero B R &?

Answer 1

Possiamo trovare una risposta definitiva guardando il codice sorgente (libstdC++ 5.2.1 in questo caso). Questo è come un nodo della struttura si presenta come:

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

    // ... 
} 

Così ogni nodo contiene un colore, e puntatori a sua madre e le sue figli sinistro e destro. Incremento viene implementato come:

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

L'incremento reale non è nelle intestazioni pubblici più, ma nella parte compilata della biblioteca:

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

Quindi, in definitiva, si tratta di un'implementazione manuale di albero di attraversamento : L'iteratore mantiene un puntatore al nodo "corrente" e per raggiungere il nodo successivo sale nell'albero fintantoché arriva dal bambino giusto. Se proveniva dal figlio sinistro, discenderebbe fino al nodo figlio più a sinistra del figlio destro.

Answer 2

L'iteratore esegue un [traversamento in profondità dell'albero in profondità]. 1 In genere viene implementato in un algoritmo ricorsivo. Poiché l'uso dell'iteratore non può essere implementato in modo ricorsivo, l'iteratore mantiene una pila di dove è stato in modo che possa risalire l'albero.

Aggiornamento: grazie a Chris Dodd per aver sottolineato che i nodi RB hanno i puntatori ai loro genitori, quindi l'iteratore può semplicemente seguirli fino all'elemento successivo.