C++ Primer 筆記-第11章 關(guān)聯(lián)容器
標(biāo)準(zhǔn)庫提供8個(gè)關(guān)聯(lián)容器：
map、set、multimap、multiset、unordered_map、unordered_set、unordered_multimap、unordered_multiset。8個(gè)容器間的不同體現(xiàn)在三個(gè)維度上：
（1）每個(gè)容器要么是一個(gè)?set、要么是一個(gè)map；
（2）要么要求不重復(fù)的關(guān)鍵字、要么允許重復(fù)關(guān)鍵字（multi）；
（3）要么按順序保存元素、要么無序保存（unordered）。
11.2 關(guān)聯(lián)容器概述
11.2.1 定義關(guān)聯(lián)容器
可以將關(guān)聯(lián)容器初始化為另一個(gè)同類型容器的拷貝。
新標(biāo)準(zhǔn)下可以對關(guān)聯(lián)容器進(jìn)行值初始化
vector<int> ivec = { 0, 1, 2 };
set<int> iset(ivec.begin(), ivec.end());
map<int, int> imap = { {0, 1}, {2, 3} };
11.2.2 關(guān)鍵字類型的要求
對于有序容器，關(guān)鍵字類型必須定義元素比較的方法。默認(rèn)情況下，標(biāo)準(zhǔn)庫使用關(guān)鍵字類型的 < 運(yùn)算符來比較兩個(gè)關(guān)鍵字。
傳遞給排序算法的可調(diào)用對象必須滿足與關(guān)聯(lián)容器中關(guān)鍵字一樣的類型要求。
可以向一個(gè)算法提供我們自己定義的比較操作，與之類似，也可以提供自己定義的操作來代替關(guān)鍵字上的 < 運(yùn)算符。所提供的操作必須在關(guān)鍵字類型上定義一個(gè)?嚴(yán)格弱序（strict weak ordering）。
嚴(yán)格弱序：可以比較任意兩個(gè)值并確定哪個(gè)更小。若任何一個(gè)都不小于另一個(gè)，則兩認(rèn)為兩個(gè)值相等。
實(shí)例化無<運(yùn)算符的類型作為關(guān)鍵字類型的關(guān)聯(lián)容器：
bool compareIsbn(const Sales_data& lhs, const Sales_data& rhs)
{?
????return lhs.isbn()
}
multiset<Sales_data, decltype(compareIsbn)*> bookstore(compareIsbn);
使用?
decltype?來指出自定義操作的類型，必須加上一個(gè)*來指出要使用一個(gè)給定函數(shù)類型的指針使用?
compareIsbn?來初始化?bookstore?對象，表示當(dāng)向容器添加元素時(shí)，通過調(diào)用?compareIsbn?來為這些元素排序可以使用?
compareIsbn?代替?&compareIsbn?作為構(gòu)造函數(shù)的參數(shù)，因?yàn)楫?dāng)我們使用一個(gè)函數(shù)名字的時(shí)候，在需要的情況下它會(huì)自動(dòng)轉(zhuǎn)化為一個(gè)指針。
11.3 關(guān)聯(lián)容器操作
關(guān)聯(lián)容器額外的類型別名：
key_type、mapped_type?和?value_type。
11.3.1 關(guān)聯(lián)容器迭代器
雖然?
set?類型同時(shí)定義了?iterator?和?const_iterator?類型，但兩種類型都只允許?只讀訪問?set?中的元素。在實(shí)際編程中，如果真要對一個(gè)關(guān)聯(lián)容器使用算法，要么是將它當(dāng)作一個(gè)源序列，要么當(dāng)作一個(gè)目的位置。
11.3.2 添加元素
由于?
map?和?set（以及對應(yīng)的無序類型）包含不重復(fù)的關(guān)鍵字，因此插入一個(gè)已存在的元素對容器沒有任何影響。insert（或?emplace）返回的值依賴于容器類型和參數(shù)。對于不包含重復(fù)關(guān)鍵字的容器，添加單一元素的?insert?和?emplace?版本返回一個(gè)?pair，pair?的?first?成員是一個(gè)迭代器，指向具有給定關(guān)鍵字的元素；second?成員是一個(gè)?bool?值，指出元素是插入成功還是已經(jīng)存在與容器中。對于允許重復(fù)關(guān)鍵字的容器，接受單個(gè)元素的?
insert?操作返回一個(gè)指向新元素的迭代器。無須返回一個(gè)?bool?值。
11.3.3 刪除元素
關(guān)聯(lián)容器提供一個(gè)額外的?
erase?操作，它接受一個(gè)?key_type?參數(shù)。此版本刪除所有匹配給定關(guān)鍵字的元素（如果存在的話），返回實(shí)際刪除的元素的數(shù)量。
11.3.4?map?的下標(biāo)操作
set?類型不支持下標(biāo)，因?yàn)?set?中沒有與關(guān)鍵字相關(guān)聯(lián)的 “值”。不能對一個(gè)?
multimap?或一個(gè)?unordered_map?進(jìn)行下標(biāo)操作，因?yàn)檫@些容器可能有多個(gè)值與一個(gè)關(guān)鍵字相關(guān)聯(lián)。使用一個(gè)不在容器中的關(guān)鍵字作為下標(biāo)，會(huì)添加一個(gè)具有此關(guān)鍵字的元素到?
map?中（同理：調(diào)用容器的at()操作，會(huì)拋出一個(gè)?out_of_range?異常）。
11.3.5 訪問元素
c.lower_bound(k)?返回一個(gè)迭代器，指向第一個(gè)關(guān)鍵字不小于?k?的元素。如果關(guān)鍵字不在容器中，則?
lower_bound?會(huì)返回關(guān)鍵字的第一個(gè)安全插入點(diǎn)-不影響容器中元素順序的插入位置。c.upper_bound(k)?返回一個(gè)迭代器，指向第一個(gè)關(guān)鍵字大于?k?的元素。如果?
lower_bound?和?upper_bound?返回相同的迭代器，則給定關(guān)鍵字不在容器中。c.equal_range(k)?返回一個(gè)迭代器?pair，表示關(guān)鍵字等于?k?的元素的范圍。若?k?不存在，?pair?的兩個(gè)成員均等于?c.end()。如果一個(gè)?
multimap?或?multiset?中有多個(gè)元素具有相同的給定關(guān)鍵字，則這些元素在容器中會(huì)相鄰存儲(chǔ)。
11.4 無序容器
新標(biāo)準(zhǔn)定義了4個(gè)?無序關(guān)聯(lián)容器（unordered associative container）。這些容器不是使用比較運(yùn)算符來組織元素，而是使用一個(gè)?哈希函數(shù)（hash function）?和關(guān)鍵字類型的?
==?運(yùn)算符。無序容器在存儲(chǔ)上組織為一個(gè)?桶（bucket）。
容器將具有一個(gè)特定哈希值的所有元素都保存在相同的桶中。如果容器允許重復(fù)關(guān)鍵字，所有具有相同關(guān)鍵字的元素也都會(huì)在同一個(gè)桶中。
無序容器的性能依賴于哈希函數(shù)的質(zhì)量和桶的數(shù)量和大小。
可以直接定義關(guān)鍵字是?內(nèi)置類型（包括指針類型）?、
string?還有?智能指針類型?的無序容器。不能直接定義關(guān)鍵字類型為自定義類型的無序容器，必須提供特定的 hash 模板版本:
// 為了能將 Sales_data 作為關(guān)鍵字，需提供函數(shù)來替代==運(yùn)算符和哈希值計(jì)算函數(shù)。
size_t hasher(const Sales_data &sd)
{
? ?return hash<string>() (sd.isbn());
}
bool eqOp(const Sales_data& lhs, const Sales_data& rhs)
{
? ?return lhs.isbn() == rhs.isbn();
}
// 使用類型別名簡化類型
using SD_multiset = unordered_multiset<Sales_data,
? ? ? ? ? ? ? ? ? ? ? ?decltype(hasher)*, decltype(eqOp)*>;
// 參數(shù)是：桶大小、哈希函數(shù)指針和相等性判斷運(yùn)算符指針
SD_multiset bookstore(42, hasher, eqOp);
