关联式容器分为set（集合）、map（映射表）,以及两个衍生体multiset（多键集合）、multimap（多键映射表），它们的底层机制都是RB_tree（红黑树），RB_tree也是一个独立容器，只不过不对外界开放。 还有一些不在标准之内的关联式容器 所谓的关联式容器，就是每一个元素都有一个键值（key）和一个实值（value），当元素被插入到容器中时，容器内部便依照某种规则将元素放在合适的位置，所以关联式容器没有所谓的首尾元素，也就不会有push_back,push_front,pop_back，pop_front,begin,end类似这样的操作 set的键值就是实值，map的键值和实值分开
1、平衡二叉搜索树(binary search tree) 提供对数的元素搜索和插入时间，二叉搜索树元素的放置规则： （1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值； （3）左、右子树也分别为二叉排序树； 所以一直往左，到无路可走时找到最小值，反之，可找到最大值。 AVL，RB_tree，AA_tree也属于平衡二叉树的一种。
平衡树被破坏的四种插入情况： (1)、插入点位于左子节点的左子树——左左； (2)、插入点位于左子节点的右子树——左右； (3)、插入点位于右子节点的左子树——右左； (4)、插入点位于右子节点的右子树——右右； 其中(1)(4)称为“外侧”插入，使用单旋转即可调整； (3)(4)称为“内侧”插入，需要使用双旋转调整。
2、RB_tree (1)、节点不是红色就是黑色； (2)、根节点为黑色； (3)、如果节点为红，则其子节点为黑； (4)、仍一节点至NULL的任何路径，所含的黑节点数必须相同。 根据(4)新插入的新节点必为红，(3)说明新增节点的父节点必为黑 图为红黑树 红黑树的节点设计分两层，迭代器也分两层！ 节点设计
typedef bool _rb_tree_color_type; const _rb_tree_color_type _rb_tree_red = false; //红色为0 const _rb_tree_color_type _rb_tree_black = true; //黑色为1 ---------------------第一层---------------------------- struct _rb_tree_node_base { typedef _rb_tree_color_type color_type; typedef _rb_tree_node_base* base_ptr; color_type color; //节点颜色，非红即黑 base_ptr parent; //父节点 base_ptr left; //左节点 base_ptr right; //右节点 }; ------------------------第二层------------------------ template<class value> struct _rb_tree_node: public _rb_tree_node_base { typedef _rb_tree_node<value>* link_type; value value_field; //节点值 } 迭代器设计： struct _rb_tree_base_iterator { _rb_tree_node_base* node; void increment(); void decrement(); }； temlate<T,R,P>struct _rb_tree_iterator { typedef _rb_tree_node<T>* link_node; operetor*(); operator->(); operator++(); operator++(int); operator--(); operator--(int); };不论是rb_tree的节点或迭代器，都是以struct的结构完成，struct的所有成员都是public，可被外界自由取用。 在红黑树的数据结构设计中，有三笔数据实现
size_type node_count; //记录数节点数量 link_type header; //一个实现技巧，root的parent节点 Compare key_compare; //节点的大小比较标准，是个仿函数 void init() { header = get_node(); //产生一个节点空间，令header指向它 color(header) = _rb_tree_red; //颜色设置成红色来区分root root() = 0; leftmore() = header; rightmore() = header; //?? }数据结构如图所示：
RB_tree的元素操作 （1）、插入 RB_tree提供两种插入操作insert_unique( )和insert_equal( ) 前者表示插入节点的键值(key)在整数中必须独一无二,如果有相同的键值，插入操作就不会真的进行。后者键值可以重复。 返回值是个pair，第一个元素是个RB_tree迭代器，指向新增节点，第二个元素表示插入是否成功
Pair<typename rb_tree<key,value,keyofvalue,compare,Alloc>::iterator,bool>（2）、三个全局函数 任何插入操作，于节点插入完毕之后，都要做一次调整操作，将树的状态调整到符合RB_tree inline void _rb_tree_rebalance(_rb_tree_node_base* x,_rb_tree_node_base* & root) 左旋函数 inline void _rb_tree_rotate_left(_rb_tree_node_base* x,_rb_tree_node_base*& root) 右旋函数 inline void _rb_tree_rotate_right(_rb_tree_node_base* x,_rb_tree_node_base*& root)
（3）、元素搜寻find( )
template<class key,class value,class keyofvalue,class compare,class Alloc> typename rb_tree<key,value,keyofvalue,compare,Alloc>::iterator rb_tree<key,value,keyofvlaue,compare,Alloc>::find(const key& k) { link_type y = header; link_type x = root(); while(x != 0) if(!key_compare(key(x),k)) y = x; x = left(x); else x = right(x); iterator j = iterator(y); return (j == end() || key_compare(k,key(j.node)))?end():j; }