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

Solution 1:

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

• std::map (and std::multimap)
• std::set (and std::multiset)

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

Solution 2:

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