encore une autre question de l'arbre STL

Question

assez une question drôle que j'ai.

Je travaille maintenant sur l'analyseur HTML et j'utilisais le vecteur pour toutes mes fins d'entrée qui semblait assez fin et rapide pour la création d'arborescence.

Dans une autre application, j'ai besoin d'éditer la structure HTML et maintenant l'insertion ou la réorganisation des éléments serait extrêmement douloureuse en utilisant le vecteur, j'ai donc décidé de passer à une structure plus arborescente.

J'ai lu quelques articles sur les arbres et leur implémentation et je pensais à std :: map dans ce but.

Quelque chose comme ceci:

std::map< element, *child_map >

Alors, quand je pensais à insérer une étiquette quelque part entre les deux et les avoir tous commandés par une clé (par exemple id entier unique) Il me reste un problème de mettre à jour tous les clés dans une branche après l'insertion.

par exemple: 1: SCRIPT 2: TETE 3: CORPS

Quand je veux insérer nouvel élément « SCRIPT » après la tête, j'incrémentiez clé du corps à 4 et ont smth comme celui-ci : 1: SCRIPT 2: HEAD 3: SCRIPT 4: CORPS

semble un peu encombrant pour moi. Est-ce que je manque smth? En guise d'alternative, je pensais plutôt à faire l'implémentation list<pair<>> à la place. Le tri n'est donc pas déterminé par une clé et je peux ajouter des éléments n'importe où sans mise à jour supplémentaire.

Answer 1

Je voudrais faire l'enfant a fixé un membre de l'élément et utiliser std :: liste:

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

Cela dit, vous voudrez peut-être regarder dans une bibliothèque DOM existant au lieu de rouler vos propres. Par exemple, vous pouvez utiliser htmlcxx.

Answer 2

Liste < paire> fonctionnerait bien pour simuler toute forme de structure arborescente, comme ce que vous essayez de faire:

liste < paire < « html », liste> vous permettrait de stocker un nombre arbitraire de enfants ainsi que de contrôler l'ordre des objets dans la liste des enfants.

Amusez-vous à marcher dans cet arbre.