關聯(lián)容器和順序容器的本質區(qū)別在于：關聯(lián)容器中的元素是按關鍵字來保存和訪問的，而順序容器是按它們在容器中的位置來順序保存和訪問的味咳。
- 標準庫提供8個關聯(lián)容器
按關鍵字有序保存元素：
- map
- set
- multimap
- multiset
無序集合：
- unordered_map
- unordered_set
- unordered_multimap
- unordered_multiset
其中，multi表示允許重復關鍵字檬嘀。map和multimap定義在頭文件map中槽驶；set和multiset定義在set中；無需容器定義在頭文件unordered_map和unordered_set中鸳兽。
- 一個經典的使用關聯(lián)容器的例子是單詞計數(shù)程序：
map<string,int> word_count;
string tmp;
while(cin>>tmp){
++word_count[tmp];
}
for(const auto &w:word_count){
cout<<w.first<<":"<<w.second<<endl;
}
一旦讀取完所有輸入掂铐，范圍for語句就會遍歷map，當從map中提取一個元素時揍异，會得到一個pair類型的對象全陨，它是一個模板類型，保存兩個名為first和second的公有數(shù)據(jù)成員衷掷，前者為key辱姨，后者為value。
- 上一個程序的一個合理拓展是：忽略常見單詞戚嗅，我們可以使用set保存想忽略的單詞雨涛，只對不在集合中的單詞統(tǒng)計出現(xiàn)次數(shù)：
map<string,int> word_count;
set<string> exclude={"The","But","And"};
string tmp;
while(cin>>tmp){
if(exclude.find(tmp)==exclude.end())
++word_count[tmp];
}
set的find成員返回一個迭代器。如果給定關鍵字在set中懦胞，迭代器指向該關鍵字替久。否則，find返回尾后迭代器躏尉。
- 對于有序容器蚯根，關鍵字類型必須定義元素比較的方法，默認情況下胀糜，標準庫使用關鍵字類型的<運算符來比較兩個關鍵字稼锅。當然也可以自定義比較規(guī)則：
multiset<Sales_data,decltype(compareIsbn)*> bookstore(compareIsbn);
需要提供比較操作類型（一種函數(shù)指針類型），以及在構造函數(shù)中傳入比較函數(shù)
- pair標準庫類型僚纷，定義在頭文件utility中矩距，一個pair保存兩個數(shù)據(jù)成員。pair的默認構造函數(shù)對數(shù)據(jù)成員進行值初始化怖竭，我們可以這樣初始化pair：
pair<string,string> author{"james","kevin"};
pair<int,string> student(1,"kevin");
- 關聯(lián)容器額外定義了幾個類型別名：
- key_type：關鍵字類型
- mapped_type：每個關鍵字關聯(lián)的類型
- value_type：對于set锥债，就是key_type；對于map，是pair類型
- 當解引用一個關聯(lián)容器迭代器時哮肚，我們會得到一個類型為容器的value_type的值得引用登夫。
- set的迭代器是const的 ，無論是iterator還是const_iterator允趟。而map的pair中的第一個成員也是const的恼策。
- map和set類型都支持前述的begin和end操作，對于有序關聯(lián)容器來說潮剪，按照關鍵字升序遍歷涣楷。
-
我們通常不對關聯(lián)容器使用泛型算法，關鍵字是const這一特性意味著不能將關聯(lián)容器傳遞給修改或重排容器元素的算法抗碰。對于搜索算法而言狮斗，泛型算法是順序搜索，而關聯(lián)容器內部定義的find成員根據(jù)關鍵字搜索會快得多弧蝇。
一般來說碳褒，僅在把關聯(lián)容器當作源序列或者目的位置的時候才使用泛型算法。 -
添加元素：
添加元素
// 插入一個元素到map中
word_count.insert({word,1});
word_count.insert(make_pair(word,1));
word_count.insert(pair<string,size_t>(word,1));
word_count.insert(map<string,size_t>::value_type(word,1));
- insert（或emplace）返回值依賴于容器類型和參數(shù)看疗，對于不包含重復關鍵字的容器沙峻，添加單一元素的insert和emplace返回一個pair，first成員是一個指向給定關鍵字的迭代器(即使插入失斄椒肌）摔寨，second成員是一個bool，如果插入之前key已經存在返回false盗扇，否則插入成功返回true。對于允許重復關鍵字的容器沉填，insert操作僅僅返回一個指向新元素的迭代器疗隶，沒有bool值。
-
刪除元素：
刪除元素 -
map的下標操作：
下標操作
我們不能對multi版本的map進行下標操作翼闹，因為可能有多個值相關聯(lián)斑鼻。
下標運算符在關鍵字不存在的情況下會創(chuàng)建元素并插入到map。 - 與迭代器不同猎荠，map的下標操作返回的是mapped_type而不是解引用迭代器得到的value_type坚弱。
-
查找元素：
查找元素
我們可以通過lower_bound和upper_bound找到一個關鍵字相同的序列（對于multi來說） - 新標準定義了4個無序關聯(lián)容器，這些容器不是使用比較運算符（樹）來組織元素关摇，而是使用哈希函數(shù)和關鍵字類型的==運算符荒叶。在關鍵字類型的元素沒有明顯的序關系的情況下，無序容器非常有用输虱。
無序容器無非就是一組桶些楣，除了提供與有序容器相同的操作之外，它還提供了一組管理桶的成員函數(shù)，這些成員函數(shù)允許我們查詢容器的狀態(tài)以及在必要時強制容器進行重組：
無序容器管理操作 - 默認情況下愁茁，無序容器使用關鍵字類型的==運算符來比較元素蚕钦，它們還使用一個hash<key_type>類型的對象來生成每個元素的哈希值。標準庫為內置類型（包括指針）提供了hash模板鹅很。還為一些標準庫類型嘶居，包括string和智能指針類型定義了hash。因此促煮，我們可以直接定義關鍵字是內置類型邮屁，string以及智能指針的無序容器。
- 但是污茵，我們不能直接定義關鍵字類型為自定義類型的無序容器樱报，與容器不同，不能直接使用哈希模板泞当，而必須提供我們自己的hash模板版本迹蛤。但我們可以使用類似于為有序容器重載關鍵字類型的方法提供函數(shù)代替==運算符和哈希值計算函數(shù)去實現(xiàn)同樣的效果。
