为什么 C++ STL 不提供任何“树”容器？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/205945/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Why does the C++ STL not provide any "tree" containers?
提问by Roddy
Why does the C++ STL not provide any "tree" containers, and what's the best thing to use instead?
为什么 C++ STL 不提供任何“树”容器，而最好使用什么？
I want to store a hierarchy of objects as a tree, rather than use a tree as a performance enhancement...
我想将对象的层次结构存储为树，而不是使用树作为性能增强...
采纳答案by Martin York
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
您想使用树状结构来反映问题：
为此，我们有boost 图库
Or you want a container that has tree like access characteristics For this we have
或者你想要一个具有树状访问特征的容器为此我们有
std::map(andstd::multimap)std::set(andstd::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
另见这个问题： C树实现
回答by Greg Rogers
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.
可能出于同样的原因，boost 中没有树容器。实现这样一个容器的方法有很多种，没有一个好的方法可以让每个会使用它的人都满意。
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 Libraryis essentially a superset of what a tree library could be used for.
最后，问题最终在于，一个对每个人都足够有用的树容器太重了，无法满足大多数使用它的人。如果您正在寻找功能强大的东西，Boost Graph Library本质上是树库可用于什么的超集。
Here are some other generic tree implementations:
下面是一些其他的通用树实现：
回答by wilhelmtell
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.
STL 的理念是您根据保证而不是根据容器的实现方式来选择容器。例如，您选择的容器可能是基于快速查找的需要。不管你关心什么，容器可以作为一个单向列表来实现——只要搜索速度非常快，你就会很高兴。那是因为您无论如何都没有接触内部结构，而是使用迭代器或成员函数进行访问。您的代码与容器的实现方式无关，而与容器的实现方式有关，或者它是否具有固定和定义的排序，或者它是否在空间上有效，等等。
回答by nobar
"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...
C++11 来来去去，他们仍然认为没有必要提供一个std::tree，尽管这个想法确实出现了（见这里）。也许他们没有添加这个的原因是在现有容器之上构建自己的容器非常容易。例如...
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 andyou 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 defininga range within a hierarchy could be a messy business.
如果您想维护一个层次结构并且您希望它与STL 算法一起工作，那么事情可能会变得复杂。您可以构建自己的迭代器并实现一些兼容性，但是许多算法对于层次结构根本没有任何意义（例如，任何改变范围顺序的东西）。即使在层次结构中定义范围也可能是一件麻烦事。
回答by systemsfault
If you are looking for a RB-tree implementation, then stl_tree.hmight be appropriate for you too.
如果您正在寻找 RB 树实现，那么stl_tree.h也可能适合您。
回答by J.J.
the std::map is based on a red black tree. You can also use other containersto help you implement your own types of trees.
回答by Eclipse
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.
在某种程度上，std::map 是一棵树（它需要具有与平衡二叉树相同的性能特征），但它不公开其他树功能。不包括真正的树数据结构背后的可能原因可能只是不包括 stl 中的所有内容。stl 可以看作是一个框架，用于实现您自己的算法和数据结构。
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.
一般来说，如果您想要一个基本的库功能，它不在 stl 中，那么修复方法是查看BOOST。
Otherwise, there's a bunchof librariesoutthere, depending on the needs of your tree.
回答by Emilio Garavaglia
All STL container are externally represented as "sequences" with one iteration mechanism. Trees don't follow this idiom.
所有 STL 容器都在外部表示为具有一种迭代机制的“序列”。树不遵循这个习语。
回答by Paul Nathan
Because the STL is not an "everything" library. It contains, essentially, the minimum structures needed to build things.
因为 STL 不是“一切”库。从本质上讲，它包含构建事物所需的最少结构。
回答by roffez
This one looks promising and seems to be what you're looking for: http://tree.phi-sci.com/
这个看起来很有前途，似乎正是您正在寻找的：http: //tree.phi-sci.com/
