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

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

Solution 3

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.

Solution 4

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

Solution 5

If you are looking for a RB-tree implementation, then stl_tree.h might be appropriate for you too.

View more solutions

Comments

[Martin York]

It usually uses red-black trees (Its not required to do so).

[J.J.]

GCC uses a tree to implement map. Anyone wanna look at their VC include directory to see what microsoft uses?

[J.J.]

// Red-black tree class, designed for use in implementing STL // associative containers (set, multiset, map, and multimap). Grabbed that from my stl_tree.h file.

[Sharon]

There are many, many reasons to use a tree, even if these are the most common. Most common !equal all.

[Catskul]

Strangely this is the only response that actually answers the original question.

[Catskul]

Binary trees are an extremely basic functionality, and in fact, more basic than other containers since types like std::map, std::multimap, and stl::set. Since those types are based on them, you would expect the underlying type to be exposed.

[Catskul]

"...no good way to satisfy everyone..." Except that since stl::map, stl::multimap, and stl::set are based on stl's rb_tree, it should satisfy just as many cases as those basic types do.

[VoidStar]

A third major reason to want a tree is for an always-sorted list with fast insertion/removal, but for that there is std:multiset.

[Andrew Tomazos]

A tree data structure could provide preorder, inorder or postorder traversal via iterators. In fact this is what std::map does.

[Emilio Garavaglia]

Yes and no ... it depends on what you mean by "tree". std::map is internally implemented as btree, but externally it appears as a sorted SEQUENCE of PAIRS. Given whatever element you can universally ask who is before and who is after. A general tree structures containing elements each of which contains other does not impose any sorting or direction. You can define iterators that walk a tree structure in many ways (sallow|deep first|last ...) but once you did it, an std::tree container must return one of them from a begin function. And there is no obvious reason to return one or another.

[Andrew Tomazos]

A std::map is generally represented by a balanced binary search tree, not a B-tree. The same argument you have made could apply to std::unordered_set, it has no natural order, yet presents begin and end iterators. The requirement of begin and end is just that it iterates all elements in some deterministic order, not that there has to be a natural one. preorder is a perfectly valid iteration order for a tree.

[Emilio Garavaglia]

"A std::map is generally represented by a balanced binary search tree, not a B-tree.": what game are you playing? a btree is an implementation for a binary search tree and map is nor "represented" as such. it is "IMPLEMENTED" as such. it is REPRESENTED as a sorted sequence of pairs that starts at begin() and terminate just before end(). It is true that you can walk a tree starting form some begin() up to some end(), but, unless defining a purpose for it (like map does) there is anymore no clue than have the elements into a list.

[Andrew Tomazos]

The implication of your answer is that there is no stl n-tree data structure because it is doesn't have a "sequence" interface. This is simply incorrect.

[Emilio Garavaglia]

No: because it doesn't have a UNIQUE WAY to define a sequence interface, since it's normal purpose is to don't be just plain sequence. Imposing one of it as "standard" will defeat the advantage to have such a structure, and not imposing it will make the structure useless respect to <algorithm>, every other container is compliant with. You can always do that yourself, but the way you will do it will conflict with the way of somebody else, and there are no technical reasons to prefer one or the other. So there cannot be a "standard" way.

[Andrew Tomazos]

@EmiloGaravaglia: As evidenced by std::unordered_set, which has no "unique way" of iterating its members (in fact the iteration order is pseudo-random and implementation defined), but is still an stl container - this disproves your point. Iterating over each element in a container is still a useful operation, even if the order is undefined.

[Emilio Garavaglia]

I'm not anymore able to userstand if it's me uncapable to explain or you that don't want to understand. unordered_set has no unique way to SORT, but has a unique way to WALK: start with begin() and ends with end(), and can be subject to whatever <algorithm>. But a tree with a unique way to WALK is useless, since the purpose of a tree is to be WALKED in at least up-dowmn and left-right. If my way to speak is not comprehensible to you, read this: stackoverflow.com/a/206011/924727 That's exactly my concept, with other wording.

[Andrew Tomazos]

There is no reason that a container needs to have one way to walk, it is possible to offer different iteration orders by different types of iterator pairs (for example see rbegin/rend). A std:tree could have something like breadth_begin/breadth_end and depth_begin/depth_end for the up-down and left-right orders respectively. The answer you link to is correct, it is the great variance in potential structure that lead to it being left out of the standard library, but this has nothing to do with "sequences" or "one iteration mechanism".

[Emilio Garavaglia]

It has to do, because they are the main reason of such a variance. Feel free to don't beleave it, but let me believe in peace in with god!

[Mooing Duck]

Considering there's no way to retrieve the children of a node of a std::map, I wouldn't call those tree containers. Those are associative containers that are commonly implemented as trees. Big difference.

[Mooing Duck]

I don't think he's talking about container implementations, he's talking about an actual tree container itself.

[Mooing Duck]

Considering he wants a "Heiarchy", It seems safe to assume that anything with "balancing" is the wrong answer.

[Mooing Duck]

I don't think the OP is asking for a binary tree, he's asking for a tree to store a hierarchy.

[Mooing Duck]

That's a lot of owning raw pointers you have there, many of which have no need of being pointers at all.

[J Jorgenson]

If the project can allow for the the children of a tree_node to be sorted, then using a std::set<> in place of the std::vector<> and then adding an operator<() to the tree_node object will greatly improve 'search' performance of an 'T'-like object.

[tomas789]

But you can say BFS or DFS is the correct way. Or support both of them. Or any other you can imagine. Jut tell the user what it is.

[Marco A.]

I agree with Mooing Duck, how would you implement a breadth first search on a std::map? It's going to be terribly expensive

[Jake88]

I started using Kasper Peeters' tree.hh, however after reviewing the licensing for GPLv3, or any other GPL version, it would contaminate our commercial software. I would recommend looking at treetree provided in the comment by @hplbsh if you need a structure for commercial purposes.

[user541686]

It turns out that they were lazy and actually made your first example Undefined Behavior.

[Wildcat]

Actually, Boost provides a tree container. The library is called Boost.PropertyTree.

[Tom]

I ended up using datasoftsolutions.net/tree_container_library/overview.php, I tried treetree but the documentation was sparse and usage very difficult. Boost.PropertyTree works well with strings, but didn't see any examples of using anything else. TCL is header-only, commercial friendly, and STL friendly. It's working well for my purposes.

[Dan]

"This is an internal header file, included by other library headers. You should not attempt to use it directly."

[NDestiny]

How can we use map for tree kind of data structure when we don't know depth of the tree ??

[André]

The variety specific requirements on trees is an argument to have different types of trees, not to have none at all.

[emsr]

@EmilioGaravaglia I see your point. You want to be able to choose iteration strategy in a tree container because a) a tree semantically matches your data b) you want to traverse the tree in a specific to solve a problem. Possible solution: std::tree has an enumeral tag template argument which tells the default traversal order as given by begin() for range for, say. This template arg is defaulted to say traversal::inorder. You could even give names to the others: template<typename NodeT> using tree_pre<NoteT> = tree<NodeT, traversal::preorder>; etc. This is a workable problem.

[emsr]

In other news, a lot of work is going into an iterator library for the next standard. Maybe something in there would help.

[Emilio Garavaglia]

@emsr: Good suggestion. Of course, 3 years later something is evolving, but ... in fact it introduced a new concept (ranges), in fact allowing to break a constrain.

[Martin York]

@Durga: Not sure how the depth is relevant when you are using map as a sorted container. Map guarantees log(n) insertion/deletion/lookup (and containing elements in sorted order). This is all map is used for and is implemented (usually) as a red/black tree. A red/black tree makes sure that the tree is balanced. So the depth of the tree is directly related to the number of elements in the tree.

[Jai]

in std::map there is tree iterator.

[Brent Bradburn]

@Mehrdad: I finally decided to ask for the detail behind your comment here.

[Jordan Melo]

@MooingDuck I think what wilhelmtell means is that the C++ standard library doesn't define containers based on their underlying data structure; it only defines containers by their interface and observable characteristics like asymptotic performance. When you think about it, a tree isn't really a container (as we know them) at all. They don't even have a a straight forward end() and begin() with which you can iterate through all elements, etc.

[Mooing Duck]

@JordanMelo: Nonsense on all points. It's a thing that contains objects. It's very trivial to design it to have a begin() and end() and bidirectional iterators to iterate with. Each container has different characteristics. It would be useful if one could additionally have tree characteristics. Should be pretty easy.

[Justin Time - Reinstate Monica]

Would it be possible to create a template class or struct that can act as a tree, allowing the user to specify their needs as template parameters? I imagine that would be the most general way to implement a standard tree, although it would likely be somewhat clunky.

[Justin Time - Reinstate Monica]

@J.J. At least in Studio 2010, it uses an internal ordered red-black tree of {key, mapped} values, unique keys class, defined in <xtree>. Don't have access to a more modern version right at the moment.

[Justin Time - Reinstate Monica]

A tree could define its own custom iterator type that traverses all nodes in order from one "extreme" to the other (i.e. for any binary tree with paths 0 & 1, it could offer an iterator that goes from "all 0s" to "all 1s", and a reverse iterator that does the opposite; for a tree with a depth of 3 and starting node s, for example, it could iterate over the nodes as s000, s00, s001, s0, s010, s01, s011, s, s100, s10, s101, s1, s110, s11, s111 ("leftmost" to "rightmost"); it could also use a depth traversal pattern (s, s0, s1, s00, s01, s10, s11,

[Justin Time - Reinstate Monica]

, etc.), or some other pattern, as long as it iterates over every node in such a way that each one is only passed a single time.

[einpoklum]

I disagree with this answer, both in 2008 and now. The standard library does not "have" boost, and the availability of something in boost should not be (and has not been) a reason not to adopt it into the standard. Additionally, the BGL is general and involved enough to merit specialized tree classes independent from it. Also, the fact that std::map and std::set require a tree is, IMO, another argument for having an stl::red_black_tree etc. Finally, the std::map and std::set trees are balanced, an std::tree might not be.

[einpoklum]

@Dan: Copying it does not constitute using it directly.

[einpoklum]

Suggest you withdraw this answer. A TreeNode class is part of a tree implementation.

[alfC]

I don't understand why this answer have been so badly downvoted. This is the the only one that actually answers the question. Tree is not part of the STL interface (although it is there internally) because a Tree is not a Container in the STL sense, that is, it is not a container of elements with linear iteration. (For example it won't have a unique begin() and end()). Adding a tree to STL would have mean to add many many new concepts, for example a tree navigator (generalizing Iterator).

[alfC]

Not only that, adding a tree "container" to STL would have mean to add many many new concepts, for example a tree navigator (generalizing Iterator).

[Edward Kirton]

Boost Graph Library provides an R-tree.

[mip]

Thus one wants to have a container that provides fast lookups for child and parent nodes, and reasonable memory requirements.

[mip]

@alfC what's wrong with defining begin() as a root node and end() as a last leaf?

[alfC]

@doc, there are many leafs of course, and even if you choose one as the last there is no unique way to walk the three linearly.

[mip]

@alfC you can pick any of the DFS or BFS as tomas789 pointed out already. I have implemented iterators for my tree-like structures many times.

[alfC]

@doc, sure, but the transversal is not unique like in a sequence. A general graph can be DFS or BFS transversed and that still doesn't make them a sequence. They can be viewed as sequence, but that is different.

[mip]

@alfC std library is not limitted to sequences, std::unordered_map is not a sequence, yet it already exists in standard library. There's no such thing as "unique iteration" or "unique traversal". Even with an array you could iterate over it in any fashion you like. Iterators address this issue exactly and provide an abstraction layer, so you can iterate over structures like std::map. It's all a matter of convention.

[mip]

"Minimum structures to build things" is a very subjective statement. You can build things with raw C++ concepts, so I gues true minimum would be no STL at all.

[mip]

many of the algorithms simply don't make any sense for a hierarchy. A matter of interpretation. Imagine a structure of stackoverflow users and each year you want those with higher amount of reputation points to boss those with lower reputation points. Thus providing BFS iterator and appropriate comparison, every year you just run std::sort(tree.begin(), tree.end()).

[alfC]

@doc, very good point. I think std::unordered_set was "made" a sequence because we don't know a better way of iterating over the elements other than some arbitrary way (internally given by the hash function). I think it is the opposite case of the tree: the iteration over unordered_set is underspecified, in theory there is "no way" of defining an iteration other than perhaps "randomly". In the case of tree there are many "good" (non random) ways. But, again, your point is valid.

[Martin Bonner supports Monica]

@einpoklum : "the availability of something in boost should not be a reason not to adopt it into the standard" - given one of the purposes of boost is to act as a proving ground for useful libraries before incorporation in the standard, I can only say "absolutely!".

[andreee]

@JordanMelo: From that perspective, also adapters like queues, stacks or priority queues would not belong to the STL (they also do not have begin() and end()). And remember that a priority queue is typically a heap, which at least in theory is a tree (even though actual implementations). So even if you implemented a tree as an adapter using some different underlying data structure, it would be eligible to be included in the STL.

[Jordan Melo]

@andreee Certainly nobody is saying that only containers belong in the STL. Container adapters do not fit the Container concept and they are obviously in the STL as you've observed. You give priority_queue as an example, but I think you would agree that it does not expose any tree-like behaviours and utilizes a tree structure for a very specific purpose. But what about generic trees? Remember that one of the most important functions of a tree structure is to model relationships, which don't always adhere to the binary tree structure.

[Brent Bradburn]

By the same token, you could easily build an associative tree (to model unstructured key-value records, like JSON for example) by replacing vector with map in the example above. For full support of a JSON-like structure, you could use variant to define the nodes.

[fwyzard]

it's also trivially easy to build one's own implementation of vector on top of new/delete, yet we have and most everybody uses std::vector...

[gast128]

The standard library / STL is minimal compared to extensive library support in other environments like .NET and JAVA. I wish it would be more extensive so that for basic things (like XML, JSON; serialization; networking; gui) you don't have to include external libraries. A raw (unbalanced) tree could be an addition as other containers like a vector with sbo; circular_buffer; better hash map; dynamic_bitset with sbo; AVL and B-tree's; etc.)

[MSalters]

The answer is indeed fundamentally flawed. Most STL containers already define TWO ways; rbegin/rend form another iterator range. A tree could easily offer inorder_begin() etcetera.

[ealfonso]

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. What about fast sorted inserts?