noch eine STL-Baum-Frage

Question

eine ziemlich lustige Frage, die ich habe.

Ich arbeite jetzt an der HTML-Parser und ich verwendete Vektor für alle meine Eingabe Zwecke, die ziemlich gut und schnell für die Erstellung von Baum schien.

In einer anderen Anwendung muss ich HTML-Struktur bearbeiten und jetzt Einfügen oder Neuanordnen der Elemente wäre sehr schmerzhaft mit Vektor, so dass ich beschloss, zu mehr Baum-ähnliche Struktur zu wechseln.

Ich las ein paar Artikel über Bäume und ihre Umsetzung und ich dachte für diesen Zweck an std :: map.

Etwas wie folgt aus:

std::map< element, *child_map >

Also, wenn ich dachte an einen Tag irgendwo dazwischen eingefügt und mit ihnen alle von einigen Schlüssel bestellt (zB eindeutige Ganzzahl-ID) Ich habe immer noch ein Problem, alles zu aktualisieren Schlüssel in einem Zweig nach dem Einfügen.

zum Beispiel: 1: SCRIPT 2: HEAD 3: BODY

Wenn ich will nach dem HEAD neues Element "SCRIPT" einfügen Ich muss Körper Key bis 4 und haben smth so erhöhen, : 1: SCRIPT 2: HEAD 3: SCRIPT 4: BODY

etwas umständlich zu mir zu sein scheint. Vermisse ich etwas?

Als Alternative habe ich stattdessen list<pair<>> Umsetzung gedacht. Daher wird die Sortierung nicht durch einen Schlüssel bestimmt und ich kann Elemente überall ohne zusätzliche Aktualisierungen hinzufügen.

Answer 1

Ich würde das Kind machen ein Mitglied des Elements gesetzt und verwenden std :: list:

class Element { 
/* ... */ 
    std::list<boost::shared_ptr<Element> > children; 
/* ... */ 
}; 

Das heißt, Sie eine vorhandene DOM-Bibliothek in anstelle Ihrer eigenen Walz aussehen wollen könnte. Zum Beispiel könnten Sie htmlcxx verwenden.

Answer 2

Liste < Paare> würde gut jede Form der Baumstruktur zu simulieren, wie, was Sie versuchen zu tun: eine beliebige Anzahl von

Liste < Paar < „html“, Liste> würden Sie speichern Kinder sowie steuern die Reihenfolge der Objekte in der Child-Liste.

Viel Spaß beim Gehen diesen Baum.