---

概述及類型

關聯容器和順序容器有著根本的不同：

• 關聯容器中的元素是按關鍵字來保存和訪問的。
• 順序容器中的元素是按它們在容器中的位置來順序保存和訪問的。
• 順序容器的底層數據結構是數組、鏈表。
• 關聯容器的底層數據結構是紅黑樹（set、multimap）、哈希表等。

關聯容器支持高效的關鍵字查找和訪問。兩個主要的關聯容器（associative-container）類型是map和set：

• map中的元素是一些關鍵字-值（key-value）對。
• set中每個元素只包含一個關鍵字；

標準庫提供8個關聯容器，這8個容器間的不同體現在三個維度上：每個容器

1. 或者是一個set，或者是一個map；
2. 或者要求不重復的關鍵字，或者允許重復關鍵字；
3. 按順序保存元素，或無序保存。

特性由名字表示：

• 允許重復關鍵字的容器的名字中都包含單詞multi；
• 不保持關鍵字按順序存儲的容器的名字都以單詞unordered開頭。

因此一個unordered_multi_set是一個允許重復關鍵字，元素無序保存的集合，而一個set則是一個要求不重復關鍵字，有序存儲的集合。無序容器使用哈希函數來組織元素。

所在的頭文件：

• 類型map和multimap定義在頭文件map中；
• set和multiset定義在頭文件set中；
• 無序容器則定義在頭文件unordered_map和unordered_set中。

下表中的操作關聯容器和順序容器都支持：

---

---

map

為了高效實現 “按值訪問元素” 這個操作而設計的。

當從map中提取一個元素時，會得到一個pair類型的對象。

簡單來說，pair是一個模板類型，保存兩個名為 first 和 second 的（公有）數據成員。

---

---

set

保存特定的值（如：滿足/不滿足，忽略/不忽略）集合。

---

---

pair類型

概念

• pair是標準庫類型，定義在頭文件utility中。
• pair的數據成員是public的。兩個成員分別命名為 first 和 second。可以用成員訪問符號（.）來訪問它們。
• map的元素是pair，pair用first成員保存關鍵字，用second成員保存對應的值。

---

初始化

默認初始化

一個pair保存兩個數據成員。創建一個pair時，我們必須提供兩個類型名，但是不要求一樣：

pair的默認構造函數對數據成員進行值初始化。因此：

• anon是兩個空的string
• line保存一個空的string一個空的vector
• word_count保存一個空串和一個為0的size_t

---

提供初始化器

pair <string, string> anon = {"zhangsan", "nan"};

---

允許的操作

---

可以創建一個pair類的函數

可以利用c++11標準下，允許對返回值進行列表初始化的特性，完成這一目的：

pair<string, int>
fun(vector<string> &vs){if(!vs.empty())return {vs.back(), vs.back().size()}; // 列表初始化//返回尾元素和尾元素的大小組成的pairelsereturn pair<string,int>(); // 隱式構造返回值，返回一個空串和0構成的pair
}

也可以用make_pair來生成pair對象，pair的兩個類型來自于make_pair的參數：

return make_pair(vs.back(), v.back().size());

---

可以作為容器的類型

push_back的參數也可以寫成列表初始化的形式或者使用make_pair:

arr.push_back({s, i});
arr.push_back(make_pair(s, i));

---

---

關聯容器迭代器

概念

當解引用一個關聯容器迭代器時，會得到一個類型為容器的value_type的值的引用。

迭代器的類型：

• map：pair<關鍵字類型，值類型>::iterator
• set：set<元素值類型>::iterator

對于自定義的比較類型的set或者multiset：

set<A, decltype(compareA)*> Aset(compareA);

其迭代器類型應為：pair<關鍵字類型，自定義比較類型>::iterator

---

map的迭代器

一個map的value_type是一個pair。可以改變pair的值（即改變映射關系），但不能改變關鍵字成員的值，因為它是const的。

---

set的迭代器是const的

我們在概念中說過：當解引用一個關聯容器迭代器時，會得到一個類型為容器的value_type的值的引用。但set的value_type即使它的key_type。因此，雖然set類型同時定義了iterator和const_iterator類型，但兩種類型都只允許只讀訪問set中的元素。

與不能改變一個map元素的關鍵字一樣，一個set中的關鍵字也是const的。可以用一個set迭代器來讀取元素的值，但不能修改：

---

---

初始化

map and set

• 每個關聯容器都定義了一個默認構造函數，它創建一個指定類型的空容器。
• 可以將關聯容器初始化為另一個同類型容器的拷貝。
• 或是從一個值范圍來初始化關聯容器，只要這些值可以轉化為容器所需類型就可以。

在新標準下，我們也可以對關聯容器進行值初始化：

正如上圖所示，我們初始化map時，必須將每個關鍵字 - 值對包圍在花括號中：

（key，value）

---

multimap and multiset

一個map或set中的關鍵字必須是唯一的，即，對于一個給定的關鍵字，只能有一個元素的關鍵字等于它。容器multimap和multiset沒有此限制，它們都允許多個元素具有相同的關鍵字。

實例：

---

---

關聯容器的操作

額外的類型別名

對于set類型，key_type和value_type是一樣的——set中保存的值就是關鍵字。

在一個map中，元素是關鍵字-值對。即，每個元素是一個pair對象，包含一個關鍵字和一個關聯的值。由于我們不能改變一個元素的關鍵字，因此這些pair的關鍵字部分是const的：

---

關聯容器和算法

由上面的知識可知，set類型中的元素是const的，map中的元素是pair，其第一個成員是const的。不能通過迭代器更改set中的元素的值、以及map的關鍵字的值。也就意味著關聯容器只可用于只讀算法。

但是由于只讀算法都要搜索序列。關聯容器又不能通過關鍵字遍歷查找， 因此關聯容器定義了很多特有的搜索成員，通過給定的關鍵字直接獲取元素。

因此如果我們真要對一個關聯容器使用算法，要么將它當成一個源序列，要么將它當作一個目的位置。

---

刪除元素

刪除關鍵字的版本：對于保存不重復關鍵字的容器，erase的返回值總是0 or 1，0表示想刪除的元素并不在容器中。

---

添加元素

insert操作

insert有兩個版本，分別接受一對迭代器，或者是一個初始化器列表，這兩個版本對于一個給定的關鍵字，只有第一個帶此關鍵字的元素才被插入到容器中：

---

通過insert操作向map添加元素

對一個map進行insert操作時，必須記住元素類型是pair。

通常，對于想要插入的數據，并沒有一個現成的pair對象。可以在insert的參數列表中創建一個pair：

---

insert的返回值

insert（或emplace）返回的值依賴于容器類型和參數。對于不包含重復關鍵字的容器，添加單一元素的insert和emplace版本返回一個pair，告訴我們插入操作是否成功。pair的first成員是一個迭代器，指向具有給定關鍵字的元素；second成員是一個bool值，指出元素是插入成功還是已經存在于容器中。如果關鍵字已在容器中，則insert什么事情也不做，且返回值中的bool部分為false。如果關鍵字不存在，元素被插入容器中，且bool值為true。

---

向兩種multi容器添加元素

與map和set不同，一個multi容器中的關鍵字不必唯一，在這些類型上調用insert總會插入一個元素。返回一個指向新元素的迭代器。

---

map的下標操作

• map和unordered_map容器提供了下標運算符和一個對應的at函數。
• set類型不支持下標，因為set中沒有與關鍵字相關聯的“值”。 元素本身就是關鍵字，因此“獲取與一個關鍵字相關聯的值”的操作就沒有意義了。
• 不能對一個multimap或一個unordered_multimap進行下標操作，因為這些容器中可能有多個值與一個關鍵字相關聯。

類似我們用過的其他下標運算符，map下標運算符接受一個索引（即，一個關鍵字），獲取與此關鍵字相關聯的值。

但是，與其他下標運算符不同的是（對于其他下標運算符而言，訪問一個不存在地址/索引顯然是一個未定義的行為），如果關鍵字并不在map中，會為它創建一個元素并插入到map中，并對關聯值進行值初始化。

用一個實例來看：

將會執行如下操作：

• 在word_count中搜索關鍵字為Anna的元素，未找到。
• 將一個新的關鍵字-值對插入到word_count中。關鍵字是一個const string，保存Anna。值進行值初始化，在本例中值為0。
• 提取出新插入的元素（鍵值對），并將值1賦予它（它指的是鍵值對中的值）。

由于下標運算符可能插入一個新元素，因此只可以對非const的map使用下標操作。

---

下標操作的返回值

通常情況下，解引用一個迭代器所返回的類型與下標運算符返回的類型是一樣的（如vector和string）。但對map則不然：

• 當對一個map進行下標操作時，會獲得一個mapped_type對象；
• 當解引用一個map迭代器時，會得到一個value_type對象。

---

通過下標（[]）對map的key與value進行操作：

void add_val(map<string, vector<string>>& map, const string& key,const string& s){map[key].push_back(s);// 當map[key]對應的vector<string>存在時直接將s push_back進去// 不存在時首先創建一個空的vector<string>，再將s push_back進去
}void add_key(map<string, vector<string>>& map, const string& key) {map[key];// 當map[key]對應的vector<string>存在時只是獲取其vector，但不做任何操作// 不存在時，在容器中為key創建一個對象，進行默認初始化，構造一個空的vector//等價于：/*if(map.find(key) == map.end()){map.[key] = vector<string>();}find函數找到參數返回參數對應的迭代器，未找到返回尾迭代器。*/
}
int main(int argc, char const *argv[]) {map<string, vector<string>> map;add_key(map, "li");add_key(map, "chen");add_key(map, "jiang");add_val(map, "li", "si");add_val(map, "chen", "chouchou");add_val(map, "li", "wu");add_val(map, "chen", "bianbian");for(auto& i : map){cout << i.first << ": ";for(auto& j : i.second){cout << j << " ";}cout << endl;}return 0;
}

其實map<string, vector<string>>和multimap<string, string>起到的作用是類似的。

如果用multimap存儲的話只是不需要add_key函數了、add_value函數可以直接用insert操作。

---

訪問元素

概念

---

利用find和count進行查找

以multi容器為例，容器中如果有多個元素具有一樣的關鍵字，則這些元素在容器中會相鄰存儲。

那么想要遍歷一個關鍵字的所有元素應該這么做：

  auto countover = multi.count(key); // 關鍵詞出現的次數auto findover = multi.find(key); // 具有給定關鍵字的第一個元素while (countover--) { // 循環次數為關鍵字出現的次數cout << findover->second << endl; // 關鍵字對應的值findover++; // 后移一位元素，相同的關鍵字相鄰排列}

lower_bound和upper_bound面向迭代器

lower_bound和upper_bound返回一個范圍：

• 如果關鍵字在容器中，lower_bound返回的迭代器指向第一個具有關鍵字的元素；upper_bound返回的迭代器指向最后一個具有關鍵字的元素的后面位置。 也就是類似于begin和end迭代器組成的左閉右開區間，表示所有具有該關鍵字的元素的范圍。
• 如果關鍵字不在容器內， 由于lower_bound和upper_bound面向有序的關聯容器，因此兩者返回的迭代器相同，都指向第一個關鍵字大于k（給定關鍵字）的元素。

因此可以重寫上面的程序：

for(auto beg = multi.lower_bound(key); beg != multi.upper_bound(key); beg++){cout << beg -> second << endl;
}

---

equal_range函數

用equal_range函數重寫上面的程序：

for(auto pos = multi.equal_range(key); pos.first != pos.second; pos.first++){cout << (pos.first)->second << endl;
}

對照使用lower_bound和upper_bound的代碼，可以清晰看出來pos.first等價于beg，pos.second等價于end。返回的都是指向一個multi元素的迭代器，對其解引用會得到一個multi的value_type對象——pair，因此需要通過->來訪問second——也就是“鍵-值對”中的值。

---

下標和insert的區別、下標與find的區別

[]與insert不同，

• insert： 當map的key存在時不做任何操作；不存在時插入鍵值對。
• []： 當key存在時，用push_back將value添加進去；如果不存在，創建key然后用push_back將value添加進去。

兩者在key不存在時操作是類似的。存在時，insert維護原有鍵值對（不對容器進行更改），下標使用最新的鍵值對覆蓋原有的鍵值對（對容器進行更改）。

[]與find不同：

• []： key不存在時，構造一個元素，將其插入到容器；存在時，獲取其元素
• find： key不存在時，返回尾后迭代器；存在時，返回的迭代器指向第一次出現的關鍵字的位置

兩者在key存在時操作是類似的。不存在時，find不做更改容器的操作，下標會對容器的內容進行更改。

---

---

有序容器

關鍵字類型

有序容器使用比較函數來比較關鍵字，從而將元素按順序存儲。

對于有序容器——map、multimap、set以及multiset，關鍵字類型必須定義元素比較的方法。 默認情況下，標準庫使用關鍵字類型的<運算符來比較兩個關鍵字。在集合類型set中，關鍵字類型就是元素類型；在映射類型map中，關鍵字類型是元素的第一部分的類型。

c++11允許提供自己定義的操作來代替關鍵字上的<運算符。所提供的操作必須在關鍵字類型上定義一個嚴格弱序（strict weak ordering）。可以將嚴格弱序看作“小于等于”：

• 兩個關鍵字不能同時“小于等于”對方；如果k1“小于等于”k2，那么k2絕不能“小于等于”k1。
• 如果k1“小于等于”k2，且k2“小于等于”k3，那么k1必須“小于等于”k3。
• 如果存在兩個關鍵字，任何一個都不“小于等于”另一個，那么我們稱這兩個關鍵字是“等價”的。如果k1“等價于”k2，且k2“等價于”k3，那么k1必須“等價于”k3。

如果兩個關鍵字是等價的（即，任何一個都不“小于等于”另一個），那么容器將它們視作相等來處理。當用作map的關鍵字時，只能有一個元素與這兩個關鍵字關聯，我們可以用兩者中任意一個來訪問對應的值。

---

重載關鍵字類型代替<運算符

在定義關聯容器時，必須用尖括號指出要定義哪種類型的容器，自定義的比較類型必須在尖括號中緊跟著元素類型給出。

上面說到，可以用一個具有嚴格弱序性質的函數來起到<運算符的作用，但是函數名并不是一個類型，它僅僅只是一個名字。因此需要提供一個指向函數的指針——此時操作類型為函數指針類型。

struct A{int age;
};bool compareA(const A& a1, const A& a2){return a1.age < a2.age;
}int main(int argc, char const *argv[]) {set<A, decltype(compareA)*> Aset(compareA);return 0;
}

上例中，我們使用decltype來指出自定義操作的類型。

當用decltype來獲得一個函數指針類型時，必須加上一個*來指出我們要使用一個給定函數類型的指針。 用compareA來初始化Aset對象，這表示當我們向Aset添加元素時，通過調用compareA來為這些元素排序。即，Aset中的元素將按它們的age成員的值排序。可以用compareA代替&compareA作為構造函數的參數，因為當我們使用一個函數的名字時，在需要的情況下它會自動轉化為一個指針。 當然，使用&compareIsbn的效果也是一樣的。

用typedef定義與compareA相容的函數指針類型，然后用此類型聲明set，起到的效果和上面是一樣的：

typedef bool (*pf)(const A& , const A&);
set<A, pf> Aset2(compareA);

---

無序容器

關鍵字類型

與有序容器使用比較運算符來組織元素不同。無序容器使用關鍵字類型的==運算符來比較元素，還使用一個hash<key_type>類型的對象來生成每個元素的哈希值。

不能直接定義關鍵字類型為自定義類類型的無序容器。因為不能向容器那樣直接使用哈希模板（如 hash<string>()），必須定義我們自己的hash模板版本。

類似于有序容器重載關鍵字類型的默認比較操作。無序容器需要提供函數來替代==運算符和哈希值計算函數，格式如下（以unordered_multiset為例）：

unordered_multiset<類型名， 重載的哈希函數， 重載的==運算符>

---

管理桶

無序容器在存儲上組織為一組桶，每個桶保存零個或多個元素。無序容器使用一個哈希函數將元素映射到桶。為了訪問一個元素，容器首先計算元素的哈希值，它指出應該搜索哪個桶。容器將具有一個特定哈希值的所有元素都保存在相同的桶中。如果容器允許重復關鍵字，所有具有相同關鍵字的元素也都會在同一個桶中。因此，無序容器的性能依賴于哈希函數的質量和桶的數量和大小。

不同關鍵字的元素映射到相同的桶也是允許的。當一個桶保存多個元素時，需要順序搜索這些元素來查找我們想要的那個。計算一個元素的哈希值和在桶中搜索通常都是很快的操作。但是，如果一個桶中保存了很多元素，那么查找一個特定元素就需要大量比較操作。

---

關鍵字相同的元素相鄰存儲

不論在有序容器還是無序容器中，具有相同關鍵字的元素都是相鄰存儲的。