Is there an stl container for this hierarchical model data?

Question

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

• Item A
  • SubItem A
  • SubItem B
  • SubItem C
    • SubSubItem A
    • SubSubItem B
  • SubItem D
• Item B
• Item C

Now, within each "level" (Item, SubItem, SubSubItem, etc.) the items need to be sorted alphabetically.

Seems 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. (and one root item). I would need to generally iterate through each item's children in a forward direction.

After construction/sorting, I do not need to add or delete items. Generally small numbers of items (hundreds).

This is for model organization of the backing data of an outline-style control.

Rolling a simple class would be easy, but this is such a common pattern — isn't there already a ready-made STL container with this behavior?

Answer 1

Nothing in STL itself, but you might find this useful:

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

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

I believe their example is exactly what you are asking about (a tree with strings), in fact.

Answer 2

A simple solution:

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

So long as your GUID are sortable via operator<, lexographic sorting on the std::vector will get things in the order you requested.

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

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