为什么c++ STL不提供任何“树”容器,用什么代替最好?

我想将对象的层次结构存储为树,而不是使用树来增强性能……


当前回答

在我看来,这是个疏忽。但是我认为有很好的理由不在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不是一个“万能”库。本质上,它包含了建造东西所需的最小结构。

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

使用树有两个原因:

你想用树形结构来镜像问题: 为此我们有boost图形库

或者您想要一个具有树形访问特征的容器 我们有

Std::map(和Std::multimap) Std::set(和Std::multiset)

基本上,这两个容器的特点是,它们实际上必须使用树来实现(尽管这实际上不是一个要求)。

还有这个问题: C树实现

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

通读这里的答案,常见的命名原因是不能遍历树,或者树没有假设与其他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