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...
Join Stack Overflow to learn, share knowledge, and build your career.
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...
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
stl::red_black_tree
etc. Finally, the std::map
and std::set
trees are balanced, an std::tree
might not be.
– einpoklum
Jul 26 '16 at 15:59
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:
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:
std::map
, I wouldn't call those tree containers. Those are associative containers that are commonly implemented as trees. Big difference.
– Mooing Duck
Sep 30 '13 at 4:53
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.
end()
and begin()
with which you can iterate through all elements, etc.
– Jordan Melo
Nov 26 '15 at 20:43
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.
– andreee
Jan 10 '19 at 14:58
"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.
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())
.
– doc
Dec 30 '16 at 3:04
vector
with map
in the example above. For full support of a JSON-like structure, you could use variant
to define the nodes.
– Brent Bradburn
Aug 19 '19 at 16:31
If you are looking for a RB-tree implementation, then stl_tree.h might be appropriate for you too.
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.
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
Jun 15 '16 at 21:16
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 look at BOOST.
Otherwise, there's a bunch of libraries out there, depending on the needs of your tree.
All STL container are externally represented as "sequences" with one iteration mechanism. Trees don't follow this idiom.
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.
– Emilio Garavaglia
Sep 23 '12 at 13:41
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.
– Andrew Tomazos
Sep 25 '12 at 3:10
Because the STL is not an "everything" library. It contains, essentially, the minimum structures needed to build things.
This one looks promising and seems to be what you're looking for: http://tree.phi-sci.com/
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 with empty collection of subtrees are thought 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 be iterated through 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.
IMO, an omission. But I think there is good reason not to include a Tree structure in the STL. There is a lot of logic in maintaining a tree, which is best written as member functions into the base TreeNode
object. When TreeNode
is wrapped up in an STL header, it just gets messier.
For example:
template <typename T>
struct TreeNode
{
T* DATA ; // data of type T to be stored at this TreeNode
vector< TreeNode<T>* > children ;
// insertion logic for if an insert is asked of me.
// may append to children, or may pass off to one of the child nodes
void insert( T* newData ) ;
} ;
template <typename T>
struct Tree
{
TreeNode<T>* root;
// TREE LEVEL functions
void clear() { delete root ; root=0; }
void insert( T* data ) { if(root)root->insert(data); }
} ;
Reading through the answers here the common named reasons are that one cannot iterate through the tree or that the tree does not assume the similar interface to other STL containers and one could not use STL algorithms with such tree structure.
Having that in mind I tried to design my own tree data structure which will provide STL-like interface and will be usable with existing STL algorthims as much as possible.
My idea was that the tree must be based on the existing STL containers and that it must not hide the container, so that it will be accessible to use with STL algorithms.
The other important feature the tree must provide is the traversing iterators.
Here is what I was able to come up with: https://github.com/cppfw/utki/blob/master/src/utki/tree.hpp
And here are the tests: https://github.com/cppfw/utki/blob/master/tests/tree/tests.cpp
All STL containers can be used with iterators. You can't have an iterator an a tree, because you don't have ''one right'' way do go through the tree.
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
Jun 15 '16 at 21:32
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.
– alfC
Dec 30 '16 at 5:46
std::unordered_map
andstd::unordered_set
until recently. And before that there was no STL containers in standard library at all. – doc Dec 30 '16 at 2:34std::map
andstd::set
will use a tree in every implementation out there, but they don't have to if if some non-tree structure also meets the specifications. – Mark K Cowan Jul 27 '17 at 21:22