11.1關(guān)聯(lián)容器概述
關(guān)聯(lián)容器有map和set兩大類，map是關(guān)鍵字和值得映射囊卜，set是關(guān)鍵字的簡單集合娜扇，它們分別有對應(yīng)的multi(允許關(guān)鍵字重復(fù)）,unordered版本（無序容器 ）错沃，有序容器使用比較函數(shù)來比較關(guān)鍵字，從而使元素順序存儲雀瓢，所以相等元素也是連續(xù)存放的枢析，而無序容器使用關(guān)鍵字的==運(yùn)算符和一個hash <key_type>類型的對象來組織元素
11.2關(guān)聯(lián)容器對關(guān)鍵字的要求
關(guān)聯(lián)容器不支持順序容器的有關(guān)位置方面的操作，對于有序容器而言刃麸，標(biāo)準(zhǔn)庫使用關(guān)鍵字類型的<運(yùn)算符來比較兩個關(guān)鍵字醒叁，在集合類型，關(guān)鍵字類型就是元素類型泊业；在映射類型把沼，關(guān)鍵字類型是元素的第一部分的類型。替代<的函數(shù)必須在關(guān)鍵字類型上定義一個嚴(yán)格弱序吁伺。
函數(shù)必須滿足如下基本性質(zhì)：
- 任意兩個關(guān)鍵字不能同時“小于等于”對方
- 關(guān)系具有傳遞性
- 如果存在兩個關(guān)鍵字饮睬，任何一個都不”小于等于”對方，則稱它們是等價的箱蝠。等價性也必須具備傳遞性续捂。
使用形式如下：
set<string,decltype(compare)*> set_ex(compare);
decltype來獲得一個函數(shù)指針類型時，必須加上一個*來指示使用一個給定的函數(shù)類型的指針
tips:
可以使用列表初始化返回值宦搬，如返回類型是pair<int,int>,可以return {1,1};
11.3關(guān)聯(lián)容器操作
關(guān)聯(lián)容器的類型別名：
key_type:容器的關(guān)鍵字類型
mapped_type:每個關(guān)鍵字關(guān)聯(lián)的類型牙瓢；只適用于map
value_type:對于set和key_type相同，對于map间校，為pair<const key_type,mapped_type>
11.3.1 關(guān)聯(lián)容器迭代器
當(dāng)解引用一個關(guān)聯(lián)容器迭代器時矾克，會得到一個類型為value_type的之的引用，不能修改關(guān)鍵成員的值憔足。set的iterator和const_iterator都只允許只讀
11.3.2 關(guān)聯(lián)容器算法
通常不對關(guān)聯(lián)容器使用算法胁附，因?yàn)樗鼈兊年P(guān)鍵字都是const,故只能用于只讀算法，使用關(guān)聯(lián)容器定義的find方法比泛型要快
11.3.3 檢測insert的返回值
對于不允許關(guān)鍵字重復(fù)的關(guān)聯(lián)容器滓彰，insert(v)返回一個pair類型控妻，pair的first成員是指向給定元素的迭代器，second成員是一個表示是否插入成功的bool值揭绑。
insert(p,v)表示從p開始搜索新元素應(yīng)該存儲的位置,返回指向給定元素的迭代器弓候。
對于允許關(guān)鍵字重復(fù)的關(guān)聯(lián)容器，insert(v)返回指向給定元素的迭代器
11.3.4 map的下標(biāo)操作
map和unordered_map提供下標(biāo)運(yùn)算符和一個對應(yīng)的at函數(shù)他匪，使用下標(biāo)運(yùn)算符菇存，返回類型是mapped_type，如果關(guān)鍵字不在map中邦蜜，會為它創(chuàng)建一個元素插入到map中依鸥，關(guān)聯(lián)值將進(jìn)行值初始化，at函數(shù)當(dāng)關(guān)鍵字不在容器中悼沈，會拋出Out of range異常
11.3.5 訪問元素
lower_bound(k)：返回第一個不小于k的元素的迭代器
upper_bound(k)：返回第一個大于k元素的迭代器
equal_range(k): 返回一個迭代器pair,表示等于關(guān)鍵字k的元素范圍贱迟，若k不在姐扮，返回兩個end()
11.4 無序容器
無序關(guān)聯(lián)容器在存儲上使用哈希函數(shù)和關(guān)鍵字 類型的==運(yùn)算符，使用鏈地址法來解決哈希沖突关筒，同時額外提供了哈希策略來重組容器溶握。
無序容器對關(guān)鍵字類型的要求：
使用一個hash<key_type>類型的對象來生成每個元素的哈希值。標(biāo)準(zhǔn)庫提供了內(nèi)置類型包含其對應(yīng)的指針提供了hash模板蒸播，而且也包括string，
使用形式如下：
using DS_set unordered_set<string ,decltype(hash)*,decltype(equal)*>;
DS_set set_ex(bucket_count,hash,equal);
