为什么c++ STL不提供任何“树”容器,用什么代替最好?
我想将对象的层次结构存储为树,而不是使用树来增强性能……
为什么c++ STL不提供任何“树”容器,用什么代替最好?
我想将对象的层次结构存储为树,而不是使用树来增强性能……
当前回答
因为STL不是一个“万能”库。本质上,它包含了建造东西所需的最小结构。
其他回答
因为STL不是一个“万能”库。本质上,它包含了建造东西所需的最小结构。
通读这里的答案,常见的命名原因是不能遍历树,或者树没有假设与其他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容器在外部都被表示为具有一种迭代机制的“序列”。 树不遵循这个成语。
在某种程度上,std::map是一棵树(它被要求具有与平衡二叉树相同的性能特征),但它不公开其他树功能。不包含真正的树数据结构的原因可能只是不包含stl中的所有内容。stl可以被视为一个框架,用于实现您自己的算法和数据结构。
一般来说,如果你想要一个基本的库功能,而它不在stl中,修复方法是查看BOOST。
除此之外,还有很多库,这取决于树的需要。
std::map基于红黑树。您还可以使用其他容器来帮助您实现自己的树类型。