STL中的红黑树_stl 红黑树

STL中的set、map都通过红黑树实现。红黑树的类型实际上是可以拿出来用的。用起来也是容易的。因为不是标准规定的容器，具体的名字可能会略有的差别。

例子最后演示了迭代器find()。这个地方语法上可以修改，但不能随便修改，因为会破坏key的排序。

#include <stdio.h>
#include <set>

using namespace std;

typedef _Rb_tree<int, int, _Identity<int>, less<int> > Tree;

int main()
{
        Tree t;

/*
        t.insert_equal(3);
        t.insert_equal(5);
        t.insert_equal(7);
        t.insert_equal(9);
*/

        t.insert_unique(3);
        t.insert_unique(5);
        t.insert_unique(7);
        t.insert_unique(9);
        t.insert_unique(3);
        t.insert_unique(5);
        t.insert_unique(7);
        t.insert_unique(9);

        Tree::iterator  it;
        it = t.begin();
        while (it!=t.end()) {
                printf("%d ", *it);
                ++it;
        }
        printf("\n");

        it = t.find(7);
        *it=8;
        it = t.begin();
        while (it!=t.end()) {
                printf("%d ", *it);
                ++it;
        }
        printf("\n");

        return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47