RBTree
? 红黑树是一种适度平衡的二叉搜索树 ,排列规则有利于插入和查找,并且会自动保持平衡。没有任何分支过深。
? 是一种半线性结构,按照正常的遍历规则,得到的是排序状态(sorted)
? 不应该使用迭代器去修改元素的值,因为元素有着严谨的排列规则,编程层面上没有阻止。如此设计是正确的
? 基于红黑树的容器适配器
- set/multiset
- Map/multimap
- 两种insertion操作,对应set/multiset, map/multimap
容器RBTree
应用
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 []
|