Why does the C++ STL not provide any "tree" containers?
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 std::set 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
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
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.
链接地址: http://www.djcxy.com/p/62802.html上一篇: 无法在终端中显示Git树