關聯容器不同於順序容器的是，順序容器底層用數組實現，為線性結構，而關聯容器在實現中，用到的非線性存儲方式；順序容器是通過元素在容器中的位置順序存儲和訪問元素，而關聯容器是通過鍵(key)存儲和讀取元素的。c++標准模板庫中，關聯容器有set、multiset、map、multimap。 1.底層原理 我們已經說過，關聯容器底層實現是用非線性存儲方式，那麼這種非線性存儲方式是什麼呢？答案是“紅黑樹”（RB-Tree），紅黑樹是平衡二叉樹的一種，其有以下特點： （1）所有左子樹結點的值小於等於根節點的值，右子樹節點的值大於根節點的值。 （2）沒有一個節點深度過大。 通過上面，就可以知道，關聯容器是平衡二叉樹的具體應用，因為其內部是通過鏈表的方式組織，所以在插入的時候比vector要快，比list要慢；由於其底層是平衡二叉樹，查找、插入、刪除時間復雜度都應該為O（logN。 2.set set就是一個集合，組內的元素是唯一的，並且按一定的順序排列。每個元素可以看成一個鍵或者一個值 3.multiset multiset與set的唯一區別是，支持一個鍵多次出現。 4.map map同時擁有實值(value)和鍵值(key)，其每一個元素都是pair，pair的第一個元素是鍵值，第二個元素是實值。鍵用作元素在 map 中的索引，而值則表示所存儲和讀取的數據 5.multimap map不允許兩個元素擁有相同的鍵值，而multimap允許存在重復的鍵值。 6.關聯容器的選擇 map和set的底層實現都是很RB-tree，這兩種類型的對象所包含的元素都具有不同的鍵，不允許為同一個鍵添加第二個元素。 如果一個鍵必須對應多個實例，則需使用 multimap 或 multiset，這兩種類型允許多個元素擁有相同的鍵。 關聯容器中，只有map支持下表操作。 一般來說，如果希望有效地存儲不同值的集合，那麼使用 set 容器比較合適，而 map 容器則更適用於需要存儲（乃至修改）每個鍵所關聯的值的情況
