本章内容：
1 deque&queue和stack深度探索
2 RB-tree深度探索
3 set/multiset深度探索
4 map/multimap深度探索
1. deque&queue和stack深度探索
1.1 deque深度探索
-
deque表示双向开口容器，它模拟了一个连续的存储空间(实质表示连续分段的容器)，其中buffer和元素结点设计如下图所示：
deque容器数据存放结构
- 其中buffer表示deque的缓冲区，每个buffer可以存放多个元素结点。并且每个buffer指针存放在vector容器中。每个iterator存放四个指针:cur、first、last、node，cur表示当前数据结点的指针，first表示buffer首指针，last表示buffer的尾指针，node表示这个iterator在vector中的指针地址。
-
deque的源代码如下所示：
deque类设计
__deque_iterator设计
- deque的insert操作：
deque::insert()
insert
insert_aux实现
-
deque模拟连续空间，如下图所示：
deque的操作
deque操作符重载
deque的++和--
deque的+=和+操作
deque的-=和-操作
1.2 queue深度探索
-
queue是先进后出的容器，内部使用了容器deque的相关功能
queue示意图
queue模板类设计
1.3 stack深度探索
-
stack是先进后出的容器，内部使用了容器deque的相关功能
stack示意图
stack模板类设计
2. RB-tree深度探索
- Red-Black tree(红黑树)是一个平衡二分搜索树(balanced binary search tree)中常被使用的一种。平衡二分搜索树的特性：排列规则有利于search和insert，并保持适度的平衡—无任何结点过深。
- rb_tree提供遍历操作及iterators。
- 我们不应使用rb_tree的iterators改变元素值(因为元素有其严谨的排列规则)。编程层面(programming leve)并非阻绝此事。如此设计是正确的，因为rb_tree即将为set何map服务(作为其底部支持)。而map允许元素的data被该改变，只有元素的key才是不可被改变的。
- rb_tree提供两种insertion操作：
insert_unique()和insert_equal()：
rb_tree结构
-
rb_tree源代码
rb_tree源码
-
rb_tree的例子
使用G2.9的rb_tree例子
使用G4.9的rb_tree例子
3 set/multiset深度探索
- set/multiset以rb_tree为底层结构，因此有“元素自动排序”特性。排序的依据是key，而set/multiset元素的value和key合一：value就是key。
- set/multiset提供遍历操作及iterators。按正常规则(++ite)遍历，便能获得排序状态(sorted)。
- 我们无法使用set/multiset的iterators改变元素值(因为key有其严谨排序规则)。set/multiset的iterator是其底部的RB_tree的const-iterator就是为了禁止用户对元素的赋值。
- set元素的key必须独一无二，因此其insert()用的是rb_tree的insert_unique()。
- multiset元素的key可以重复，因此其insert()用的是rb_tree的insert_equal()。
-
容器set源代码如下所示：
set源码
4 map/multimap深度探索
- map/multimap以rb_tree为底层结构，因此有“元素自动排序”特性。排序的依据是key。
- map/multimap提供遍历操作及iterators。按正常规则(++ite)遍历，便能获得排序状态(sorted)。
- 我们无法使用map/multimap的iterators改变元素的key(因为key有其最严谨的排序规则)，但可以用它来改变元素的data。因此map/multimap内部自动将用户指定的key
- type设为const，如此便能禁止用户对元素的key赋值。
- map元素的key必须独一无二，因此其insert()用的是rb_tree的insert_unique()。
- multimap元素的key可以重复，因此其insert()用的是rb_tree的insert_equal()。
-
map容器的源代码如下图所示：
map容器源码
-
容器map，独特的operator[]，如下图所示：
map操作符[]
网友评论