1class Foo {...};
2Foo *pf = new Foo;
3delete pf;

 1allocator::value_type
 2allocator::pointer
 3allocator::const_pointer
 4allocator::reference
 5allocator::const_reference
 6allocator::size_type
 7allocator::difference_type
 8
 9//一个嵌套的class template，class rebind<U> 拥有唯一成员other,是一个typedef，代表allocator<U> 
10allocator::rebind
11
12//构造函数
13allocator::allocator()
14//拷贝构造函数
15allocator::allocator(const allocator&)  
16template <class U> allocator::allocator(const allocator<U>&)
17//析构函数
18allocator::~allocator
19
20//返回某个对象的地址，等同于&x
21pointer allocator::address(reference x) const   
22const_pointer allocator::address(const_reference x) const
23
24//分配空间，足以容纳n个元素
25pointer allocator::allocate(size_type n,const void* = 0)
26//归还之前分配的空间
27void allocator::deallocate(pointer p,size_type n)
28//可分配的最大空间
29size_type allocator::max_size() const
30
31//通过x，在p指向的地址构造一个对象。相当于new((void*)p) T(x)
32void allocator::construct(pointer p,const T& x)
33//析构地址p的对象
34void allocator::destroy(pointer p)

 1template<class T, class Alloc>
 2class simple_alloc {
 3
 4public:
 5    static T *allocate(size_t n)
 6                { return 0 == n? 0 : (T*) Alloc::allocate(n * sizeof (T)); }
 7    static T *allocate(void)
 8                { return (T*) Alloc::allocate(sizeof (T)); }
 9    static void deallocate(T *p, size_t n)
10                { if (0 != n) Alloc::deallocate(p, n * sizeof (T)); }
11    static void deallocate(T *p)
12                { Alloc::deallocate(p, sizeof (T)); }
13};

 1//一般而言是线程安全，并且对于空间的运用比较高效
 2//无“template型别参数”，至于”非型别参数“inst，则完全没派上用场
 3template <int inst>
 4class __malloc_alloc_template {
 5
 6private:
 7//oom：out of memory ，用来处理内存不足的情况
 8static void *oom_malloc(size_t);
 9
10static void *oom_realloc(void *, size_t);
11
12#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
13    static void (* __malloc_alloc_oom_handler)();
14#endif
15
16public:
17
18static void * allocate(size_t n)
19{
20    void *result = malloc(n);//第一级分配器直接使用malloc()
21    //以下无法满足需求时，改用oom_malloc()
22    if (0 == result) result = oom_malloc(n);
23    return result;
24}
25
26static void deallocate(void *p, size_t /* n */)
27{
28    free(p);//第一级分配器直接使用free()
29}
30
31static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz)
32{
33    void * result = realloc(p, new_sz);//第一级分配器直接使用realloc()
34    //以下无法满足需求时，改用oom_realloc()
35    if (0 == result) result = oom_realloc(p, new_sz);
36    return result;
37}
38
39//以下仿真C++的set_new_handler()。可以通过它指定自己的
40//out-of-memory handler
41//不能直接运用C++ new-handler机制，因为它并非使用::operator new来分配内存
42static void (* set_malloc_handler(void (*f)()))()
43{
44    void (* old)() = __malloc_alloc_oom_handler;
45    __malloc_alloc_oom_handler = f;
46    return(old);
47}
48
49};
50
51// malloc_alloc out-of-memory handling
52
53#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
54//初值为0，有待客户设定
55template <int inst>
56void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;
57#endif
58
59template <int inst>
60void * __malloc_alloc_template<inst>::oom_malloc(size_t n)
61{
62    void (* my_malloc_handler)();
63    void *result;
64
65    for (;;) {//不断尝试释放、分配、再释放、再分配...
66        my_malloc_handler = __malloc_alloc_oom_handler;
67        if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; }
68        (*my_malloc_handler)(); //调用处理例程，企图释放内存
69        result = malloc(n);     //再次尝试分配内存
70        if (result) return(result);
71    }
72}
73
74template <int inst>
75void * __malloc_alloc_template<inst>::oom_realloc(void *p, size_t n)
76{
77    void (* my_malloc_handler)();
78    void *result;
79
80    for (;;) {//不断尝试释放、分配、再释放、再分配...
81        my_malloc_handler = __malloc_alloc_oom_handler;
82        if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; }
83        (*my_malloc_handler)(); //调用处理例程，企图释放内存
84        result = realloc(p, n); //再次尝试分配内存
85        if (result) return(result);
86    }
87}

1//使用union解决free-list带来的额外负担：维护链表所必须的指针而造成内存的另一种浪费
2union obj{
3    union obj * free_list_link; //系统视角
4    char client_data[1];        //用户视角
5}

 1#ifdef __SUNPRO_CC
 2// breaks if we make these template class members:
 3  enum {__ALIGN = 8};                           //小型区块的上调边界
 4  enum {__MAX_BYTES = 128};                     //小型区块的上限
 5  enum {__NFREELISTS = __MAX_BYTES/__ALIGN};    //free-list的个数
 6#endif
 7
 8//第二级分配器的定义
 9//无”template型别参数“，第一个参数用于多线程环境，第二参数完全没派上用场
10template <bool threads, int inst>
11class __default_alloc_template {
12
13private:
14    //将bytes上调至8的倍数
15    static size_t ROUND_UP(size_t bytes) {
16        return (((bytes) + __ALIGN-1) & ~(__ALIGN - 1));
17    }
18private:
19    //free-list
20    union obj {
21        union obj * free_list_link;
22        char client_data[1];    /* The client sees this.        */
23    };
24private:
25    //16个free-list
26    static obj * volatile free_list[__NFREELISTS]; 
27    //根据区块大小，决定使用第n号free-list。n从0算起
28    static  size_t FREELIST_INDEX(size_t bytes) {
29        return (((bytes) + __ALIGN-1)/__ALIGN - 1);
30    }
31
32    //返回一个大小为n的对象，并可能加入大小为n的其它区块到free-list
33    static void *refill(size_t n);
34    //分配一大块空间，可容纳nobjs个大小为”size“的区块
35    //如果分配nobjs个区块有所不便，nobjs可能会降低
36    static char *chunk_alloc(size_t size, int &nobjs);
37
38    // Chunk allocation state.
39    static char *start_free;  //内存池起始位置。只在chunk_alloc()中变化
40    static char *end_free;    //内存池结束位置。只在chunk_alloc()中变化
41    static size_t heap_size;
42
43public:
44    static void * allocate(size_t n){ /*详述于后*/ }
45    static void deallocate(void *p, size_t n){ /*详述于后*/ }
46    static void * reallocate(void *p, size_t old_sz, size_t new_sz);
47};
48
49/*以下是static data member的定义与初始值*/
50
51template <bool threads, int inst>
52char *__default_alloc_template<threads, inst>::start_free = 0;
53
54template <bool threads, int inst>
55char *__default_alloc_template<threads, inst>::end_free = 0;
56
57template <bool threads, int inst>
58size_t __default_alloc_template<threads, inst>::heap_size = 0;
59
60template <bool threads, int inst>
61__default_alloc_template<threads, inst>::obj * volatile
62__default_alloc_template<threads, inst> ::free_list[__NFREELISTS] = 
63    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };

1template <class Iterator>
2struct iterator_traits{
3    typedef typename Iterator::iterator_category   iterator_category;
4    typedef typename Iterator::value_type          value_type;
5    typedef typename Iterator::difference_type     difference_type;
6    typedef typename Iterator::pointer             pointer;
7    typedef typename Iterator::reference           reference;
8};

 1//以C++内建的ptrdiff_t（定义于<cstddef>头文件）作为原生指针的difference type
 2
 3//针对原生指针的偏特化版本
 4template <class T>
 5struct iterator_traits<T*>{
 6    //原生指针是一种Random Access Iterator
 7    typedef random_access_iterator_tag   iterator_category;
 8    typedef T                            value_type;
 9    typedef ptrdiff_t                    difference_type;
10    typedef T*                           pointer;
11    typedef T&                           reference;
12};
13
14//针对原生pointer-to-const的偏特化版本
15template <class T>
16struct iterator_traits<const T*>{
17    //原生指针是一种Random Access Iterator
18    typedef random_access_iterator_tag   iterator_category;
19    typedef T                            value_type;
20    typedef ptrdiff_t                    difference_type;
21    typedef const T*                     pointer;
22    typedef const T&                     reference;
23};

 1//这个函数可以很方便地萃取category
 2template <class Iterator>
 3inline typename iterator_traits<Iterator>::iterator_category
 4iterator_category(const Iterator&) {
 5  typedef typename iterator_traits<Iterator>::iterator_category category;
 6  return category();
 7}
 8
 9//这个函数可以很方便地萃取distance type
10template <class Iterator>
11inline typename iterator_traits<Iterator>::difference_type*
12distance_type(const Iterator&) {
13  return static_cast<typename iterator_traits<Iterator>::difference_type*>(0);
14}
15
16//这个函数可以很方便地萃取value type
17template <class Iterator>
18inline typename iterator_traits<Iterator>::value_type*
19value_type(const Iterator&) {
20  return static_cast<typename iterator_traits<Iterator>::value_type*>(0);
21}

 1template <class Category,
 2          class T,
 3          class Distance = ptrdiff_t,
 4          class Pointer = T*,
 5          class Reference = T&>
 6struct iterator{
 7    typedef Category    iterator_category;
 8    typedef T           value_type;
 9    typedef Distance    difference_type;
10    typedef Pointer     pointer;
11    typedef Reference   reference;
12};

1template <class Item>
2struct ListIter : public std::iterator<std::forword_iterator_tag, Item>{
3    ...
4};

1struct __true_type { };
2struct __false_type { };

1template <class T,class Alloc = alloc>
2class vector{
3public:
4    typedef T               value_type;
5    typedef value_type*     iterator;   //vector的迭代器时普通指针
6...
7};

1template<class T,class Alloc = alloc>
2class vector{
3protected:
4    typedef simple_alloc<value_type,Alloc> data_allocator;
5...
6};

1template <class T>
2struct __list_node{
3    typedef void* void_pointer;
4    void_pointer prev;  //类型为void*
5    void_pointer next;
6    T data;
7};

 1template<class T, class Ref, class Ptr>
 2struct __list_iterator {
 3  typedef __list_iterator<T, T&, T*>             iterator;
 4  typedef __list_iterator<T, const T&, const T*> const_iterator;
 5  typedef __list_iterator<T, Ref, Ptr>           self;
 6
 7  typedef bidirectional_iterator_tag iterator_category;
 8  typedef T value_type;
 9  typedef Ptr pointer;
10  typedef Ref reference;
11  typedef __list_node<T>* link_type;//节点指针类型link_type
12  typedef size_t size_type;
13  typedef ptrdiff_t difference_type;
14
15  link_type node;//迭代器内部的指针，指向list的节点
16
17  __list_iterator(link_type x) : node(x) {}
18  __list_iterator() {}
19  __list_iterator(const iterator& x) : node(x.node) {}
20
21  bool operator==(const self& x) const { return node == x.node; }
22  bool operator!=(const self& x) const { return node != x.node; }
23  //对迭代器取值，取的是节点的数据值
24  reference operator*() const { return (*node).data; }
25
26#ifndef __SGI_STL_NO_ARROW_OPERATOR
27  //以下是迭代器的成员存取运算子的标准做法
28  pointer operator->() const { return &(operator*()); }
29#endif /* __SGI_STL_NO_ARROW_OPERATOR */
30
31  //对迭代器累加1，就是前进一个节点
32  self& operator++() { 
33    node = (link_type)((*node).next);
34    return *this;
35  }
36  self operator++(int) { 
37    self tmp = *this;
38    ++*this;
39    return tmp;
40  }
41
42  //对迭代器递减1，就是后退一个节点
43  self& operator--() { 
44    node = (link_type)((*node).prev);
45    return *this;
46  }
47  self operator--(int) { 
48    self tmp = *this;
49    --*this;
50    return tmp;
51  }
52};

 1template <class T, class Alloc = alloc>
 2class list {
 3protected:
 4    typedef __list_node<T> list_node;
 5public:
 6    typedef list_node* link_type;
 7
 8protected:
 9    link_type node; //只要一个指针，便可表示整个环状双向链表
10};
11
12iterator begin() { return (link_type)((*node).next); }
13iterator end() { return node; }
14size_type size() const {
15    size_type result = 0;
16    distance(begin(), end(), result);
17    return result;
18}

1template <class T, class Alloc = alloc>
2class list {
3protected:
4    typedef simple_alloc<list_node, Alloc> list_node_allocator;
5...
6};

 1template <class T, class Ref, class Ptr, size_t BufSiz>
 2struct __deque_iterator {   //未继承std::iterator
 3  typedef __deque_iterator<T, T&, T*, BufSiz>             iterator;
 4  typedef __deque_iterator<T, const T&, const T*, BufSiz> const_iterator;
 5  static size_t buffer_size() {return __deque_buf_size(BufSiz, sizeof(T)); }
 6
 7  //为继承std::iterator，所以必须自行撰写5个必要的迭代器相应类型
 8  typedef random_access_iterator_tag iterator_category; // (1)
 9  typedef T value_type;                                 // (2)
10  typedef Ptr pointer;                                  // (3)
11  typedef Ref reference;                                // (4)
12  typedef size_t size_type;
13  typedef ptrdiff_t difference_type;                    // (5)
14  typedef T** map_pointer;
15
16  typedef __deque_iterator self;
17
18  //保持与容器的联结
19  T* cur;           //此迭代器所指缓冲区中的当前元素
20  T* first;         //此迭代器所指缓冲区的头
21  T* last;          //此迭代器所指缓冲区的尾(含备用空间)
22  map_pointer node; //指向中控器map
23...
24};

 1temlate <class T,class Alloc = alloc,size_t BufSiz = 0>
 2class deque{
 3public:     //Basic types
 4    typedef T value_type;
 5    typedef value_type* pointer;
 6    typedef size_t size_type;
 7    ...
 8
 9public:
10    typedef __deque_iterator<T,T&.T*,BufSiz> iterator;  //迭代器类型
11
12protected:  //Internal typedefs
13    //元素的指针的指针
14    typedef pointer* map_pointer;
15
16protected:  //Data members
17    iterator start;         //第一个节点的迭代器
18    iterator finish;        //最后一个节点的迭代器
19
20    map_pointer map;        //指向map，map是块连续空间
21                            //其每个元素都是个指针，指向一个节点(缓冲区)
22    size_type map_size;     //map的大小，即内有多少个指针
23...
24};

1protected:
2    //专属的空间分配器，每次分配一个元素大小
3    typedef simple_alloc<value_type,Alloc> data_allocator;
4    //专属的空间分配器，每次分配一个指针大小
5    typedef simple_alloc<pointer,Alloc> map_allocator;

 1template <class T, class Sequence = deque<T> >
 2class stack {
 3  //以下__STL_NULL_TMPL_ARGS会展开为 <>
 4  friend bool operator== __STL_NULL_TMPL_ARGS (const stack&, const stack&);
 5  friend bool operator< __STL_NULL_TMPL_ARGS (const stack&, const stack&);
 6public:
 7  typedef typename Sequence::value_type value_type;
 8  typedef typename Sequence::size_type size_type;
 9  typedef typename Sequence::reference reference;
10  typedef typename Sequence::const_reference const_reference;
11protected:
12  Sequence c;   //底层容器
13public:
14  //以下完全利用Sequence c的操作，完成stack的操作
15  bool empty() const { return c.empty(); }
16  size_type size() const { return c.size(); }
17  reference top() { return c.back(); }
18  const_reference top() const { return c.back(); }
19  //deque是两头可进出，stack是后进后出
20  void push(const value_type& x) { c.push_back(x); }
21  void pop() { c.pop_back(); }
22};
23
24template <class T, class Sequence>
25bool operator==(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {
26  return x.c == y.c;
27}
28
29template <class T, class Sequence>
30bool operator<(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {
31  return x.c < y.c;
32}

1stack<int,list<int> > istack;

 1template <class T, class Sequence = deque<T> >
 2class queue {
 3  //以下__STL_NULL_TMPL_ARGS会展开为 <>
 4  friend bool operator== __STL_NULL_TMPL_ARGS (const queue& x, const queue& y);
 5  friend bool operator< __STL_NULL_TMPL_ARGS (const queue& x, const queue& y);
 6public:
 7  typedef typename Sequence::value_type value_type;
 8  typedef typename Sequence::size_type size_type;
 9  typedef typename Sequence::reference reference;
10  typedef typename Sequence::const_reference const_reference;
11protected:
12  Sequence c;   //底层容器
13public:
14  //以下完全利用Sequence c的操作，完成stack的操作
15  bool empty() const { return c.empty(); }
16  size_type size() const { return c.size(); }
17  reference front() { return c.front(); }
18  const_reference front() const { return c.front(); }
19  reference back() { return c.back(); }
20  const_reference back() const { return c.back(); }
21  //deque是两头可进出，queue是尾端进、首部出
22  void push(const value_type& x) { c.push_back(x); }
23  void pop() { c.pop_front(); }
24};
25
26template <class T, class Sequence>
27bool operator==(const queue<T, Sequence>& x, const queue<T, Sequence>& y) {
28  return x.c == y.c;
29}
30
31template <class T, class Sequence>
32bool operator<(const queue<T, Sequence>& x, const queue<T, Sequence>& y) {
33  return x.c < y.c;
34}

1queue<int,list<int> > iqueue;

 1template <class T, class Sequence = vector<T>, 
 2          class Compare = less<typename Sequence::value_type> >
 3class  priority_queue {
 4public:
 5  typedef typename Sequence::value_type value_type;
 6  typedef typename Sequence::size_type size_type;
 7  typedef typename Sequence::reference reference;
 8  typedef typename Sequence::const_reference const_reference;
 9protected:
10  Sequence c;       //底层容器
11  Compare comp;     //元素大小比较标准
12public:
13  priority_queue() : c() {}
14  explicit priority_queue(const Compare& x) :  c(), comp(x) {}
15
16  //以下用到的make_heap()、push_heap()、pop_heap()都是泛型算法
17  //构造一个priority queue，首先根据传入的迭代器区间初始化底层容器c，然后调用
18  //make_heap()使用底层容器建堆
19  template <class InputIterator>
20  priority_queue(InputIterator first, InputIterator last, const Compare& x)
21    : c(first, last), comp(x) { make_heap(c.begin(), c.end(), comp); }
22  template <class InputIterator>
23  priority_queue(InputIterator first, InputIterator last) 
24    : c(first, last) { make_heap(c.begin(), c.end(), comp); }
25
26  bool empty() const { return c.empty(); }
27  size_type size() const { return c.size(); }
28  const_reference top() const { return c.front(); }
29  void push(const value_type& x) {
30    //先利用底层容器的push_back()将新元素推入末端，再重排heap
31    __STL_TRY {
32      c.push_back(x); 
33      push_heap(c.begin(), c.end(), comp);
34    }
35    __STL_UNWIND(c.clear());
36  }
37  void pop() {
38    //从heap内取出一个元素。但不是真正弹出，而是重排heap，然后以底层容器的pop_back()
39    //取得被弹出的元素
40    __STL_TRY {
41      pop_heap(c.begin(), c.end(), comp);
42      c.pop_back();
43    }
44    __STL_UNWIND(c.clear());
45  }
46};

 1//单向链表的节点基本结构
 2struct __slist_node_base
 3{
 4    __slist_node_base *next;
 5};
 6
 7//单向链表的节点结构
 8template <class T>
 9struct __slist_node : public __slist_node_base
10{
11    T data;
12}

 1//已知某一节点prev_node，将新节点new_node插入其后
 2inline __slist_node_base* __slist_make_link(
 3    __slist_node_base *prev_node,
 4    __slist_node_base *new_node)
 5{
 6    //令new节点的下一节点为prev节点的下一节点
 7    new_node->next = prev_node->next;
 8    prev_node->next = new_node; //令prev节点的下一节点指向new节点
 9    return new_node;
10}
11
12//单向链表的大小（元素个数）
13inline size_t __slist_size(__slist_node_base *node)
14{
15    size_t result = 0;
16    for(;node != 0;node = node->next)
17        ++result;   //一个个累计
18    return result;
19}

 1//单向链表的迭代器基本结构
 2struct __slist_iterator_base
 3{
 4  typedef size_t size_type;
 5  typedef ptrdiff_t difference_type;
 6  typedef forward_iterator_tag iterator_category;   //单向
 7
 8  __slist_node_base* node;  //指向节点基本结构
 9
10  __slist_iterator_base(__slist_node_base* x) : node(x) {}
11
12  void incr() { node = node->next; }    //前进一个节点
13
14  bool operator==(const __slist_iterator_base& x) const {
15    return node == x.node;
16  }
17  bool operator!=(const __slist_iterator_base& x) const {
18    return node != x.node;
19  }
20};
21
22//单向链表的迭代器结构
23template <class T, class Ref, class Ptr>
24struct __slist_iterator : public __slist_iterator_base
25{
26  typedef __slist_iterator<T, T&, T*>             iterator;
27  typedef __slist_iterator<T, const T&, const T*> const_iterator;
28  typedef __slist_iterator<T, Ref, Ptr>           self;
29
30  typedef T value_type;
31  typedef Ptr pointer;
32  typedef Ref reference;
33  typedef __slist_node<T> list_node;
34
35  __slist_iterator(list_node* x) : __slist_iterator_base(x) {}
36  __slist_iterator() : __slist_iterator_base(0) {}
37  __slist_iterator(const iterator& x) : __slist_iterator_base(x.node) {}
38
39  reference operator*() const { return ((list_node*) node)->data; }
40  pointer operator->() const { return &(operator*()); }
41
42  self& operator++()
43  {
44    incr(); //前进一个节点
45    return *this;
46  }
47  self operator++(int)
48  {
49    self tmp = *this;
50    incr(); //前进一个节点
51    return tmp;
52  }
53};

 1typedef bool __rb_tree_color_type;
 2const __rb_tree_color_type __rb_tree_red = false;   //红色为0
 3const __rb_tree_color_type __rb_tree_black = true;  //黑色为1
 4
 5//RB-tree节点的基类
 6struct __rb_tree_node_base
 7{
 8  typedef __rb_tree_color_type color_type;
 9  typedef __rb_tree_node_base* base_ptr;
10
11  color_type color; //颜色
12  base_ptr parent;  //指向父节点的指针
13  base_ptr left;    //指向左子节点的指针
14  base_ptr right;   //指向右子节点的指针
15
16  //静态函数，获取以x为根节点的RB-tree最小节点的指针
17  static base_ptr minimum(base_ptr x)
18  {
19    while (x->left != 0) x = x->left;
20    return x;
21  }
22
23  //静态函数，获取以x为根节点的RB-tree最大节点的指针
24  static base_ptr maximum(base_ptr x)
25  {
26    while (x->right != 0) x = x->right;
27    return x;
28  }
29};
30
31//RB-tree节点类
32template <class Value>
33struct __rb_tree_node : public __rb_tree_node_base
34{
35  typedef __rb_tree_node<Value>* link_type;
36  Value value_field;    //RB-tree节点的value
37};

 1//迭代器基类
 2struct __rb_tree_base_iterator
 3{
 4  typedef __rb_tree_node_base::base_ptr base_ptr;
 5  typedef bidirectional_iterator_tag iterator_category;
 6  typedef ptrdiff_t difference_type;
 7
 8  base_ptr node;    //节点基类类型的指针，将迭代器连接到RB-tree的节点
 9
10  void increment()
11  {
12    if (node->right != 0) {//如果node右子树不为空，则找到右子树的最左子节点
13      node = node->right;
14      while (node->left != 0)
15        node = node->left;
16    }
17    else {//如果node右子树为空，则找到第一个“该节点位于其左子树”的节点
18      base_ptr y = node->parent;
19      while (node == y->right) {
20        node = y;
21        y = y->parent;
22      }
23      if (node->right != y)
24        node = y;
25    }
26  }
27
28  void decrement()
29  {
30    if (node->color == __rb_tree_red &&
31        node->parent->parent == node)//这种情况发生于node为header时（亦即node为
32      node = node->right;            //end()时）header右子节点即mostright，指向max节点
33    else if (node->left != 0) {//如果左子树不为空，则找到左子树的最右子节点
34      base_ptr y = node->left;
35      while (y->right != 0)
36        y = y->right;
37      node = y;
38    }
39    else {//如果左子树为空，则找到第一个“该节点位于其右子树”的节点
40      base_ptr y = node->parent;
41      while (node == y->left) {
42        node = y;
43        y = y->parent;
44      }
45      node = y;
46    }
47  }
48};
49
50//迭代器类
51template <class Value, class Ref, class Ptr>
52struct __rb_tree_iterator : public __rb_tree_base_iterator
53{
54  typedef Value value_type;
55  typedef Ref reference;
56  typedef Ptr pointer;
57  typedef __rb_tree_iterator<Value, Value&, Value*>             iterator;
58  typedef __rb_tree_iterator<Value, const Value&, const Value*> const_iterator;
59  typedef __rb_tree_iterator<Value, Ref, Ptr>                   self;
60  typedef __rb_tree_node<Value>* link_type; //指向RB-tree节点的指针类型
61
62  __rb_tree_iterator() {}
63  __rb_tree_iterator(link_type x) { node = x; }
64  __rb_tree_iterator(const iterator& it) { node = it.node; }
65
66  //解引用操作为获取所指RB-tree节点的value
67  reference operator*() const { return link_type(node)->value_field; }
68#ifndef __SGI_STL_NO_ARROW_OPERATOR
69  pointer operator->() const { return &(operator*()); }
70#endif /* __SGI_STL_NO_ARROW_OPERATOR */
71
72  //调用父类的increment()，函数会修改node成员，使其指向后一个RB-tree节点
73  self& operator++() { increment(); return *this; }
74  self operator++(int) {
75    self tmp = *this;
76    increment();
77    return tmp;
78  }
79    
80  //调用父类的decrement()，函数会修改node成员，使其指向前一个RB-tree节点
81  self& operator--() { decrement(); return *this; }
82  self operator--(int) {
83    self tmp = *this;
84    decrement();
85    return tmp;
86  }
87};

 1template <class Key, class Compare = less<Key>, class Alloc = alloc>
 2class set {
 3public:
 4    ...
 5    //键值和实值类型相同，比较函数也是同一个
 6    typedef Key key_type;
 7    typedef Key value_type;
 8    typedef Compare key_compare;
 9    typedef Compare value_compare;
10private:
11    ...
12    typedef rb_tree<key_type, value_type, 
13                  identity<value_type>, key_compare, Alloc> rep_type;
14    rep_type t;  // 内含一棵RB-tree，使用RB-tree来表现set
15public:
16    ...
17    //iterator定义为RB-tree的const_iterator，表示set的迭代器无法执行写操作
18    typedef typename rep_type::const_iterator iterator;
19    ...
20};

 1template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
 2class map {
 3public:
 4  typedef Key key_type;     //键值类型
 5  typedef T data_type;      //实值类型
 6  typedef T mapped_type;    
 7  typedef pair<const Key, T> value_type;    //键值对，RB-tree节点中的value类型
 8  typedef Compare key_compare;  //键值比较函数
 9
10  ...
11
12private:
13  typedef rb_tree<key_type, value_type, 
14                  select1st<value_type>, key_compare, Alloc> rep_type;
15  rep_type t;  // 内含一棵RB-tree，使用RB-tree来表现map
16public:
17  ...
18  //迭代器和set不同，允许修改实值
19  typedef typename rep_type::iterator iterator;
20  ...
21
22  //下标操作
23  T& operator[](const key_type& k) {
24    return (*((insert(value_type(k, T()))).first)).second;
25  }
26
27  //插入操作
28  pair<iterator,bool> insert(const value_type& x) { return t.insert_unique(x); }
29
30  ...
31};

1template <class Value>
2struct __hashtable_node
3{
4    __hashtable_node *next;
5    Value val;
6};

 1template <class Value, class Key, class HashFcn,
 2          class ExtractKey, class EqualKey, class Alloc>
 3struct __hashtable_iterator {
 4  typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
 5          hashtable;
 6  typedef __hashtable_iterator<Value, Key, HashFcn, 
 7                               ExtractKey, EqualKey, Alloc>
 8          iterator;
 9  typedef __hashtable_const_iterator<Value, Key, HashFcn, 
10                                     ExtractKey, EqualKey, Alloc>
11          const_iterator;
12  typedef __hashtable_node<Value> node;
13
14  typedef forward_iterator_tag iterator_category;
15  typedef Value value_type;
16  typedef ptrdiff_t difference_type;
17  typedef size_t size_type;
18  typedef Value& reference;
19  typedef Value* pointer;
20
21  node* cur;        //迭代器目前所指的节点
22  hashtable* ht;    //指向相应的hashtable
23
24  __hashtable_iterator(node* n, hashtable* tab) : cur(n), ht(tab) {}
25  __hashtable_iterator() {}
26  reference operator*() const { return cur->val; }
27  pointer operator->() const { return &(operator*()); }
28  iterator& operator++();
29  iterator operator++(int);
30  bool operator==(const iterator& it) const { return cur == it.cur; }
31  bool operator!=(const iterator& it) const { return cur != it.cur; }
32};

 1template <class V, class K, class HF, class ExK, class EqK, class A>
 2__hashtable_iterator<V, K, HF, ExK, EqK, A>&
 3__hashtable_iterator<V, K, HF, ExK, EqK, A>::operator++()
 4{
 5  const node* old = cur;
 6  cur = cur->next;  //如果存在，就是它。否则进入以下if流程
 7  if (!cur) {
 8    //根据元素值，定位出下一个bucket，其起头处就是我们的目的地
 9    size_type bucket = ht->bkt_num(old->val);
10    while (!cur && ++bucket < ht->buckets.size())
11      cur = ht->buckets[bucket];
12  }
13  return *this;
14}
15
16template <class V, class K, class HF, class ExK, class EqK, class A>
17inline __hashtable_iterator<V, K, HF, ExK, EqK, A>
18__hashtable_iterator<V, K, HF, ExK, EqK, A>::operator++(int)
19{
20  iterator tmp = *this;
21  ++*this;
22  return tmp;
23}