概述
C++primer對聯想容器的定義如下：
A type that holds a collection of objects that supports efficient lookup by key
實際上，和序列式容器不同，聯想容器是考關鍵字進行搜索的，它的底層實現不是簡單的順序表或鏈表，而是更加復雜的紅黑樹，這種數據結構具備順序表和鏈表的雙重優點，同時擁有很高插入效率和查詢效率。並且，與序列式容器不同的還有一點，就是無論是插入，還是刪除操作，都不會使以前已經持有的迭代器失效（當然，指向被刪除元素的迭代器除外），這主要跟它底層的數據結構的實現有關。
STL支持的聯想容器有map,set 以及 multimap,multiset。其中，map維護的是有KEY和VALUE組成的鍵值對，而set則只存儲鍵。map和set都要求鍵必須唯一，而 multimap和multiset則是它們的鍵可以不唯一的版本。
實際上，在unix和linux平台下，都有一個庫叫isc，它是C語言的一個包裝庫。許多人認為直接使用這些函數會比STL map速度快。其實不然，它們的區別不再於算法，而在於內存碎片。如果直接使用這些函數，你需要自己去new一些節點，當節點特別多， 而且進行頻繁的刪除和插入的時候，內存碎片就會存在，而STL采用自己的Allocator分配內存，以內存池的方式來管理這些內存，會大大減少內存碎 片，從而會提升系統的整體性能。有位叫Winter的前輩在自己的系統中做過測試，他把以前所有直接用isc函數的代碼替換成map，程序速度基本一致。當時間運行很長時間後（例如後台服務程序），map的優勢就會體現出來。從另外一個方面講，使用map會大大降低你的編碼難度，同時增加程序的可讀性。何樂而不為？
map
前面說過，map裡存儲的實際上是鍵值對pair,這是一個定義在utility頭文件裡的數據結構，它有兩個公共域，first和second。map是容器，而所有的容器都是可以用迭代器去訪問的，需要注意的是，迭代出來的值是pair而不是value。除了通過迭代器去訪問外，map還可以使用下標運算符，即把key當做索引，從而得到value值。例如：
[cpp]
map<string, int> my_map;
my_map["hello"] = 3;
需要注意的是，使用下標運算符去索引value，當鍵不存在時，它會利用這個鍵在這個map中插入一個新的鍵值對，對於value，所使用的是其默認構造函數。這在某些情況下會造成我們不希望看見的副作用，所以，STL同樣為我們提供了另外一種索引方式，即find函數，它返回的是與給定鍵關聯的pair的迭代器引用，當key不存在時，則返回off-the-end
iterator。如果只是想知道map中是否已經插入了指定的KEY，也可以使用另外一個函數count，它返回的是與指定key對應的pair的數量，對於map，它的返回值只有1和0兩種情況，這個函數在multimap中可能更有用。
對於插入操作，可以直接使用下標運算符，但那樣會照成對於新值的重復初始化，更有效的方式實際上是使用insert函數，與下標運算符不同的是，無論使用哪個版本的insert，如果該鍵已存在，則會添加失敗，而前者則能成功插入，並將舊值替換為新值。
set
對於set，它的使用方式基本和map相同，由於它的數據結構裡面只存有鍵，因此，它不支持下標運算符。set在某些方向和序列式容器有些相似，除了操作的效率不同外，它們之間最大的區別就是由於set要求KEY必須唯一，所以它不會重復的進行插入，如果利用一對vector的迭代器來初始化set，那麼裡面重復的值將被忽略。例如：
[cpp]
// define a vector with 20 elements, holding two copies of each number from 0 to 9
vector<int> ivec;
for (vector<int>::size_type i = 0; i != 10; ++i) {
ivec.push_back(i);
ivec.push_back(i); // duplicate copies of each number
}
// iset holds unique elements from ivec
set<int> iset(ivec.begin(), ivec.end());
cout << ivec.size() << endl; // prints 20
cout << iset.size() << endl; // prints 10
multimap和multiset
multimap和multiset實際上就是map和set的允許鍵重復的版本，它們的操作方式和它們的普通版本基本一致。當然，由於他們允許鍵重復，在一些操作上自然會有所區別。例如，對於multimap,它不能像map那樣使用下標運算符，因為它保存的不是一個單獨的值。
因為鍵值不要求唯一，所以對於multimap和multiset，insert函數總能成功的執行，並在相應鍵下添加上一個新的value（multiset只添加鍵）。需要注意的是，multimap的設計和map<key, vector>的結構並不類似，multimap只是簡單的允許重復鍵而已，也就是說，如果與某個key有三個關聯的value，那麼將會有三個pair存在，只是由於紅黑樹的有序性，它們的迭代序列是連續的而已。
