为什么C++ STL不提供任何"树"容器？

为什么C++ STL不提供任何"树"容器,而最好使用什么？

我想将对象的层次结构存储为树,而不是使用树作为性能增强...

1> Martin York..：

---

您可能想要使用树有两个原因:

您希望使用类似树的结构来镜像问题:
为此,我们使用了boost图库

或者你想要一个具有树状访问特征的容器为此我们有

std::map

std::multimap

基本上这两个容器的特征是它们实际上必须使用树来实现(尽管这实际上不是必需的).

另见这个问题: C树实现

---

使用树的原因有很多,即使这些是最常见的.最常见的!等于全部.

---

我在2008年和现在都不同意这个答案.标准库没有"有"提升,并且提升中某些东西的可用性不应该(并且还没有)成为不将其纳入标准的理由.此外,BGL是通用的,并且足以支持独立于其的专用树类.另外,std :: map和std :: set需要树的事实是,IMO,另一个参数是拥有`stl :: red_black_tree`等等.最后,`std :: map`和`std :: set`树是平衡的,`std :: tree`可能不是.

---

请将std :: multiset和std :: multimap添加到列表中.

---

想要树的第三个主要原因是具有快速插入/删除的始终排序列表,但是为此存在std:multiset.

2> Greg Rogers..：

---

可能出于同样的原因,在增强中没有树容器.有很多方法可以实现这样一个容器,并没有很好的方法来满足每个使用它的人.

需要考虑的一些问题:
- 节点的子节点数是固定的还是可变的？
- 每个节点有多少开销？- 即,你需要父指针,兄弟指针等
- 提供什么算法？ - 不同的迭代器,搜索算法等

最后,问题最终是一个对每个人都足够有用的树容器,对于大多数使用它的人来说太重了.如果您正在寻找功能强大的东西,Boost Graph Library本质上是树库可用的超集.

以下是一些其他通用树实现:
- Kasper Peeters的tree.hh
- Adobe的林
- 核心::树

---

考虑到无法检索`std :: map`节点的子节点,我不会调用那些树容器.这些是通常作为树实现的关联容器.很大的区别.

---

"......没有好办法让每个人都满意......"除了因为stl :: map,stl :: multimap和stl :: set都是基于stl的rb_tree,它应该满足那些基本类型的情况. .

---

对树木的特定品种要求是拥有不同类型的树木而不是根本没有树木的论点。

3> wilhelmtell..：

---

STL的理念是您选择基于保证的容器,而不是基于容器的实现方式.例如,您选择的容器可能基于快速查找的需要.对于您所关心的一切,容器可以实现为单向列表 - 只要搜索速度非常快,您就会感到高兴.那是因为你无论如何都没有触及内部,你正在使用迭代器或成员函数进行访问.您的代码不受容器实现方式的限制,而是绑定到它的速度,或者它是否具有固定和定义的顺序,或者它是否在空间上有效等等.

---

我不认为他在谈论容器实现,他在谈论一个真正的树容器本身.

---

@JordanMelo:关于所有观点的废话.这是一个包含对象的东西.将它设计为具有begin()和end()以及双向迭代器以进行迭代是非常简单的.每个容器都有不同的特征.如果可以另外具有树特征将是有用的.应该很容易.

---

@MooingDuck我认为wilhelmtell意味着C++标准库没有根据它们的底层数据结构定义容器; 它只通过它们的接口和渐近性能等可观察的特征来定义容器.当你想到它时,一棵树根本就不是一个容器(就像我们所知道的那样).它们甚至没有一个直接的`end()`和`begin()`,您可以使用它来遍历所有元素等.

4> nobar..：

---

"我想将对象的层次结构存储为树"

C++ 11已经过去了,他们仍然没有看到需要提供一个std::tree,虽然这个想法确实出现了(见这里).也许他们没有添加这个的原因是,在现有容器之上构建自己的容易起来非常容易.例如...

template< typename T >
struct tree_node
   {
   T t;
   std::vector children;
   };

一个简单的遍历将使用递归...

template< typename T >
void tree_node::walk_depth_first() const
   {
   cout<

如果您想维护层次结构并希望它与STL算法一起使用,那么事情可能会变得复杂.您可以构建自己的迭代器并实现一些兼容性,但是许多算法对层次结构没有任何意义(例如,任何改变范围顺序的东西).即使在层次结构中定义范围也可能是一项混乱的业务.

        
事实证明,他们是懒惰的,实际上是你的第一个例子Undefined Behavior. 
如果项目可以允许对tree_node的子节点进行排序,那么使用std :: set <>代替std :: vector <>然后将一个运算符<()添加到tree_node对象将大大改善'搜索''T'类对象的表现. 
@Mehrdad:我最后决定要求你的评论背后的细节[这里](http://stackoverflow.com/questions/32487575/class-or-struct-self-reference-by-template). 

5> systemsfault..：
如果您正在寻找RB树实现,那么stl_tree.h也可能适合您.

        
奇怪的是,这是实际回答原始问题的唯一回应. 
考虑到他想要一个"Heiarchy",似乎可以安全地假设任何具有"平衡"的东西都是错误的答案. 
"这是一个内部头文件,包含在其他库头文件中.您不应该尝试直接使用它." 
@Dan:复制它并不构成直接使用它. 

6> J.J...：
std :: map基于一棵红黑树.您还可以使用其他容器来帮助您实现自己的树类型.

        
它通常使用红黑树(不需要这样做). 

7> Eclipse..：
在某种程度上,std :: map是一棵树(它需要具有与平衡二叉树相同的性能特征),但它不会暴露其他树功能.不包括真实树数据结构的可能原因可能只是不包括stl中的所有内容.可以将stl看作是用于实现自己的算法和数据结构的框架.

一般来说,如果你想要一个基本的库功能,那就不是在stl中,修复就是看看BOOST.

否则,有一个一堆的库 了 那里,这取决于你的树的需求.

        

8> Emilio Garav..：
所有STL容器外部表示为具有一个迭代机制的"序列".树木不遵循这个习语.

        
树数据结构可以通过迭代器提供预订,顺序或后序遍历.实际上这就是std :: map的作用. 
是的,不是......这取决于你对"树"的意思.`std :: map`在内部实现为btree,但在外部它显示为PAIRS的排序SEQUENCE.无论你有什么元素,你都可以普遍地问谁以前和谁在追求.包含元素的一般树结构中的每一个都包含其他元素,不会强加任何排序或方向.你可以定义以多种方式遍历树结构的迭代器(sallow | deep first | last ...)但是一旦你做到了,`std :: tree`容器必须从`begin`函数返回其中一个.并没有明显的理由让一个或另一个回归. 
std :: map通常由平衡二叉搜索树表示,而不是B树.您所做的相同参数可以应用于std :: unordered_set,它没有自然顺序,但提供了开始和结束迭代器.开始和结束的要求只是它以某种确定性顺序迭代所有元素,而不是必须有一个自然元素.preorder是树的完全有效的迭代顺序. 
你的答案的含义是没有stl n-tree数据结构,因为它没有"序列"接口.这完全是错误的. 
@EmiloGaravaglia:由`std :: unordered_set`证明,它没有迭代其成员的"独特方式"(实际上迭代顺序是伪随机和实现定义),但仍然是一个stl容器 - 这反驳了你的观点.即使订单未定义,迭代容器中的每个元素仍然是一项有用的操作.