header的语义 left: 红黑树中最左节点 right：红黑树中最右节点 parent:红黑树原本实际根节点
实际的root的父节点为header
begin() : node为最左边节点的迭代器 end() : node为header的迭代器
模板参数 class _KeyOfValue, 能够通过value值提取出其对应的key _KeyOfValue()新构造一个_KeyOfValue类型的临时对象，然后调用该对象的operator()函数得到_Key,如下图程序所示
template <class _Key, class _Value, class _KeyOfValue, class _Compare, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Value) > class _Rb_tree : protected _Rb_tree_base<_Value, _Alloc>{ static const _Key& _S_key(_Link_type __x) { return _KeyOfValue()(_S_value(__x)); } }注意红黑树的的KeyOfValue的含义，Value指的是键值-实值Pair对，不是单独的实值T！！！T才是真正的实值
调用红黑树的接口，维持一颗红黑树即可
因为set要求key和value（实际上是类型T的对象p）相同，所以红黑树节点中的value域中只需要保留一份实际的类型T的对象p即可，然后通过实际的实际的类型T的对象p转化出key,然后根据key，比较key的大小来查找插入删除
template <class _Key, class _Compare, class _Alloc> class set { // requirements: __STL_CLASS_REQUIRES(_Key, _Assignable); __STL_CLASS_BINARY_FUNCTION_CHECK(_Compare, bool, _Key, _Key); public: // typedefs: typedef _Key key_type; typedef _Key value_type; typedef _Compare key_compare; typedef _Compare value_compare; private: typedef _Rb_tree<key_type, value_type, _Identity<value_type>, key_compare, _Alloc> _Rep_type; _Rep_type _M_t; // red-black tree representing set …… }class _Identity的源码 返回了传入参数的的引用
// identity is an extensions: it is not part of the standard. template <class _Tp> struct _Identity : public unary_function<_Tp,_Tp> { const _Tp& operator()(const _Tp& __x) const { return __x; } };实际的内部红黑树对应关系为
_Rb_tree< _Key => int, _Value => int, _KeyOfValue => _Identity<int> _Compare => less<int>, _Alloc => _Alloc >结合内部代码
_Compare _M_key_compare; value __v; _M_key_compare(_KeyOfValue()(__v), _S_key(__x))等效于
less<int> _M_key_compare; int __v; _M_key_compare(_Identity<int>()(__v), _S_key(__x))等效于如下过程
Created with Raphaël 2.1.0 start 调用_Identity<int>()构造一个临时对象_Identity<int> tmp 调用tmp.operator(__V),返回__v的引用，即int& __v,也即int p1 _S_key(__x)返回一个对象int p2 两者通过_M_key_compare.operator(int p1, int p2)进行比较 比较规则是按照_M_key_compare的类型less<int>来决定的 end这样配接，即把实值value的类型和键值key的类型设成一样，用value来构造新的key，然后让key按照排序插入
map的key 和 value(实际上是类型T的对象p)是不同的，所以需要在红黑树的节点的value域中保留key p1 和T p2的pair对，下次从pair对中取出对应的key，根据key的大小查找插入排序
template <class _Key, class _Tp, class _Compare, class _Alloc> class map { public: // requirements: __STL_CLASS_REQUIRES(_Tp, _Assignable); __STL_CLASS_BINARY_FUNCTION_CHECK(_Compare, bool, _Key, _Key); // typedefs: typedef _Key key_type; typedef _Tp data_type; typedef _Tp mapped_type; typedef pair<const _Key, _Tp> value_type; typedef _Compare key_compare; class value_compare : public binary_function<value_type, value_type, bool> { friend class map<_Key,_Tp,_Compare,_Alloc>; protected : _Compare comp; value_compare(_Compare __c) : comp(__c) {} public: bool operator()(const value_type& __x, const value_type& __y) const { return comp(__x.first, __y.first); } }; private: typedef _Rb_tree<key_type, value_type, _Select1st<value_type>, key_compare, _Alloc> _Rep_type; _Rep_type _M_t; // red-black tree representing map …… } // select1st and select2nd are extensions: they are not part of the standard. template <class _Pair> struct _Select1st : public unary_function<_Pair, typename _Pair::first_type> { const typename _Pair::first_type& operator()(const _Pair& __x) const { return __x.first; } };实际的内部红黑树对应关系为
_Rb_tree< _Key => string, _Value => pair<const string, int>, //map存到红黑树里面就是pair对 _KeyOfValue => _Select1st<pair<const string, int>>, _Compare => less<string>, _Alloc => _Alloc >结合内部代码 map插入代码
value_type 实际为 pair<const string, int> pair<iterator,bool> insert(const value_type& __x) { return _M_t.insert_unique(__x); }红黑树插入代码
template <class _Key, class _Value, class _KeyOfValue, class _Compare, class _Alloc> pair<typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator, bool> _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::insert_unique(const _Value& __v) { _Link_type __y = _M_header; _Link_type __x = _M_root(); bool __comp = true; while (__x != 0) { __y = __x; __comp = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)); __x = __comp ? _S_left(__x) : _S_right(__x); } iterator __j = iterator(__y); if (__comp) if (__j == begin()) return pair<iterator,bool>(_M_insert(__x, __y, __v), true); else --__j; if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v))) return pair<iterator,bool>(_M_insert(__x, __y, __v), true); return pair<iterator,bool>(__j, false); }其中关键代码为
_Compare _M_key_compare; value __v; _M_key_compare(_KeyOfValue()(__v), _S_key(__x))等效于
less<string> _M_key_compare; pair<const string, int> __v; _M_key_compare(_Select1st<pair<const string, int>>()(__v), _S_key(__x))等效于
less<string> _M_key_compare; pair<const string, int> __v; _M_key_compare(_Select1st<pair<const string, int>>().operator(__v), _S_key(__x))等效于如下过程
Created with Raphaël 2.1.0 Start _Select1st<pair<const string, int>>().operator(__v) 取出pair<const string, int> __v 的first参数，即返回__v的 first参数 const string p1 _S_key(__x)返回一个对象 const string p2 两者通过_M_key_compare.operator(const string p1, const string p2)进行比较 比较规则是按照_M_key_compare的类型less<string>来决定的 End这样的配接关系保证了，红黑树insert，erase的时候，都是按照键值Key的大小排序来操作的，也即string的相互大小比较决定了插入顺序 其他键值类型 和 实值类型 也是同样的道理。
小节 分析set和map中红黑树的模板参数KeyOfValue，发现这个类型参数是为了从存储到容器中的T类型参数中提取出期中的键值 1)set中，容器中只保存了value没有保存key,需要key的时候，从value中取出来作为key， 所以KeyOfValue的作用很简单，返回value本身即可 2)map中,容器中保存了<”key, value”>pair对，keyOfValue需要从这个pair对中取出其中的key参数，便于下一步比较操作。
iterator begin() { for (size_type __n = 0; __n < _M_buckets.size(); ++__n) if (_M_buckets[__n]) return iterator(_M_buckets[__n], this); return end(); }
bkt_num实际上是对hash_function作了一层封装,也就是说bkt_num调用了hasher类型对象的.operator函数
实际上是对保存元素中的key关键码进行hash散列，找到对应位置，存储到容器中
size_type _M_bkt_num_key(const key_type& __key, size_t __n) const { return _M_hash(__key) % __n; }
这里注意 1)hash-func类型用来对key作hash散列,STL内部只对几种常用类型做了hash-func处理，具体如下 对特定类型做偏特化处理
如果value的类型是除这些常用类型以外的特殊的对象类型p，那么hash-func就要重新自定义hash<”p”>，并重载operator(),传入参数类型为p型,在重载函数内部实现hash散列，也即先转为int数值型，然后再做散列，和const char* s一样的处理方式；
2)equal-key同理，如果key的类型是特殊的对象类型p，那么equal_to<”p”>需要用到类型p的判等处理，所以必须在类型p内部重载==号处理
