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



Answers

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

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




I think there are several reasons why there are no stl trees. Primarily Trees are a form of recursive data structure which, like a container (list, vector, set), has very different fine structure which makes the correct choices tricky. They are also very easy to construct in basic form using the STL.

A finite rooted tree can be thought of as a container which has a value or payload, say an instance of a class A and, a possibly empty collection of rooted (sub) trees; trees that empty of subtrees are though of as leaves.

template<class A>
struct unordered_tree : std::set<unordered_tree>, A
{};

template<class A>
struct b_tree : std::vector<b_tree>, A
{};

template<class A>
struct planar_tree : std::list<planar_tree>, A
{};

One has to think a little about iterator design etc. and which product and co-product operations one allows to define and be efficient between trees - and the original stl has to be well written - so that the empty set, vector or list container is really empty of any payload in the default case.

Trees play an essential role in many mathematical structures (see the classical papers of Butcher, Grossman and Larsen; also the papers of Connes and Kriemer for examples of they can be joined, and how they are used to enumerate). It is not correct to think their role is simply to facilitate certain other operations. Rather they facilitate those tasks because of their fundamental role as a data structure.

However, in addition to trees there are also "co-trees"; the trees above all have the property that if you delete the root you delete everything.

Consider iterators on the tree, probably they would be realised as a simple stack of iterators, to a node, and to its parent, ... up to the root.

template<class TREE>
struct node_iterator : std::stack<TREE::iterator>{
operator*() {return *back();}
...};

However, you can have as many as you like; collectively they form a "tree" but where all the arrows flow in the direction toward the root, this co-tree can iterated though iterators towards the trivial iterator and root; however it cannot be navigated across or down (the other iterators are not known to it) nor can the ensemble of iterators be deleted except by keeping track of all the instances.

Trees are incredibly useful, they have a lot of structure, this makes it a serious challenge to get the definitively correct approach. In my view this is why they are not implemented in the STL. Moreover, in the past, I have seen people get religious and find the idea of a type of container containing instances of its own type challenging - but they have to face it - that is what a tree type represents - it is a node containing a possibly empty collection of (smaller) trees. The current language permits it without challenge providing the default constructor for container<B> does not allocate space on the heap (or anywhere else) for an B, etc.

I for one would be pleased if this did, in a good form, find its way into the standard.




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.







All STL container are externally represented as "sequences" with one iteration mechanism. Trees don't follow this idiom.




"I want to store a hierarchy of objects as a tree"

C++11 has come and gone and they still didn't see a need to provide a std::tree, although the idea did come up (see here). Maybe the reason they haven't added this is that it is trivially easy to build your own on top of the existing containers. For example...

template< typename T >
struct tree_node
   {
   T t;
   std::vector<tree_node> children;
   };

A simple traversal would use recursion...

template< typename T >
void tree_node<T>::walk_depth_first() const
   {
   cout<<t;
   for ( auto & n: children ) n.walk_depth_first();
   }

If you want to maintain a hierarchy and you want it to work with STL algorithms, then things may get complicated. You could build your own iterators and achieve some compatibility, however many of the algorithms simply don't make any sense for a hierarchy (anything that changes the order of a range, for example). Even defining a range within a hierarchy could be a messy business.




Links



Tags

c++ c++   stl   tree