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...

Answer 1

In a way, std::map is a tree (it is required to have the same performance characteristics as a balanced binary tree) but it doesn't expose other tree functionality. The likely reasoning behind not including a real tree data structure was probably just a matter of not including everything in the stl. The stl can be looked as a framework to use in implementing your own algorithms and data structures.

In general, if there's a basic library functionality that you want, that's not in the stl, the fix is to looks at BOOST.

Otherwise, there's a bunch of libraries out there, depending on the needs of your tree.

Answer 2

std::map is usually implemented as a tree.

Answer 3

the std::map is based on a red black tree. You can also use other containers to help you implement your own types of trees.

Answer 4

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

You want to mirror a tree like structure problematically:
For this we have boost graph library

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

• std::map
• std::set

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

See also this question: C tree Implementation

Answer 5

Because the STL is not an "everything" library. It contains, essentially, the minimum structures needed to build things.

Answer 6

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

Answer 7

The STL's philosophy is that you choose a container based on guarantees and not based on how the container is implemented. For example, your choice of container may be based on a need for fast lookups. For all you care, the container may be implemented as a unidirectional list -- as long as searching is very fast you'd be happy. That's because you're not touching the internals anyhow, you're using iterators or member functions for the access. Your code is not bound to how the container is implemented but to how fast it is, or whether it has a fixed and defined ordering, or whether it is efficient on space, and so on.