Why does the C++ STL not provide any "tree" containers?


Question

Why does the C++ STL not provide any "tree" containers, and what's the best thing to use instead?

I want to store a hierarchy of objects as a tree, rather than use a tree as a performance enhancement...

1
354
11/18/2008 9:22:33 AM

Accepted Answer

There are two reasons you could want to use a tree:

You want to mirror the problem using a tree-like structure:
For this we have boost graph library

Or you want a container that has tree like access characteristics For this we have

Basically the characteristics of these two containers is such that they practically have to be implemented using trees (though this is not actually a requirement).

See also this question: C tree Implementation

176
5/24/2019 2:53:59 PM

Probably for the same reason that there is no tree container in boost. There are many ways to implement such a container, and there is no good way to satisfy everyone who would use it.

Some issues to consider:
- Are the number of children for a node fixed or variable?
- How much overhead per node? - ie, do you need parent pointers, sibling pointers, etc.
- What algorithms to provide? - different iterators, search algorithms, etc.

In the end, the problem ends up being that a tree container that would be useful enough to everyone, would be too heavyweight to satisfy most of the people using it. If you are looking for something powerful, Boost Graph Library is essentially a superset of what a tree library could be used for.

Here are some other generic tree implementations:
- Kasper Peeters' tree.hh
- Adobe's forest
- core::tree


Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Icon