为什么 C++ STL 不提供任何“树”容器,而最好使用什么?
我想将对象的层次结构存储为树,而不是使用树作为性能增强...
std::unordered_map
和 std::unordered_set
。在此之前,标准库中根本没有 STL 容器。
std::map
和 std::set
将在每个实现中使用树,但如果某些非树结构也符合规范,它们就不必这样做。
您可能想要使用树有两个原因:
您想使用树状结构来反映问题:
为此,我们有 boost graph library
或者您想要一个具有树状访问特性的容器为此我们有
std::map(和 std::multimap)
std::set(和 std::multiset)
基本上这两个容器的特性使得它们实际上必须使用树来实现(尽管这实际上不是必需的)。
另请参阅此问题:C tree Implementation
可能出于同样的原因,在 boost 中没有树容器。实现这样一个容器的方法有很多种,没有什么好的方法可以让所有会使用它的人都满意。
需要考虑的一些问题:
节点的子节点数量是固定的还是可变的?
每个节点有多少开销? - 即,您是否需要父指针、兄弟指针等?
提供什么算法? - 不同的迭代器、搜索算法等。
最后,问题最终是一个对每个人都足够有用的树容器太重,无法满足大多数使用它的人。如果您正在寻找功能强大的东西,Boost Graph Library 本质上是树库的超集。
以下是一些其他的通用树实现:
Kasper Peeters 的树.hh
Adobe的森林
核心::树
std::map
的节点的子节点,我不会调用这些树容器。这些是通常作为树实现的关联容器。巨大差距。
STL 的理念是基于保证而不是基于容器的实现方式来选择容器。例如,您对容器的选择可能基于快速查找的需要。对于您所关心的,容器可以实现为单向列表——只要搜索速度非常快,您会很高兴。那是因为无论如何您都没有触及内部,而是使用迭代器或成员函数进行访问。你的代码不受容器是如何实现的约束,而是它的速度,或者它是否具有固定和定义的顺序,或者它是否在空间上是有效的,等等。
end()
和 begin()
可以用来遍历所有元素等。
begin()
和 end()
)。请记住,优先级队列通常是一个堆,至少在理论上是一棵树(即使实际实现也是如此)。因此,即使您使用一些不同的底层数据结构将树实现为适配器,它也有资格包含在 STL 中。
“我想将对象的层次结构存储为树”
C++11 来来去去,他们仍然认为没有必要提供 std::tree
,尽管这个想法确实出现了(参见 here)。也许他们没有添加它的原因是在现有容器之上构建自己的容器非常容易。例如...
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 algorithms 一起工作,那么事情可能会变得复杂。您可以构建自己的迭代器并实现一些兼容性,但是许多算法对于层次结构根本没有任何意义(例如,任何改变范围顺序的东西)。即使在层次结构中定义范围也可能是一件麻烦事。
many of the algorithms simply don't make any sense for a hierarchy
。解释的问题。想象一下 stackoverflow 用户的结构,每年您都希望那些拥有较高声望点的人能够支配那些声望点较低的用户。从而提供 BFS 迭代器和适当的比较,每年您只需运行 std::sort(tree.begin(), tree.end())
。
vector
替换为 map
轻松构建关联树(用于对非结构化键值记录建模,例如 JSON)。要完全支持类似 JSON 的结构,您可以使用 variant
来定义节点。
如果您正在寻找 RB-tree 实现,那么 stl_tree.h 可能也适合您。
std::map 基于 red black tree。您还可以使用其他 containers 来帮助您实现自己的树类型。
<xtree>
中定义的内部 ordered red-black tree of {key, mapped} values, unique keys
类。目前无法访问更现代的版本。
所有 STL 容器在外部都表示为具有一种迭代机制的“序列”。树不遵循这个习语。
std::map
在内部实现为 btree,但在外部它显示为 PAIRS 的排序序列。给定任何元素,您可以普遍询问谁在前,谁在后。包含元素的一般树结构,每个元素都包含其他元素,不会强加任何排序或方向。您可以以多种方式定义遍历树结构的迭代器(sallow|deep first|last ...),但一旦这样做,std::tree
容器必须从 begin
函数返回其中一个。并且没有明显的理由退回一个或另一个。
std::unordered_set
所证明的那样,它没有迭代其成员的“独特方式”(实际上迭代顺序是伪随机和实现定义的),但仍然是一个 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 的经典论文;以及 Connes 和 Kriemer 的论文中关于它们可以连接的示例以及它们如何用于枚举)。认为他们的角色只是为了促进某些其他操作是不正确的。相反,它们促进了这些任务,因为它们作为数据结构的基本作用。
但是,除了树之外,还有“合作树”;最重要的树都有一个属性,如果你删除根,你会删除所有东西。
考虑树上的迭代器,可能它们将被实现为一个简单的迭代器堆栈,到一个节点,到它的父节点,......直到根。
template<class TREE>
struct node_iterator : std::stack<TREE::iterator>{
operator*() {return *back();}
...};
但是,您可以拥有任意数量;它们共同形成一棵“树”,但所有箭头都流向根的方向,这棵共同树可以通过迭代器迭代到平凡的迭代器和根;然而,它不能被导航或向下导航(它不知道其他迭代器),也不能删除迭代器的集合,除非跟踪所有实例。
树非常有用,它们有很多结构,这使得获得绝对正确的方法成为一个严峻的挑战。在我看来,这就是为什么它们没有在 STL 中实现的原因。此外,在过去,我看到人们变得虔诚并发现包含其自身类型实例的容器类型的想法具有挑战性 - 但他们必须面对它 - 这就是树类型所代表的 - 它是一个包含可能是(较小的)树的空集合。当前语言允许它毫无挑战地提供 container<B>
的默认构造函数不会在堆(或其他任何地方)上为 B
分配空间等。
如果这确实以一种良好的形式进入标准,我会很高兴。
问题是没有一种万能的解决方案。此外,树甚至没有万能的接口。也就是说,甚至不清楚这种树数据结构应该提供哪些方法,甚至不清楚树是什么。
这就解释了为什么没有 STL 支持:STL 用于大多数人需要的数据结构,基本上每个人都同意什么是合理的接口和有效的实现。对于树来说,这样的事情根本不存在。
血淋淋的细节
如果想进一步了解问题所在,请继续阅读。否则,上面的段落应该足以回答您的问题。
我说连通用接口都没有。您可能不同意,因为您只考虑了一个应用程序,但是如果您进一步考虑它,您会发现树上有无数可能的操作。您可以拥有一个数据结构来有效地启用它们中的大多数,但因此总体上更复杂并且具有该复杂性的开销,或者您拥有更简单的数据结构,只允许基本操作,但这些操作尽可能快。
如果您想了解完整的故事,请查看my paper on the topic。在那里,您将找到可能的接口、不同实现的渐近复杂性、问题的一般描述以及更多可能实现的相关工作。
什么是树?
它已经从您认为是一棵树的东西开始:
有根或无根:大多数程序员想要有根,大多数数学家想要无根。 (如果您想知道什么是无根的: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,请参阅 this explanation 了解要点)。但是当然,天真地,即使是父指针也已经是 64 位了。一旦你选择了一个很好导航的结构,你可能宁愿每个节点需要 20 个字节。
有了很多复杂性,也可以构建 a data structure that only takes some bits per entry, can be updated efficiently, and still enables all query operations asymptotically fast,但这是一个结构非常复杂的野兽。我曾经开设了一门实践课程,让研究生实施这篇论文。他们中的一些人能够在 6 周内实施它(!),其他人则失败了。虽然该结构具有很好的渐近性,但它的复杂性使其对于非常简单的操作具有相当大的开销。
同样,没有一种万能的。
结论
我花了 5 年时间寻找表示树的最佳数据结构,尽管我想出了一些并且有相当多的相关工作,但我的结论是没有。根据用例,高度复杂的数据结构将优于简单的父指针。甚至为树定义接口也很困难。我尝试在我的论文中定义一个,但我必须承认在各种用例中我定义的接口太窄或太大。所以我怀疑这是否会出现在 STL 中,因为调音旋钮太多了。
因为 STL 不是“一切”库。本质上,它包含构建事物所需的最小结构。
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); }
} ;
通读这里的答案,常见的命名原因是不能遍历树,或者树不假设与其他 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 容器都可以与迭代器一起使用。你不能有一个迭代器和一棵树,因为你没有“一个正确的”方式穿过树。
s
的树,它可以将节点迭代为 s000
、s00
、s001
, s0
、s010
、s01
、s011
、s
、s100
、s10
、s101
、s1
、s110
、s11
、s111
(“最左边" 到 "最右边");它也可以使用深度遍历模式 (s
, s0
, s1
, s00
, s01
, s10
, s11
,
std::unordered_set
是“制作”一个序列,因为除了某种任意方式(内部由散列函数给出)之外,我们不知道迭代元素的更好方式。我认为这是树的相反情况:unordered_set
上的迭代未指定,理论上除了“随机”之外,“没有办法”定义迭代。在树的情况下,有许多“好”(非随机)方式。但是,再一次,你的观点是有效的。
stl::red_black_tree
等的参数。最后,std::map
和std::set
树是平衡的,std::tree
可能不是。