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

Question

为什么C ++ STL不提供任何“树”容器，而最好使用什么呢？我想将对象的层次结构存储为树，而不是将树用作性能增强...

Answer 1

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

您想使用树状结构来反映问题：

为此，我们有增强图形库

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

std::map（和std::multimap）

std::set（和std::multiset）

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

Answer 2

可能出于同样的原因，boost中没有树容器。有很多方法可以实现这样的容器，并且没有令人满意的方法来满足使用它的每个人。

需要考虑的一些问题：

-节点的子代数目是固定的还是可变的？

-每个节点多少开销？-例如，您是否需要父指针，兄弟指针等？

-提供哪些算法？-不同的迭代器，搜索算法等

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

Answer 3

STL的理念是，您根据保证而不是根据容器的实现方式来选择容器。例如，您对容器的选择可能基于对快速查找的需求。尽您所能，容器可以实现为单向列表-只要搜索非常快，您就会感到满意。那是因为您无论如何都没有接触内部，而是使用迭代器或成员函数进行访问。您的代码并不局限于容器的实现方式，而是取决于它的运行速度，它是否具有固定的和已定义的顺序，或者在空间上是否有效等等。