Share|

平时用STL通常只是顺手把vector, map之类常用的类拿来用用就完了，也没有想到去仔细研究里面都有些什么东西。这两天有一个算法程序需要将一堆对象排序，并且会非常频繁的插入删除，对效率的要求极高。原本想用priority queue，但是发现它是对一个数组进行堆排序的方式来操作，效率并不高。在STL的文档里面找了找发现居然没有红黑树，google了一下才知道set, map底层都是用红黑树实现的，只是这个红黑树没有暴露出来给人用。

也不知道是出于什么考虑，性能优秀的红黑树虽然标准库里面有，但是却遮遮掩掩不直接提供给大家用。值得注意的是，因为红黑树是内部使用的类，各个STL实现中的红黑树还不一样。

在VC的实现中红黑树是在xtree文件中的_Tree类，用法如下：

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#include 
#include 
#include 
 
using namespace std;
 
typedef _Tree< _Tset_traits, allocator, false > > rb_tree;
 
int main()
{
    rb_tree* tree = new rb_tree( less(), allocator() );
    for(int i=35; iinsert(i);
 
    printf("output: %d ", *tree->begin() );
}

gcc中的实现则是在bits/stl_tree.h文件中，而且类的名字和用法都不一样：

?View Code C
1
2
3
4
5
6
7
8
9
10
11
12

#include 
 
typedef _Rb_tree,
                 less > rb_tree;
typedef rb_tree::iterator rb_tree_iter;
 
int main()
{
    rb_tree queue;
    queue._M_insert_unique( int );
    printf("size: %d", queue.size() );
}