为什么C ++ STL不提供任何“树”容器？
为什么C ++ STL不提供任何“树”容器，而最好使用什么呢？
我想将对象的层次结构存储为树，而不是将树用作性能增强…
有两个原因可以使用树：
你想用一个树状结构来反映问题：
为此，我们增加了graphics库
或者你想要一个像访问特性树的容器为此我们有
std::map-
std::set
基本上这两个容器的特点是它们实际上必须用树来实现（尽pipe这实际上不是要求）。
另请参阅此问题： C树实现
也许出于同样的原因，没有树容器在推动。 实现这样一个容器的方法有很多，没有什么好办法来满足每个使用它的人。
有些问题需要考虑：
– 一个节点的孩子数是固定的还是可变的？
– 每个节点有多less开销？ – 即，你需要父指针，兄弟指针等
– 提供什么algorithm？ – 不同的迭代器，searchalgorithm等
最后，问题的结果是一个对每个人都足够有用的树容器将太重以至于不能满足大多数使用它的人。 如果您正在寻找强大的function， Boost Graph Library本质上是一个树库的超集。
以下是其他一些通用树实现：
– Kasper Peeters的tree.hh
– Adobe的森林
– core :: tree
STL的理念是select一个基于保证的容器，而不是基于容器如何实现。 例如，您select的容器可能基于快速查找的需要。 对于你所关心的，容器可以被实现为一个单向列表 – 只要search速度非常快，你就会开心。 那是因为你没有触及内部，你使用迭代器或成员函数来访问。 你的代码并不受限于容器的实现方式，而是它的速度有多快，或者它是否具有固定和定义的顺序，或者是否在空间上有效等等。
“我想将对象的层次结构存储为一棵树”
C ++ 11已经过去了，他们仍然没有看到需要提供一个std::tree ，尽pipe这个想法确实出现了（见这里 ）。 也许他们之所以没有添加这个function，是因为在现有的容器之上构build自己的应用程序非常简单。 例如…
template< typename T > struct tree_node { T t; std::vector<tree_node> children; };
一个简单的遍历将使用recursion…
template< typename T > void tree_node<T>::walk_depth_first() const { cout<<t; for ( auto & n: children ) n.walk_depth_first(); }
如果你想保持一个层次结构， 并希望它与STLalgorithm一起工作，那么事情可能会变得复杂。 你可以构build你自己的迭代器并实现一些兼容性，然而许多algorithm对于一个层次结构（例如，改变一个范围的顺序的任何东西）根本没有任何意义。 即使在层次结构中定义一个范围可能是一个混乱的业务。
如果你正在寻找一个RB树实现，那么stl_tree.h也许适合你。
std :: map基于一棵红黑树 。 您也可以使用其他容器来帮助您实现自己的树型。
在某种程度上，std :: map是一个树（它需要与平衡二叉树具有相同的性能特征），但是它不公开其他树function。 不包括真正的树数据结构的可能原因可能仅仅是不包括stl中的所有内容。 stl可以看作一个框架，用于实现你自己的algorithm和数据结构。
一般来说，如果你需要一个基本的库函数，那不在stl中，修正就是看BOOST 。
否则，根据你的树的需要，这里有一堆 库 。
所有STL容器在外部表示为具有一个迭代机制的“序列”。 树不遵循这个习语。
因为STL不是“一切”库。 它基本上包含构build事物所需的最小结构。
这一个看起来很有希望，似乎是你要找的东西： http : //tree.phi-sci.com/
国际海事组织，一个遗漏。 但是我认为在STL中不包含树结构是有好理由的。 在维护一个树时有很多逻辑，最好把这个树写成基本TreeNode对象的成员函数 。 当TreeNode封装在STL头部时，它变得更加混乱。
例如：
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); } } ;
我认为有几个原因为什么没有stl树。 主要树是recursion数据结构的一种forms，像容器（列表，向量，集合）一样，具有非常不同的精细结构，使得正确的select变得棘手。 使用STL的基本forms也很容易构build。
有限根树可以被认为是一个容器，它具有一个值或有效载荷，例如一个类A的实例，以及一个可能为空的根（子）树集合。 空树的树虽然是叶子。
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 {};
人们必须考虑一些关于迭代器devise等等，以及允许哪些产品和联合产品操作在树之间定义和有效，并且原始stl必须写得很好，以便空集，向量或列表容器是在默认情况下真的是空的任何有效载荷。
树在许多math结构中扮演着重要的angular色（参见Butcher，Grossman和Larsen的经典论文，Connes和Kriemer关于它们可以被join的例子，以及它们如何被用来列举）。 认为他们的angular色仅仅是为了便利某些其他行动是不正确的。 而是因为它们作为数据结构的基本angular色而促成了这些任务。
但是，除了树木之外，还有“共同的树木”。 首先是树的属性，如果你删除根目录，你删除所有的东西。
考虑树上的迭代器，可能它们将被实现为一个简单的迭代器栈，一个节点以及它的父节点，直到根节点。
template<class TREE> struct node_iterator : std::stack<TREE::iterator>{ operator*() {return *back();} ...};
但是，你可以拥有尽可能多的， 它们共同形成一个“树”，但是所有的箭头都朝着根的方向stream动，这个共树可以通过迭代器迭代到平凡的迭代器和根; 但是不能跨越或向下导航（其他迭代器不知道），也不能删除迭代器的集合，除非跟踪所有的实例。
树木是非常有用的，他们有很多的结构，这是一个严峻的挑战，得到最终正确的方法。 在我看来，这就是为什么他们没有在STL中实现。 而且，在过去，我看到人们有了宗教信仰，并且发现了一种容器types的概念，它包含了自己types的实例，但它们必须面对它 – 这是一个树types所代表的 – 它是一个包含可能是空的（小）树的集合。 当前的语言允许它没有任何挑战，如果container<B>的默认构造函数不为container<B>的堆（或其他任何地方）分配空间等等。
如果这样做的话，我会很高兴，以一个好的forms，find标准的方式。
所有的STL容器都可以和迭代器一起使用。 你不能有一个迭代器一棵树，因为你没有“一个正确”的方式去通过树。
