为什么不C++STL不提供任何"树"集装箱?

StackOverflow https://stackoverflow.com/questions/205945

  •  03-07-2019
  •  | 
  •  

题

为什么不C++STL不提供任何"树"容器，以及什么是最好的事情来使用，而不是?

我想要保存一个层次的对象一棵树，而不是使用一种树作为增强性能...

有帮助吗？

解决方案

有两个原因，你可能要使用一棵树：

你要镜子的使用问题树形结构：
为此，我们必须 提高图表的图书馆

或者你想一个容器的有树一样的访问特点 为此，我们必须

基本特点这两个容器就是这样，他们几乎有可实施的使用树木(虽然这实际上不是一个要求)。

也看到这个问题：C树执行情况

其他提示

可能出于同样的原因，没有树容器中的提升。有许多方法来实现这样的容器，并且没有良好的方式满足的人都会使用它。

要考虑的一些问题:
-是的儿童人数为一个节点的固定的或可变的?
-多少开销，每个节点?-即你需要父母的指针，同级的指针，等等。
-什么样的算法来提供？-不同的迭代，搜索算法，等等。

最终，问题的结束是一个树容器，将是有用的足够的每一个人，将会过于重量级，以满足大多数人使用它。如果你是在寻找的东西强大， 提高图表的图书馆 基本上是一个超集一个什么样的树库可用。

这里有一些其他一般的树实现：
- 卡斯帕Peeters'树。hh
- Adobe的森林
- 核心::树

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

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

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

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

一般情况下，如果你想要一个基本的库功能，那就不在stl中，修复就是查看 BOOST 。

否则，一堆 //www.codeproject.com/KB/architecture/treedata_class.aspx"rel =“nofollow noreferrer”>库 out 那里，视乎需求而定你的树。

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

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

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

IMO，遗漏。但我认为有充分的理由不在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); } 
} ;

我认为没有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中实现的原因。此外，在过去，我看到人们变得宗教，并且发现包含自己类型的实例的容器类型的想法具有挑战性 - 但是他们必须面对它 - 这就是树类型所代表的 - 它是一个包含可能是（较小的）树木的空集合。当前语言允许它没有挑战提供容器的默认构造函数＆lt; B＆gt; 不在堆（或其他任何地方）为 B 等分配空间。

如果这样做，我会很高兴以良好的形式进入标准。

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top