C++ STL与泛型编程-第三篇

本章内容：
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源码剖析1
  
  
  deque源码剖析2
• deque的insert操作：deque<T>::insert()
  
  insert操作
  
  
  insert_aux操作

• 下面讲解deque如何模拟连续空间(全都是deque iterator的功劳)，如下图所示：

  
  
  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源代码

• 容器rb_tree的用例：

  
  
  rb_tree测试用例G2.9
  
  
  rb_tree的用例G4.9

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 operator[]