1.關聯式容器定義

所謂的關聯式容器，就是有一對鍵值對（key-value），然后容器中的元素按照鍵值根據某種確定的規則自動排序。

2.各種樹型數據結構對比

（1）二叉樹：任何節點最多只允許兩個節點
（2）最大（小）堆：父節點大于（或小于）子節點，完全二叉樹
（3）二叉搜索樹（BST）：左子樹小于父節點，右子樹大于父節點。因此，從根節點一直往左走，走到無路可走就是最小值，同理得最大值
（4）AVL樹：是二叉搜索樹，要求任何節點的左右字樹高度最多相差1.單旋轉用于解決外側插入的情況（拎起根節點的左子節點）；雙旋轉（兩次單旋轉）則用于解決內側插入的情況
[單旋轉]
[雙旋轉]
（5）紅黑樹（RB-Tree）：
滿足的條件：首先是一顆二叉搜索樹
1.每個節點不是紅色就是黑色
2.根節點為黑色
3.如果節點為紅色，則子節點必須是黑色
4.任一節點至NULL的任何路徑，所含的黑節點數必須相同。
注：AVL樹和RB樹都是在二叉搜索樹的基礎上，從不同角度定義平衡條件而實現的，主要的調整操作是單旋轉和雙旋轉來解決不平衡的問題。
構建：當新節點根據二叉搜索樹的規則到達其插入點的時候卻未能符合RB樹的條件，則必須調整顏色并旋轉樹型。

3.紅黑樹實現

（1）紅黑樹的節點包括：vaule、color、left指針、right指針和parent指針
（2）SGI STL的紅黑樹實現是通過雙層節點結構和雙層迭代器結構實現的，有利于增大彈性。

（3）RB-Tree的迭代器的前進和后退操作完全依賴二叉搜索樹的節點排列法則，與紅黑無關。即前進操作就是找到排序規則的下一個數；而后退操作則是找到按照排序規則的前一個數。

4.紅黑樹的構造和內存管理

（1）RB-Tree構造的兩種方式：復制或者構造空的：構造一個頭結點，使其左右指針指向自己，并使其顏色為red

5. set實現

（1）特性：set只有一組值（既是鍵值也是實值），set會根據元素的鍵值自動排序（有序的），不允許有重復元素。注意：set的迭代器是常量迭代器，并不能通過迭代器改變set的值
(2)set以re-tree為底層實現機制

6. map實現

（1）stl pair：一對鍵值對的數據機構
（2）map的所有元素都是pair，所有元素會根據鍵值自動排序
（3）map的迭代器不可以改變map的鍵值，但是可以修改map的實值。
（4）map的底層機制也是rb-tree
注意：set和map都不允許有重復的鍵值，所以插入操作都是調用rb-tree的insert_unique來實現的。

7. multiset和multimap實現

（1）multiset與set唯一差別是它允許鍵值重復，因此其插入操作采用的是rb-tree的insert_equal實現
（2）multimap與map唯一差別是它允許鍵值重復，因此其插入操作采用的是rb-tree的insert_equal實現

8. hashtable

（1）提出的動機：為了解決無限大數組的問題，將元素映射在某個可接受的范圍之內，通過hash 函數解決映射問題。
（2）hash表實現過程中的問題及解決方法：碰撞問題（線性探測和二次探測（N+1^2,N+22）,開鏈），注意，SGI STL的hashtable實現為開鏈方法。

（3）hashtable的數據結構：vector + 單鏈表

9. hashset（hashmultiset）、hashmap（hashmultimap）

（1）以hashtable為底層機制；set有自動排序功能而哈數set沒有。
（2）hashset使用方式與set完全相同