本文共 2356 字，大约阅读时间需要 7 分钟。

http://hi.baidu.com/qingshanyin/blog/item/7271448b67d242799e2fb419.html

1、ACE提供的树实现为红黑树，名为ACE_RB_Tree，接口与映射表类似，其实现实际上是一个值容器。类型定义是：

ACE_RB_Tree

2、测试类：Tree_Practice.h

#include "ace/RB_Tree.h"

#include "DataElement.h" //红黑树类型封装成助手模板类Little helper class //EXT_ID--键值类型，INT_ID--元素类型 template<class EXT_ID,class INT_ID> class Tree:public ACE_RB_Tree<EXT_ID,INT_ID,ACE_Less_Than<EXT_ID>,ACE_Null_Mutex> {}; //键类型： class Tree_Test { public: //测试总函数 int run(void) {    ACE_TRACE(ACE_TEXT("Tree_Test::run"));    ACE_DEBUG((LM_DEBUG,ACE_TEXT("Using ACE_RB_Tree/n")));    DataElement *d=0;    for(int i=0;i<100;i++)    {     //树中的元素全部在堆中创建     ACE_NEW_RETURN(d,DataElement(i),-1);     //将元素插入到树中，插入复杂度是O(lgN)     int result=tree_.bind(i,d);     if(result!=0)     {      ACE_ERROR_RETURN((LM_ERROR,ACE_TEXT("%p/n"),ACE_TEXT("Bind")),-1);     }    }    //查找元素，查找复杂度也是O(lgN)    ACE_DEBUG((LM_DEBUG,ACE_TEXT("Using find:/n")));    for(int j=0;j<100;j++)    {     tree_.find(j,d);     ACE_DEBUG((LM_DEBUG,ACE_TEXT("%d:"),d->getData()));    }    ACE_DEBUG((LM_DEBUG,ACE_TEXT("/n")));

   //前向迭代

   this->iterate_forward();

   //后向迭代

   this->iterate_reverse();

   //移除所有元素

   ACE_ASSERT(this->remove_all()!=-1);

   //前向迭代

   this->iterate_forward();

   return 0;

}

//前向迭代测试

//运行结果：0：1：2：...99 void iterate_forward(void) {    ACE_TRACE(ACE_TEXT("Tree_Test::iterate_forward"));

   ACE_DEBUG((LM_DEBUG,ACE_TEXT("Forward Iteration:/n")));

   //前向迭代，注意迭代器Tree<int,DataElement*>::iterator    for(Tree<int,DataElement*>::iterator iter=tree_.begin();     iter!=tree_.end();iter++)    {     ACE_DEBUG((LM_DEBUG,ACE_TEXT("%d:"),(*iter).item()->getData()));    }    ACE_DEBUG((LM_DEBUG,ACE_TEXT("/n"))); }

//后向迭代测试

//运行结果：99：98：97：...0 void iterate_reverse(void) {    ACE_TRACE(ACE_TEXT("Tree_Test::iterate_reverse"));

   ACE_DEBUG((LM_DEBUG,ACE_TEXT("Reverse Iteration:/n")));

   for(Tree<int,DataElement*>::reverse_iterator iter=tree_.rbegin();     iter!=tree_.rend();iter++)    {     ACE_DEBUG((LM_DEBUG,ACE_TEXT("%d:"),(*iter).item()->getData()));    }

   ACE_DEBUG((LM_DEBUG,ACE_TEXT("/n")));

}

//移除所有元素

int remove_all(void) {    ACE_TRACE(ACE_TEXT("Tree_Test::remove_all"));    ACE_DEBUG((LM_DEBUG,ACE_TEXT("Removing elements/n")));    //注意这里不能用迭代器，因为在删除操作或插入操作后，迭代器会失效    for(int i=0;i<100;i++)    {     DataElement* d=0;     //移除元素     int result=tree_.unbind(i,d);     if(result!=0)     {      ACE_ERROR_RETURN((LM_ERROR,ACE_TEXT("%p/n"),ACE_TEXT("Unbind")),-1);         }     ACE_ASSERT(d!=0);     //元素在堆中创建的，需要清理内存，否则将造成内存泄漏     delete d;    }    return 0; } private: Tree<int,DataElement*> tree_; };

转载地址：http://mvgxi.baihongyu.com/