Esiste un contenitore stl per i dati del modello gerarchico?

Question

Per un livello di modello indipendente dalla piattaforma, non ho dati gerarchici (stringhe, in realtà) che assomigliano a questo:

• Voce A
  • SubItem Un
  • SubItem B
  • SubItem C
    • SubSubItem A
    • SubSubItem B
  • SubItem D
• Voce B
• Voce C

Ora, all'interno di ogni "livello" (voce, SubItem, sottosottovoce, etc.) gli oggetti devono essere in ordine alfabetico.

Sembra una soluzione semplice creare una classe semplice con uno std :: Vector o std :: MultiMap ordinato per tracciare i suoi figli e un puntatore al suo padre. (e un oggetto radice). Avrei bisogno di scorrere in generale i bambini di ciascun articolo in una direzione futura.

Dopo la costruzione/l'ordinamento, non è necessario aggiungere o eliminare elementi. Generalmente un piccolo numero di articoli (centinaia).

Questo è per l'organizzazione del modello dei dati di supporto di un controllo in stile contorno.

Il rolling di una classe semplice sarebbe facile, ma questo è un modello molto comune - non esiste già un contenitore STL già pronto con questo comportamento?

Answer 1

Nessuna disposizione del STL per sé, ma si potrebbe trovare questo utile:

tree.hh: an STL-like C++ tree class

sue API segue contenitori STL esattamente, e dovrebbe fare quello che stai cercando.

Credo che their example sia esattamente quello che stai chiedendo (un albero con le stringhe), infatti.

Answer 2

No. Non intendo essere brusco, ma questa è la risposta; vedere per es. Josuttis o lo standard. Dovrai creare una classe con indicatori genitore/figlio lungo le linee da te suggerite e utilizzare un vettore o un altro contenitore standard di questi.

Answer 3

La risposta alla tua domanda è no, non ci sono alberi nell'STL. I modelli che hai suggerito vanno bene. Vedi anche this question.

Answer 4

Una soluzione semplice:

Le chiavi sono std::vector<GUID>, dove il GUID è qualche tipo (forse un GUID, o un puntatore, o una stringa) che identifica univocamente ogni elemento. I figli di un elemento hanno semplicemente gli elementi std::vector<GUID> come "prefisso".

Fintanto che il tuo GUID è ordinabile tramite operator<, l'ordinamento lessografico su std::vector otterrà le cose nell'ordine richiesto.

A map<std::vector<GUID>, Value> potrebbe essere il vostro contenitore o uno std::vector< std::pair< GUID, Value > > che ordinate per .first manualmente.

Se il tipo di GUID può avere un "ultimo elemento", è possibile trovare ogni figlio di {x,y,z} trovando lower_bound di {x,y,z} e upper_bound di {x,y,z,last_guid}. Dandogli un "ultimo elemento" è un vantaggio non usare un puntatore nudo.