lxidea的 Boolan 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类设计
  __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操作符[]