yet another STL tree question

Question

Hello everyone,

quite a funny question I have.

I am working now on the HTML parser and I was using vector for all my input purposes which seemed quite fine and fast for creating tree.

In another application I need to edit HTML structure and now inserting or reordering of the elements would be extremely painful using vector so I decided to switch to more tree-like structure.

I read a few articles on trees and their implementation and I was thinking of std::map for this purpose.

Something like this:

std::map< element, *child_map >

So when I thought of inserting a tag somewhere in between and having them all ordered by some key (e.g. unique integer id) I still have a problem to update all keys in a branch after insertion.

for example: 1:SCRIPT 2:HEAD 3:BODY

When I want to insert new element "SCRIPT" after the HEAD I will need to increment Body Key to 4 and have smth like this: 1:SCRIPT 2:HEAD 3:SCRIPT 4:BODY

Seems a bit cumbersome to me. Am I missing smth?

As an alternative I thought of doing list<pair<>> implementation instead. Thus sorting is not determined by a key and I can add elements anywhere without any extra updates.

Answer 1

List< pair > would work well to simulate any form of tree structure such as what you're trying to do:

list< pair< "html", list > would let you store an arbitrary number of children as well as control the order of objects in the child list.

Have fun walking this tree.

Answer 2

I would make the child set a member of the element and use std::list:

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

That said, you might want to look into using an existing DOM library instead of rolling your own. For example, you could use htmlcxx.