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

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


当前回答

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

其他回答

使用树有两个原因:

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

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

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

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

还有这个问题: C树实现

"我想把对象的层次结构存储为树"

c++ 11来了又走了,他们仍然认为没有必要提供std::tree,尽管这个想法确实出现了(见这里)。也许他们没有添加的原因是,在现有容器的基础上构建自己的容器非常简单。例如……

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

在我看来,这是个疏忽。但是我认为有很好的理由不在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); } 
} ;

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

可能与boost中没有树容器的原因相同。有许多方法可以实现这样的容器,没有一种好方法可以满足所有使用它的人。

需要考虑的一些问题:

节点的子节点数是固定的还是可变的? 每个节点的开销是多少?-即,你需要父指针,兄弟指针等。 提供什么算法?-不同的迭代器,搜索算法等。

最后的问题是,一个对所有人都足够有用的树容器,会因为太过重量级而无法满足大多数使用它的人。如果您正在寻找功能强大的东西,Boost Graph Library本质上是树库的超集。

下面是其他一些通用树的实现:

卡斯珀·彼得斯的树 Adobe的森林 核心:树