Utilizzo dell'implementazione interna di albero rosso-nero di STL

Question

Capisco che il mio STL (che viene fornito con g ++ 4.x.x) utilizza alberi rosso-nero per implementare contenitori come la mappa. È possibile utilizzare direttamente l'albero rosso-nero interno dell'STL. Se é cosi, come? In caso contrario, perché no? Perché STL non espone l'albero rosso-nero?

Sorprendentemente, non riesco a trovare una risposta utilizzando google.

Edit: Sto indagando utilizzando l'albero rosso-nero come una soluzione per la chiamata al costruttore allocatore in più su di inserimento. Vedi this question. Il mio STL utilizza alberi rosso-neri per l'implementazione della mappa.

Answer 1

In realtà, la risposta è molto semplice e indipendente dalla versione di gcc. È possibile scaricare il codice sorgente di stl da sgi's website e vedere l'implementazione e utilizzarla personalmente.

Ad esempio, nella versione 3.2, è possibile vedere l'implementazione dell'albero rosso-nero nel file stl_tree.h e un esempio del suo utilizzo in stl_set.h.

Nota che, poiché le classi STL sono classi template, le implementazioni sono in realtà all'interno dei file di intestazione.

Answer 2

maggior parte delle implementazioni STL di set e map sono rosse alberi neri credo, anche se niente è fermare qualcuno da implementare utilizzando una struttura dati diversa - se non ricordo male, lo standard C++ non richiede un'implementazione albero RB.

Il STL non lo espone in quanto ciò violerebbe i principi OOP .. esporre la struttura dei dati sottostante potrebbe portare a comportamenti indesiderati se qualcun altro dovesse utilizzare la libreria. Vale a dire, in particolare per set e map, si dovrebbe consentire solo l'accesso a metodi conformi alle strutture di dati set e map. Esporre la rappresentazione sottostante potrebbe forse indurre un utente ad avere duplicati all'interno di set, il che è negativo.

Detto questo, non c'è modo (a mia conoscenza) di utilizzare direttamente il rosso albero nero di fondo .. sarebbe dipendono molto da come si vorrebbe usarlo. Molto probabilmente l'implementazione del tuo albero rosso-nero è la soluzione migliore oppure controlla le nostre librerie di terze parti (forse Boost?)

Answer 3

Non ti viene nemmeno data la garanzia che la struttura dati utilizzata sarà da a rosso- albero nero (ad esempio, è stato implementato almeno una volta come albero AVL, e qualcosa come B, B * o albero B + probabilmente andrebbe bene).

Come tale, l'unico modo per ottenere gli interni sarebbe di guardare a un'implementazione specifica, e fare uso di cose che non (almeno provare) a esporre pubblicamente.

Per quanto riguarda il motivo per cui: penso soprattutto perché è un tentativo di astrazione, non esporre tutti i dettagli di implementazione.