为什么c++ STL不提供任何“树”容器,用什么代替最好?
我想将对象的层次结构存储为树,而不是使用树来增强性能……
为什么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中包含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不是一个“万能”库。本质上,它包含了建造东西所需的最小结构。
如果您正在寻找一个rb树实现,那么stl_tree.h可能也适合您。
所有STL容器都可以与迭代器一起使用。你不能在树中使用迭代器,因为你没有遍历树的“唯一正确”方法。
这一个看起来很有前途,似乎是你正在寻找的: http://tree.phi-sci.com/