本章內(nèi)容：
1 deque&queue和stack深度探索
2 RB-tree深度探索
3 set/multiset深度探索
4 map/multimap深度探索

1. deque&queue和stack深度探索

1.1 deque深度探索

• deque表示雙向開口容器府喳，它模擬了一個連續(xù)的存儲空間(實質(zhì)表示連續(xù)分段的容器)稿茉，其中buffer和元素結(jié)點設(shè)計如下圖所示：

  
  
  deque容器數(shù)據(jù)存放結(jié)構(gòu)
• 其中buffer表示deque的緩沖區(qū)，每個buffer可以存放多個元素結(jié)點。并且每個buffer指針存放在vector容器中扒腕。每個iterator存放四個指針:cur年扩、first慌申、last吭净、node睡汹，cur表示當(dāng)前數(shù)據(jù)結(jié)點的指針，first表示buffer首指針寂殉，last表示buffer的尾指針囚巴，node表示這個iterator在vector中的指針地址。

• deque的源代碼如下所示：

  
  
  deque類設(shè)計
  
  
  __deque_iterator設(shè)計
• deque的insert操作：deque::insert()
  
  insert
  
  
  insert_aux實現(xiàn)

• deque模擬連續(xù)空間友扰，如下圖所示：

  
  
  deque的操作
  
  
  deque操作符重載
  
  
  deque的++和--
  
  
  deque的+=和+操作
  
  
  deque的-=和-操作

1.2 queue深度探索

• queue是先進后出的容器彤叉，內(nèi)部使用了容器deque的相關(guān)功能

  
  
  queue示意圖
  
  
  queue模板類設(shè)計

1.3 stack深度探索

• stack是先進后出的容器，內(nèi)部使用了容器deque的相關(guān)功能

  
  
  stack示意圖
  
  
  stack模板類設(shè)計

2. RB-tree深度探索

• Red-Black tree(紅黑樹)是一個平衡二分搜索樹(balanced binary search tree)中常被使用的一種村怪。平衡二分搜索樹的特性：排列規(guī)則有利于search和insert秽浇，并保持適度的平衡—無任何結(jié)點過深。
• rb_tree提供遍歷操作及iterators甚负。
• 我們不應(yīng)使用rb_tree的iterators改變元素值(因為元素有其嚴(yán)謹(jǐn)?shù)呐帕幸?guī)則)柬焕。編程層面(programming leve)并非阻絕此事。如此設(shè)計是正確的梭域，因為rb_tree即將為set何map服務(wù)(作為其底部支持)斑举。而map允許元素的data被該改變，只有元素的key才是不可被改變的病涨。
• rb_tree提供兩種insertion操作：insert_unique()和insert_equal()：
  
  rb_tree結(jié)構(gòu)

• rb_tree源代碼

  
  
  rb_tree源碼

• rb_tree的例子

  
  
  使用G2.9的rb_tree例子
  
  
  使用G4.9的rb_tree例子

3 set/multiset深度探索

• set/multiset以rb_tree為底層結(jié)構(gòu)富玷，因此有“元素自動排序”特性。排序的依據(jù)是key既穆，而set/multiset元素的value和key合一：value就是key赎懦。
• set/multiset提供遍歷操作及iterators。按正常規(guī)則(++ite)遍歷幻工，便能獲得排序狀態(tài)(sorted)励两。
• 我們無法使用set/multiset的iterators改變元素值(因為key有其嚴(yán)謹(jǐn)排序規(guī)則)。set/multiset的iterator是其底部的RB_tree的const-iterator就是為了禁止用戶對元素的賦值会钝。
• set元素的key必須獨一無二伐蒋，因此其insert()用的是rb_tree的insert_unique()。
• multiset元素的key可以重復(fù)迁酸，因此其insert()用的是rb_tree的insert_equal()先鱼。

• 容器set源代碼如下所示：

  
  
  set源碼

4 map/multimap深度探索

• map/multimap以rb_tree為底層結(jié)構(gòu)，因此有“元素自動排序”特性奸鬓。排序的依據(jù)是key焙畔。
• map/multimap提供遍歷操作及iterators。按正常規(guī)則(++ite)遍歷串远，便能獲得排序狀態(tài)(sorted)宏多。
• 我們無法使用map/multimap的iterators改變元素的key(因為key有其最嚴(yán)謹(jǐn)?shù)呐判蛞?guī)則)儿惫，但可以用它來改變元素的data。因此map/multimap內(nèi)部自動將用戶指定的key
• type設(shè)為const伸但，如此便能禁止用戶對元素的key賦值肾请。
• map元素的key必須獨一無二，因此其insert()用的是rb_tree的insert_unique()更胖。
• multimap元素的key可以重復(fù)铛铁，因此其insert()用的是rb_tree的insert_equal()。

• map容器的源代碼如下圖所示：

  
  
  map容器源碼

• 容器map却妨，獨特的operator[]饵逐，如下圖所示：

  
  
  map操作符[]