c++ - 为什么 C++ STL 不提供任何“树”容器？

Question

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

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

score 190 · Accepted Answer

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

您想使用树状结构来反映问题：
为此，我们有boost 图形库

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

std::map（和std::multimap）
std::set（和std::multiset）

基本上这两个容器的特性使得它们实际上必须使用树来实现（尽管这实际上不是必需的）。

另请参阅此问题： C 树实现

score 105 · Accepted Answer

可能出于同样的原因，在 boost 中没有树容器。实现这样一个容器的方法有很多种，没有什么好的方法可以让所有会使用它的人都满意。

需要考虑的一些问题：

节点的子节点数量是固定的还是可变的？
每个节点有多少开销？- 即，您是否需要父指针、兄弟指针等？
提供什么算法？- 不同的迭代器、搜索算法等。

最后，问题最终是一个对每个人都足够有用的树容器太重，无法满足大多数使用它的人。如果您正在寻找功能强大的东西，Boost Graph Library本质上是树形库的超集。

以下是一些其他的通用树实现：

score 53 · Accepted Answer

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

score 53 · Accepted Answer

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

C++11 来来去去，他们仍然认为不需要提供 a std::tree，尽管这个想法确实出现了（见这里）。也许他们没有添加它的原因是在现有容器之上构建自己的容器非常容易。例如...

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

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

template< typename T >
void tree_node<T>::walk_depth_first() const
   {
   cout<<t;
   for ( auto & n: children ) n.walk_depth_first();
   }

如果您想维护一个层次结构并希望它与STL 算法一起工作，那么事情可能会变得复杂。您可以构建自己的迭代器并实现一些兼容性，但是许多算法对于层次结构根本没有任何意义（例如，任何改变范围顺序的东西）。即使在层次结构中定义范围也可能是一件麻烦事。

score 48 · Accepted Answer

48

如果您正在寻找 RB-tree 实现，那么stl_tree.h可能也适合您。

于 2011-04-25T11:24:58.100 回答

score 13 · Accepted Answer

13

std::map 基于红黑树。您还可以使用其他容器来帮助您实现自己的树类型。

于 2008-10-15T19:00:23.250 回答

score 9 · Accepted Answer

在某种程度上，std::map 是一棵树（它需要具有与平衡二叉树相同的性能特征），但它不公开其他树功能。不包括真正的树数据结构背后的可能原因可能只是不包括 stl 中的所有内容。stl 可以看作是一个框架，用于实现您自己的算法和数据结构。

一般来说，如果有你想要的基本库功能，那不在 stl 中，解决方法是查看BOOST。

否则，那里有一堆库，这取决于你的树的需要。

score 6 · Accepted Answer

所有 STL 容器在外部都表示为具有一种迭代机制的“序列”。树不遵循这个习语。

score 6 · Accepted Answer

我认为没有 STL 树有几个原因。树主要是递归数据结构的一种形式，它像容器（列表、向量、集合）一样，具有非常不同的精细结构，这使得正确的选择变得棘手。它们也很容易使用 STL 以基本形式构建。

可以将有限有根树视为具有值或有效负载的容器，例如 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
{};

人们必须考虑一下迭代器设计等，以及允许在树之间定义和高效的乘积和联乘操作 - 并且必须很好地编写原始 STL - 以便空集、向量或列表容器是在默认情况下真的没有任何有效载荷。

树在许多数学结构中起着至关重要的作用（参见 Butcher、Grossman 和 Larsen 的经典论文；以及 Connes 和 Kriemer 的论文中关于它们可以连接的示例以及它们如何用于枚举）。认为他们的角色只是为了促进某些其他操作是不正确的。相反，它们促进了这些任务，因为它们作为数据结构的基本作用。

但是，除了树之外，还有“合作树”；最重要的树都有一个属性，如果你删除根，你会删除所有东西。

考虑树上的迭代器，可能它们将被实现为一个简单的迭代器堆栈，到一个节点，到它的父节点，......直到根。

template<class TREE>
struct node_iterator : std::stack<TREE::iterator>{
operator*() {return *back();}
...};

但是，您可以拥有任意数量；它们共同形成一棵“树”，但所有箭头都流向根的方向，这棵共同树可以通过迭代器迭代到平凡的迭代器和根；然而，它不能被导航或向下导航（它不知道其他迭代器），也不能删除迭代器的集合，除非跟踪所有实例。

树非常有用，它们有很多结构，这使得获得绝对正确的方法成为一个严峻的挑战。在我看来，这就是为什么它们没有在 STL 中实现的原因。此外，在过去，我看到人们变得虔诚并发现包含其自身类型实例的容器类型的想法具有挑战性 - 但他们必须面对它 - 这就是树类型所代表的 - 它是一个包含可能是（较小的）树的空集合。当前语言允许它毫无挑战地提供默认构造函数，container<B>不会在堆（或其他任何地方）上为 aB等分配空间。

如果这确实以一种良好的形式进入标准，我会很高兴。

score 5 · Accepted Answer

5

因为 STL 不是“一切”库。本质上，它包含构建事物所需的最小结构。

于 2008-10-15T19:05:42.117 回答

score 5 · Accepted Answer

5

这个看起来很有希望，似乎就是你要找的东西：http: //tree.phi-sci.com/

于 2011-09-29T14:13:34.150 回答

score 5 · Accepted Answer

问题是没有一种万能的解决方案。此外，树甚至没有万能的接口。也就是说，甚至不清楚这种树数据结构应该提供哪些方法，甚至不清楚树是什么。

这就解释了为什么没有 STL 支持：STL 用于大多数人需要的数据结构，基本上每个人都同意什么是合理的接口和有效的实现。对于树来说，这样的事情根本不存在。

血淋淋的细节

如果想进一步了解问题所在，请继续阅读。否则，上面的段落应该足以回答您的问题。

我说连通用接口都没有。您可能不同意，因为您只考虑了一个应用程序，但是如果您进一步考虑它，您会发现树上有无数可能的操作。您可以拥有一个数据结构来有效地启用它们中的大多数，但因此总体上更复杂并且具有该复杂性的开销，或者您拥有更简单的数据结构，只允许基本操作，但这些操作尽可能快。

如果您想要完整的故事，请查看我关于该主题的论文。在那里，您将找到可能的接口、不同实现的渐近复杂性、问题的一般描述以及更多可能实现的相关工作。

什么是树？

它已经从您认为是一棵树的东西开始：

有根或无根：大多数程序员想要有根，大多数数学家想要无根。（如果您想知道什么是无根的：A - B - C 是一棵树，其中 A、B 或 C 都可以是根。有根树定义了哪个是根。无根树没有）
单根/连接或多根/断开连接（树或林）
兄弟顺序是否相关？如果不是，那么树结构是否可以在内部重新排序更新时的子级？如果是这样，则不再定义兄弟之间的迭代顺序。但是对于大多数树来说，兄弟顺序实际上没有意义，并且允许数据结构在更新时对子节点重新排序对于某些更新非常有利。
真的只是一棵树，或者也允许 DAG 边缘（听起来很奇怪，但许多最初想要一棵树的人最终想要一个 DAG）
贴标签还是不贴标签？你需要存储每个节点的任何数据，还是只是你感兴趣的树结构（后者可以非常简洁地存储）

查询操作

在我们弄清楚我们定义的树之后，我们应该定义查询操作：基本操作可能是“导航到子节点，导航到父节点”，但还有更多可能的操作，例如：

导航到下一个/上一个兄弟：即使大多数人都认为这是一个非常基本的操作，如果你只有一个父指针或一个子数组，这实际上几乎是不可能的。因此，这已经向您表明，根据您需要的操作，您可能需要完全不同的实现。
按前/后顺序导航
子树大小：当前节点的（传递）后代的数量（可能在 O(1) 或 O(log n) 中，即不要只枚举它们全部计数）
当前节点中树的高度。即从这个节点到任何离开节点的最长路径。同样，在小于 O(n) 的时间内。
给定两个节点，找到该节点的最小共同祖先（使用 O(1) 内存消耗）
在前序/后序遍历中，节点 A 和节点 B 之间有多少个节点？（少于 O(n) 运行时间）

我强调这里有趣的是这些方法是否可以比 O(n) 执行得更好，因为仅枚举整个树始终是一种选择。根据您的应用程序，某些操作比 O(n) 更快可能是绝对关键的，或者您可能根本不关心。同样，根据您的需要，您将需要非常不同的数据结构。

更新操作

到目前为止，我只讨论了查询操作。但现在要更新了。同样，可以通过多种方式更新树。根据您的需要，您需要或多或少复杂的数据结构：

叶更新（简单）：删除或添加叶节点
内部节点更新（更难）：移动或删除移动内部节点，使其子节点成为其父节点的子节点
子树更新（更难）：移动或删除以节点为根的子树

只是给你一些直觉：如果你存储一个子数组并且你的兄弟顺序很重要，即使删除一个叶子也可能是 O(n) 因为它后面的所有兄弟都必须在其父数组的子数组中移动。相反，如果您只有一个父指针，则叶删除是微不足道的 O(1)。如果您不关心兄弟顺序，则子数组也是 O(1)，因为您可以简单地将间隙替换为数组中的最后一个兄弟。这只是一个示例，不同的数据结构将为您提供完全不同的更新功能。

在父指针的情况下，移动整个子树再次简单地 O(1)，但如果您有一个存储所有节点的数据结构，例如按预购顺序，则可能是 O(n)。

然后，有一些正交的考虑，比如如果你执行更新，哪些迭代器保持有效。一些数据结构需要使整个树中的所有迭代器都无效，即使你插入了一个新的叶子。其他人仅使树中被更改的部分中的迭代器无效。其他人保持所有迭代器（已删除节点的迭代器除外）有效。

空间考虑

树结构可以非常简洁。如果您需要节省空间（例如，DFUDS 或 LOUDS，请参阅此说明以了解要点），每个节点大约两个位就足够了。但是当然，天真地，即使是父指针也已经是 64 位了。一旦你选择了一个很好导航的结构，你可能宁愿每个节点需要 20 个字节。

有了很多复杂性，人们还可以构建一个每个条目只需要一些位的数据结构，可以有效地更新，并且仍然可以渐近快速地实现所有查询操作，但这是一个非常复杂的结构的野兽。我曾经开设了一门实践课程，让研究生实施这篇论文。他们中的一些人能够在 6 周内实施它（！），其他人则失败了。虽然该结构具有很好的渐近性，但它的复杂性使其对于非常简单的操作具有相当大的开销。

同样，没有一种万能的。

结论

我花了 5 年时间寻找表示树的最佳数据结构，尽管我想出了一些并且有相当多的相关工作，但我的结论是没有。根据用例，高度复杂的数据结构将优于简单的父指针。甚至为树定义接口也很困难。我尝试在我的论文中定义一个，但我必须承认在各种用例中我定义的接口太窄或太大。所以我怀疑这是否会出现在 STL 中，因为调音旋钮太多了。

score 4 · Accepted Answer

IMO，一个遗漏。但我认为有充分的理由不在 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); } 
} ;

score 3 · Accepted Answer

通读这里的答案，常见的命名原因是不能遍历树，或者树不假设与其他 STL 容器的类似接口，并且不能使用具有这种树结构的 STL 算法。

考虑到这一点，我尝试设计自己的树数据结构，该结构将提供类似 STL 的接口，并尽可能与现有的 STL 算法一起使用。

我的想法是，树必须基于现有的 STL 容器，并且它不能隐藏容器，以便它可以与 STL 算法一起使用。

树必须提供的另一个重要特性是遍历迭代器。

这是我能想到的：https ://github.com/cppfw/utki/blob/master/src/utki/tree.hpp

这里是测试：https ://github.com/cppfw/utki/blob/master/tests/unit/src/tree.cpp

score -10 · Accepted Answer

所有 STL 容器都可以与迭代器一起使用。你不能有一个迭代器和一棵树，因为你没有“一个正确的”方式穿过树。

c++ - 为什么 C++ STL 不提供任何“树”容器？

15 回答 15

血淋淋的细节

什么是树？

查询操作

更新操作

空间考虑

结论

Related

Reference