簡介
標準庫提供8個關聯(lián)容器：
-
map：關聯(lián)數(shù)組 -
set：只保存關鍵字 -
multimap：關鍵字可重復出現(xiàn)的map -
multiset：關鍵字可重復出現(xiàn)的set -
unordered_map：用哈希函數(shù)組織的map -
unordered_set：用哈希函數(shù)組織的set -
unordered_multimap：哈希組織的multimap -
unordered_multiset：哈希組織的multiset
1. 定義關聯(lián)容器
可以通過列表初始化的方式定義map或者set：
set<string> exclude = {"the", "but", "and", "or", "an", "a"};
map<string, string> authors = { {"Joyce", "James"}, {"Austen", "Jane"}, "Dickens", "Charles" }
2. 關鍵字類型的要求
對于有序容器，關鍵字類型必須定義元素比較的方法。默認情況下讥耗，標準庫使用關鍵字類型的<運算符來比較兩個關鍵字籽慢。
3. pair類型
pair定義在頭文件utility中闷煤，保存兩個數(shù)據(jù)成員：
pair<string, size_t> word_count;
pair的數(shù)據(jù)成員是public的，兩個成員分別被命名為first與seconnd，pair的操作包括：
-
pair<T1, T2> p;：兩個類型T1和T2構造了pair，執(zhí)行值初始化 -
pair<T1, T2> p(v1, v2);：first和second分別用v1和v2初始化 -
pair<T1, T2> p = {v1, v2};：作用同上 -
make_pair(v1, v2)：返回一個用v1和v2初始化的pair趟咆，類型自動推斷 -
p.first, p.second：返回p的共有數(shù)據(jù)成員 -
p1 relop p2：關系運算符<, >, <=, >=按字典序定義 -
p1 == p2, p1 != p2：當first和second分別相等時，兩個pair相等
關聯(lián)容器操作
C++中用下面這些類型表示容器關鍵字和值的類型：
-
key_type：關鍵字類型 -
mapped_type：每個關鍵字關聯(lián)的類型梅屉，僅用于map -
value_type：對于set與key_type相同值纱，對于map，為pair<const key_type, mapped_type>
1. 關聯(lián)容器迭代器
當解引用一個關聯(lián)容器迭代器時坯汤，我們會得到一個類型為容器的value_type的值：
- 對于
map是一個pair虐唠，我們不能改變first成員的const關鍵字 - 雖然
set同時定義了iterator和const_iterator類型，但這兩種類型都只允許只讀set中的元素但不能修改
使用迭代器可以遍歷map：
auto map_it = word_count.cbegin();
while (map_it != word_count.cend()) {
cout << map_it->first << " occurs "
<< map_it->second << " times" << endl;
++map_it; // 遞增迭代器, 移動到下一個元素
}
注意我們通常不對關聯(lián)容器使用泛型算法惰聂，一方面是因為關鍵字是
const這一特性意味著我們不能將關聯(lián)容器傳遞給修改或者重排容器元素的算法疆偿；另一方面雖然關聯(lián)容器可用于只讀取元素的算法咱筛，但是這類算法很多都需要搜索序列，由于關聯(lián)容器不支持通過關鍵字進行快速查找杆故，因此使用泛型搜索算法幾乎總是一個壞主意迅箩。
在實際編程中，如果我們真的要對一個關聯(lián)容器使用算法反番，要么是將它當做一個源序列沙热，要么當做一個目的位置。比如使用copy算法將元素從一個關聯(lián)容器拷貝到另一個序列罢缸，類似的可以用inserter將一個插入器綁定到一個關聯(lián)容器從而將關聯(lián)容器作為一個目的位置來調用另一個算法。
2. 添加元素
// set
vector<int> ivec = {2, 4, 6, 8, 2, 4, 6, 8};
set<int> set2; // 構造空集合
set2.insert(ivec.cbegin(), ivec.cend()); // set2包含四個元素：2, 4, 6, 8
set2.insert({1, 3, 5, 7, 1, 3, 5, 7}); // set2包含8個元素: 1, 2, 3, 4, 5, 6, 7, 8
// map使用insert的四種方法
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));
關聯(lián)容器支持的insert操作如下：
-
c.insert(v)：v是value_type類型的對象 -
c.emplace(args)：args用來構造一個元素 -
c.insert(b ,e)：b和e表示一個c::value_type類型值的迭代器范圍 -
c.insert(il)：il是初始化列表 -
c.insert(p, v)：將迭代器p作為一個提示從哪里開始搜索新元素應該存儲的位置 -
c.emplace(p, args)：同上
insert或emplace返回值依賴于容器類型和參數(shù)投队。對于不包含重復關鍵字的容器枫疆，添加單一元素的insert和emplace版本返回一個pair，其first成員是一個迭代器指向具有給定關鍵字的元素敷鸦，其second成員是一個bool值表示元素是插入成功還是已經(jīng)存在于容器中息楔。對于允許重復關鍵字的容器，接收單個元素的insert操作返回指向新元素的迭代器而不會返回bool值扒披。
3. 刪除元素
-
c.erase(k)：從c中刪除每個關鍵字為k的元素值依，返回一個size_type的值表示刪除的元素的數(shù)量 -
c.erase(p)：從c中刪除迭代器p指定的元素，返回一個指向p之后元素的迭代器 -
c.erase(b, e)：刪除迭代器對b和e所表示范圍中的元素碟案，返回e
4. map的下標操作
map和unordered_map容器提供了下標運算符和一個對應的at函數(shù)愿险。set類型因為沒有與關鍵字相關聯(lián)的“值”，因此不支持下標价说。對一個map使用下標時辆亏，如果該關鍵字不在容器中，那么會添加一個具有此關鍵字的元素到map中鳖目。
-
c[k]：返回關鍵字為k的元素扮叨，如果找不到的話則添加一個關鍵字為k的元素并對其進行值初始化 -
c.at(k)：訪問關鍵字為k的元素，如果查找不到的話拋出out_of_range異常
5. 訪問元素
在關聯(lián)容器中查找元素的操作包括：
-
c.find(k)：返回一個迭代器领迈，指向第一個關鍵字為k的元素 -
c.count(k)：返回關鍵字等于k元素的數(shù)量 -
c.lower_bound(k)：返回一個迭代器彻磁，指向第一個關鍵字不小于k的元素 -
c.upper_bound(k)：返回一個迭代器，指向第一個關鍵字大于k的元素 -
c.equal_range(k)：返回一個迭代器pair：表示關鍵字等于k的元素的范圍狸捅，如果不存在的話則pair的兩個成員都等于c.end()
在使用中我們需要注意：
- 由于在關鍵字不存在的情況下使用下標操作會在
map中插入一個新元素衷蜓，因此對于map最好用find替代下標操作 - 對于允許重復關鍵字的容器查找給定關鍵字，則可以通過
find和count打印這些相鄰存儲的元素：
string search_item("Alain de Botton"); // 要查找的作者
auto entries = authors.count(search_item); // 元素的數(shù)量
auto iter = authors.find(search_item); // 此作者的第一本書
// 通過循環(huán)遍歷該作者的書
while(entries) {
cout << iter->second << endl;
++iter;
--entries;
}
- 如果關鍵字在容器中薪贫，那么
lower_bound返回的迭代器指向第一個具有給定關鍵字的元素恍箭，upper_bound返回的迭代器指向最后一個匹配給定關鍵字的元素之后的位置。如果lower_bound和upper_bound指向同一個迭代器的話瞧省，那么說明給定的關鍵字不在容器中扯夭。
for (auto beg = authrors.lower_bound(search_item),
end = authors.upper_bound(search_item);
beg != end; ++beg)
cout << beg->second << endl;
-
equal_bound可以接受一個關鍵字并返回一個迭代器pair鳍贾。若關鍵字存在則第一個迭代器指向第一個與關鍵字匹配的元素，第二個迭代器指向最后一個匹配元素之后的位置交洗。若未找到匹配元素骑科，則這兩個迭代器都指向關鍵字可以插入的位置。
for (auto pos = authors.equal_range(search_item);
pos.first != pos.second; ++pos.first)
cout << pos.first->second << endl;
無序容器
新標準定義了4個無序關聯(lián)容器构拳，這些容器不是使用比較運算符來組織元素咆爽，而是使用一個哈希函數(shù)hash function和關鍵字類型的==運算符。
1. 管理桶
無須容器在存儲上組織為一組桶置森，每個桶保存零個或者多個元素斗埂。無序容器使用一個哈希函數(shù)將元素映射到桶。為了訪問一個元素凫海，首先計算元素的哈希值然后決定搜索哪個桶呛凶。因此，無序容器的性能依賴于哈希函數(shù)的質量和桶的大小行贪。
- 計算一個元素的哈希值和在桶中搜索通常都是很快的操作
- 如果一個桶中能夠保存了很多元素漾稀，那么查找一個特定元素就需要大量比較操作
2. 無序容器管理操作
桶接口：
-
c.bucket_count()：正在使用的桶的數(shù)目 -
c.max_bucket_count()：容器能容納的最多的桶數(shù)量 -
c.bucker_size(n)：第n個桶有幾個元素 -
c.bucket(k)：關鍵字為k的元素在哪個桶中
桶迭代：
-
local_iterator：可以用來訪問桶中元素的迭代器類型 -
const_local_iterator：桶迭代器的const版本 -
c.begin(n), c.end(n)：桶n的首元素迭代器和尾后迭代器 -
c.cbegin(n), c.cend(n)：同上，但是返回const_local_iterator
哈希策略：
-
c.local_factor()：每個桶的平均元素數(shù)量建瘫，返回float值 -
c.max_load_factor()：c試圖維護的平均桶大小崭捍，返回float值。c會在需要的時候添加新的桶啰脚，使得local_factor<=max_local_factor -
c.rehash(n)：重新存儲殷蛇，使得bucket_count>=n且bucket_count>size/max_load_factor -
c.reserve(n)：重新存儲，使得c可以保存n個元素而不必rehash
3. 無序容器對關鍵字類型的要求
默認情況下無序容器使用關鍵字類型的==運算符來比較元素拣播，還使用一個hash<key_type>類型的對象來生成每個元素的哈希值晾咪。標準庫為內置類型（包括指針）和一些標準庫類型（string和智能指針）等類型定義了hash模板。因此我們可以直接定義關鍵字是內置類型（包括指針）贮配、string和智能指針等類型的無序容器谍倦。
