为什么c++ STL不提供任何“树”集装箱吗?

为什么c++ STL不提供任何“树”容器，用什么代替最好?

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

253269 次浏览
小开

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

一般来说，如果你想要一个基本的库功能，而它不在stl中，修复方法是查看提高。

否则，会有库 出 在那里的群，这取决于你的树的需要。

小开

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

小开
最佳答案

使用树有两个原因:

你想用一个树形结构来镜像问题 为此，我们有Boost图形库

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

基本上，这两个容器的特点是，它们实际上必须使用树来实现(尽管这实际上不是一个要求)。

参见这个问题: C树实现 < / p >

小开

因为STL不是一个“万能”库。本质上，它包含了建造东西所需的最小结构。

小开

可能与boost中没有树容器的原因相同。有许多方法可以实现这样的容器，没有一种好方法可以满足所有使用它的人。

需要考虑的一些问题:

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

最后的问题是，一个对所有人都足够有用的树容器，会因为太过重量级而无法满足大多数使用它的人。如果你在寻找一些功能强大的东西，Boost图形库本质上是一个树库的超集。

下面是其他一些通用树的实现:

小开

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

小开

如果你正在寻找一个rb树的实现，那么stl_tree.h可能也适合你。

小开
这一个看起来很有前途，似乎是你正在寻找的: http://tree.phi-sci.com/ < / p >
小开
所有STL容器都在外部表示为具有一种迭代机制的“序列”。

.树不遵循这个成语
小开

在我看来，这是个疏忽。但是我认为有很好的理由不在STL中包含Tree结构。维护树有很多逻辑，最好写成将成员函数放入基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); }
} ;
小开

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

c++ 11来了又去，他们仍然认为没有必要提供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算法一起工作，那么事情可能会变得复杂。您可以构建自己的迭代器并实现一些兼容性，但是许多算法对于层次结构没有任何意义(例如，任何改变范围顺序的东西)。即使是层次结构中的定义范围也可能是一件混乱的事情。

小开

所有STL容器都可以与迭代器一起使用。你不能在树中使用迭代器，因为你没有遍历树的“唯一正确”方法。

小开

我认为没有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的经典论文;还有康内斯和克里默的论文，他们可以结合的例子，以及他们是如何用来列举的)。认为它们的作用只是促进某些其他行动是不正确的。相反，由于它们作为数据结构的基本角色，它们有助于完成这些任务。

然而，除了树，还有“协同树”;上面这些树都有一个特性，如果你删除根，你就删除了所有东西。

考虑树中的迭代器，它们可能会被实现为一个简单的迭代器堆栈，指向一个节点，以及它的父节点……一直到根部。

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

但是，你想要多少就可以有多少;它们共同组成了一个“树”，但所有的箭头都指向根，这个协同树可以通过迭代器迭代平凡迭代器和根;但是它不能向下或向下导航(它不知道其他迭代器)，也不能删除迭代器集合，除非通过跟踪所有实例。

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

就我个人而言，如果它以一种良好的形式出现在标准中，我会很高兴。

小开

通读这里的答案，常见的命名原因是不能遍历树，或者树没有假设与其他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

小开

问题在于，没有放之四海而皆准的解决方案。此外，对于树，甚至没有一个通用的接口。也就是说，甚至不清楚这样的树数据结构应该提供哪些方法，甚至不清楚树是什么。

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

血腥的细节

如果想进一步了解问题是什么，请继续阅读。否则，上面这段话已经足以回答你的问题了。

我说过，甚至没有一个共同的界面。您可能不同意，因为您脑海中只有一个应用程序，但如果您进一步思考，您将看到在树上有无数种可能的操作。您可以使用一种数据结构，它可以有效地实现大多数操作，但因此总体上更复杂，并为这种复杂性带来开销;或者您可以使用更简单的数据结构，它只允许基本操作，但尽可能快地执行这些操作。

如果你想了解完整的故事，请查看关于这个主题的论文。在那里，你会发现可能的接口，不同实现上的渐近复杂性，以及问题的一般描述，以及与更多可能的实现相关的工作。

树是什么?

它已经从你认为是树的东西开始:

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

查询操作

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

  • 导航到next/prev兄弟姐妹:即使大多数人都认为这是一个非常基本的操作，如果你只有一个父指针或子数组，这实际上几乎是不可能的。这已经告诉你你可能需要一个完全不同的实现基于你需要的操作。
  • 按前后顺序导航
  • 子树大小:当前节点的(可传递的)后代的数量(可能是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)。

然后，还有一些正交的考虑因素，比如如果执行更新，哪些迭代器保持有效。一些数据结构需要使整个树中的所有迭代器失效，即使您插入了一个新的叶。其他的迭代器只会使树中被修改的部分失效。其他迭代器则保持所有迭代器(删除节点的迭代器除外)有效。

空间的考虑

树形结构可以非常简洁。如果需要节省空间，大约每个节点2位就足够了(例如，DFUDS或LOUDS，请参阅这个解释以获得要点)。当然，很简单，一个父指针已经是64位了。一旦选择了易于导航的结构，则可能需要每个节点20个字节。

有了很多复杂的东西，也可以构建一个数据结构，每个条目只占用一些位，可以有效地更新，并且仍然使所有查询操作渐近快速，但这是一个非常复杂的结构。我曾经开过一门实践课，让研究生们实践这篇论文。他们中的一些人能够在6周内实现它(!)，其他人失败了。虽然这个结构有很大的渐近性，但它的复杂性使它对于非常简单的操作有相当大的开销。

再说一次，没有一刀切的方法。

结论

我花了5年的时间来寻找最好的数据结构来表示一棵树，即使我想出了一些并且有相当多的相关工作，我的结论是没有一个。根据用例的不同，一个高度复杂的数据结构将被一个简单的父指针所超越。甚至为树定义接口也很困难。我尝试在我的论文中定义一个，但我必须承认，在各种用例中，我定义的接口要么太窄，要么太大。所以我怀疑这将永远结束在STL，因为有太多的调谐旋钮。


提交答案