RBTree
? 红黑树是一种适度平衡的二叉搜索树，排列规则有利于插入和查找，并且会自动保持平衡。没有任何分支过深。
? 是一种半线性结构，按照正常的遍历规则，得到的是排序状态(sorted)
? 不应该使用迭代器去修改元素的值，因为元素有着严谨的排列规则，编程层面上没有阻止。如此设计是正确的
? 基于红黑树的容器适配器
- set/multiset
- Map/multimap
- 两种insertion操作，对应set/multiset， map/multimap
容器RBTree
- key和data 和起来叫value
应用
gnuc 4.9
? 新版本对于容器都做了很大修改，主要呈现在类的结构上。使用了委托设计模式impl handle - body
set & multiSet
- 遍历：中序遍历 获得排序状态
- 无法使用迭代器改变元素的值，因为会改变rbtree的性质 iterator 是rbtree的const iterator，禁止user对元素赋值
set
- Set指明第一个模版参数
元素类型即可，剩下的模版参数有默认值 - set里面红黑树的模版参数-> key 就是value, 使用identity获得key
- const 迭代器，以免使用者无意中修改了key
- set的所有操作，都转化为底层的rbtree的操作，从这个角度看set是一个适配器**(container adapter)**
VC 6 中没有identity，如何使用RBTree？
map, multimap
- 无法使用迭代器去修改key，但是可以修改元素的data
- insert操作
结构 gnuc
- 从value中取得第一个元素Key -> select1st
- 注意pair的一个元素是const修饰的，放在rbtree的第二个模版参数，说明Key是不可被用户修改的。但是data可以被用户修改。
- map的迭代器就是rbtree的迭代器。
- map 不可使用 [] 下标运算符做插入操作。
- select1st是gnuc提供的
map 独特的 operator []
- 返回不大于Key的最小秩。