Is there a stl container for hierarchical model data?

Question

For a platform-independent model level, I have hierarchical data (rows, actually) that look like this:

• Point a
  • SubItem A
  • SubItem B
  • SubItem C
    • SubSubItem A
    • SubSubItem B
  • SubItem D
• Point B
• Point C

Now, in each "level" (Item, SubItem, SubSubItem, etc.), the elements must be sorted in alphabetical order.

It seems like a simple solution would be to create a simple class with a sorted std :: Vector or std :: MultiMap to track its children and a pointer to its parent element. (and one root element). I would need, in general, to go through every detail of the children in the forward direction.

After creating / sorting, I don't need to add or remove elements. Usually a small number of items (hundreds).

This is for organizing a data model of a backup of a control in style.

Slipping a simple class would be easy, but this is such a common pattern - are there any ready-made STL containers with this behavior?

Answer 1

Nothing in STL, but you may find this useful:

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

Its API follows STL containers exactly, and it should do what you are looking for.

I believe that their example is exactly what you are asking about (tree with lines).

Answer 2

A simple solution:

Your keys are std::vector<GUID> , where the GUID is some type (possibly a GUID or a pointer or string) that uniquely identifies each element. Element children simply have these std::vector<GUID> elements as a "prefix".

As long as your GUID can be sorted using operator< , lexicographic sorting on std::vector will get things in the order you requested.

A map<std::vector<GUID>, Value> can be your container or std::vector< std::pair< GUID, Value > > , which you sort by .first manually.

If your GUID type can have a "last element", you can find each child element {x,y,z} by finding lower_bound from {x,y,z} and upper_bound in {x,y,z,last_guid} . Giving it the "last element" is an advantage of not using a bare pointer.

Answer 3

No. It does not mean to be harsh, but it is the answer; see, for example, Josuttis or standard. You will need to create a class, the parent / child pointer that you specified, and use a vector or other standard container from them.

Answer 4

The answer to your question: no, there is no tree in STL. The templates you proposed are good. Also see this question .