前置知识：红黑树原理 【数据结构】7.平衡搜索树（AVL树和红黑树），红黑树的平衡性有利于 search 和 insert

• 红黑树的迭代器
  • begin() 左侧
  • end() 右侧
  • 迭代顺序 5 6 7 8 10 11 12 13 15
  • 不能使用迭代器修改 Key 的值，例如将 6 改成 50 会破坏红黑树的性质

1. RB-tree

　　在g++编译器中（4.9），rbtree在 <bits/stl_tree.h> 中定义

// Key: key; Value: Key+Data; KeyOfValue: 从Value中取出Key 注意这里的Value是Key和Data结合起来传入的类
// Compare: 比较Key大小的函数
template <class Key, class Value, class KeyOfValue, class Compare, class Allocated = alloc>
class _Rb_tree {
protected:
    typedef __rb_tree_node<Value> rb_tree_node;
public:
    typedef rb_tree_node* link_type;
protected:
    size_type node_count;    // 节点元素个数
    link_type header;        // 头节点指针，包括了Value, left, right, parent
    Compare key_compare;    // key的大小比较函数
};

• 使用案例，该rbtree的key就是value，获取key的方式就是直接返回该元素
  • rbtree._M_insert_unique(5);  插入元素（无重复）
  • rbtree._M_insert_equal(5); 插入元素（可以重复），可以使用 .count(5) 计算数量

_Rb_tree<int, int, identity<int>, less<int>, alloc> rbtree;

// identity 类重载了括号，直接返回该元素本身
template <class T>
struct identity : public unary_function<T, T> {
    const T& operator()(const T& x) const { return x; }
};

// less 重载了括号，比较大小后返回元素
template <class T>
struct less : public binary_function<T, T, bool> {
    bool operator()(const T& x, const T& y) const
    { return x<y; }
};

2. set / multiset

• set 提供遍历操作以及迭代器 iterator，可以使用 ++ite 进行遍历，并且得到排序后的数据
• 无法使用迭代器修改元素值，修改值会导致破坏排序
• set insert 调用无重复插入方法，multiset insert 调用可重复插入的方法

template <class Key, class Compare = less<Key>, class Alloc = alloc>
class set {
public:
    typedef Key key_type;
    typedef Key value_type;
    typedef Compare key_compare;
    typedef Compare value_compare;
prevate:
    typedef rb_tree<key_type, value_type, identity<value_type>, key_compare, Alloc> rep_type;
    rep_type t;    // 实际存储内容的红黑树
public:
    typedef typename rep_type::const_iterator iterator;    // 从set拿迭代器拿到的是 const_iterator，避免使用者使用迭代器修改元素
    // ...
};

 2.1 typename

typedef typename rep_type::const_iterator iterator; // STL源码的写法
typedef rep_type::const_iterator iterator; // 这样存在什么问题？

　　首先看类作用域下操作符 MyClass::name 调用实际上有 3 种可能：以MyClass为例子来说，MyClass::A静态数据成员，MyClass::B静态成员函数，MyClass::C嵌套类型。由于MyClass是一个完整的定义，所以编译器完全可以推断出任意一个变量究竟是什么类型的。但还有一种可能，如果是T::name呢？

class MyClass{
    static int A;    // 静态变量A
    static int B();  // 静态成员函数B
    typedef int C;   // 嵌套类型C
}

　　以foo函数为例子，一眼看下去它的含义是定义了T类中iterator的指针并起名为iter；如果传入的是ContainsAType则完全没有问题。但如果传入的是ContainsAnotherType则会出现问题，因为在该类中定义了静态整形变量，如果有一个全局整形变量iter，则翻译后这里就会变成一个乘法表达式，二义性是不能被允许的，所以委员会引入了typename关键字

　　模板类型实例化前，并不知道它具体是哪个类型，而使用typename 可以直接告诉编译器这是一个类型，而非成员对象。

struct ContainsAType {
    struct iterator { /* ... */ }
};

struct ContainsAnotherType {
    static int iterator;
};

template <class T>
void foo() {
    T::iterator * iter;
    // ...
}

3. map / multimap

• map 提供遍历操作以及迭代器 iterator，可以使用 ++ite 遍历排序后的数据
• 无法使用迭代器修改 key，但允许修改 data（源码实现很巧妙，借用 pair<const Key, T> 实现）
• map insert 调用无重复插入方法，multimap insert 调用可重复插入方法
  • insert(pair<long, string>(1, "HelloWorld"); 插入时应该插入一个pair
  • map[5] = "Hi Five";　　// 插入 (5, "Hi Five")
  • map[5];　　// 这个比较有趣，标准规定，如果没有 Key 5, 则创建 Key 5 和 string 的默认值
  • 在multimap 不可以使用 multimap[]进行插入

template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map {
public:
    typedef Key key_type;
    typedef T data_type;
    typedef T mapped_type;
    typedef pair<const Key, T> value_type;    // value 是 const Key 和 Data 的结合
    typedef Compare key_compare;
prevate:
    typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, Alloc> rep_type;
    rep_type t;    // 实际存储内容的红黑树
public:
    typedef typename rep_type::iterator iterator;    // 因为pair中是const key, 从而实现只能修改value不能修改key
    // ...
};