为什么C STL不提供任何“树”容器？-Java 学习之路

332

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

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

13 回答

171

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

回复于 2024-04-24T01:53:09+08:00
2

这看起来很有希望，似乎是你正在寻找的：http://tree.phi-sci.com/

回复于 2024-04-24T01:53:09+08:00
82

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

回复于 2024-04-24T01:53:09+08:00
11
可能出于同样的原因，在增强中没有树容器 . 有很多方法可以实现这样一个容器，并没有很好的方法来满足每个使用它的人 .

需要考虑的一些问题：
- 节点的子节点数是固定的还是可变的？
- 每个节点有多少开销？ - 即，你需要父指针，兄弟指针等 .
- 提供什么算法？ - 不同的迭代器，搜索算法等
最后，问题最终是一个对每个人都足够有用的树容器，它太重了，无法满足大多数使用它的人 . 如果您正在寻找功能强大的东西，Boost Graph Library本质上是树库可用的超集 .

以下是一些其他通用树实现：
回复于 2024-04-24T01:53:09+08:00
8

std :: map基于red black tree . 您还可以使用其他containers来帮助您实现自己的树类型 .

回复于 2024-04-24T01:53:09+08:00
4

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

回复于 2024-04-24T01:53:09+08:00
-8

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

回复于 2024-04-24T01:53:09+08:00
48
您可能想要使用树的原因有两个：

您想使用树状结构镜像问题：
为此，我们有boost graph library

或者你想要一个具有树状访问特征的容器为此我们有
- std::map
- std::set
基本上这两个容器的特性使得它们实际上必须使用树来实现（尽管这实际上不是必需的） .

另见这个问题：C tree Implementation
回复于 2024-04-24T01:53:09+08:00
2
我认为没有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 等分配空间 .

如果以一种良好的形式做到这一点，我会很高兴找到进入标准的方法 .
回复于 2024-04-24T01:53:09+08:00
39

因为STL不是“一切”库 . 它基本上包含构建东西所需的最小结构 .

回复于 2024-04-24T01:53:09+08:00
44

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

一般情况下，如果's a basic library functionality that you want, that'不在stl中，修复方法是查看BOOST .

否则，根据树的需要，有一个bunch libraries out there .

回复于 2024-04-24T01:53:09+08:00

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); } 
} ;

回复于 2024-04-24T01:53:09+08:00

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

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一起使用，那么事情可能会变得复杂 . 您可以构建自己的迭代器并实现一些兼容性，但是许多算法对层次结构没有任何意义（例如，任何改变范围顺序的东西） . 即使在层次结构中定义范围也可能是一个混乱的业务 .
回复于 2024-04-24T01:53:09+08:00

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

13 回答

相关问题