關(guān)聯(lián)容器與順序容器的本質(zhì)差別在于：關(guān)聯(lián)容器通過鍵值（key）存儲和讀取元素，而順序容器則通過袁術(shù)在容器中的位置存儲和訪問元素。

1 關(guān)聯(lián)容器類型概述

關(guān)聯(lián)容器（Associative containers）支持通過鍵來高效地查找和讀取元素。兩個基本的關(guān)聯(lián)容器類型是map 和 set。標準庫提供了8個關(guān)聯(lián)容器：

• map類型通常被稱為"關(guān)聯(lián)數(shù)組"。map 的元素以鍵－值（key-value）對的形式組織：鍵用作元素在 map 中的索引，而值則表示所存儲和讀取的數(shù)據(jù)。關(guān)聯(lián)數(shù)組與普通數(shù)組類似，不同之處在于其下標不必是整數(shù)，需要通過關(guān)鍵值而非位置來查找對應值。

• set類型是簡單關(guān)鍵詞的集合，高效存儲和訪問不同的關(guān)鍵詞。set 僅包含一個鍵，并有效地支持關(guān)于某個鍵是否存在的查詢。

• 另外6個類型與map以及set類型相關(guān)，multi前綴類型支持重復的關(guān)鍵詞，unorder前綴類型是無序集合，用哈希函數(shù)組織。

2 關(guān)鍵字要求

關(guān)聯(lián)容器對其關(guān)鍵字有一些限制：

2.1 有序容器關(guān)鍵字

默認情況下，標準庫使用關(guān)鍵字類型的<運算符來比較兩個關(guān)鍵字。用戶可以提供一個自己定義的操作來替代關(guān)鍵字上的<，所提供的操作必須是嚴格弱序的。所謂嚴格弱序，必須遵序以下幾點：

• 不能同時出現(xiàn)a<= b, b<=a的情況
• 如果a<=b且b<=c，那么a<=c
• 如果存在a不小于c，c不小于等于a的情況，則a，c等價。如果a,c等價，b,c等價，則a,c等價。

2.2 無序容器關(guān)鍵字

默認情況下，使用關(guān)鍵字類型==運算符來比較元素，它們還使用一個hash<key_type>類型的對象為每個元素生成哈希值。標準庫為內(nèi)置類型，包括指針提供了哈希模板，還為string等標準庫類型定義了哈希，因此上述類型可直接定義無需容器。

當使用自定義類型定義無序容器時，我們還需要通過模板特例化，提供自己的hash模板版本。

3 pair類型

在介紹關(guān)聯(lián)容器之前，我們需要了解名為pair的標準庫類型，它定義在頭文件utility中。

一個pair保存兩個數(shù)據(jù)成員。類似容器，pair是一個用來生成特定類型的模板。創(chuàng)建一個pair時，必須提供兩個類型名，pair的數(shù)據(jù)成員將具有對應的類型。pair上定義的操作如下：

除了構(gòu)造函數(shù)，標準庫還定義了一個make_pair函數(shù)，由傳遞給它的兩個實參生成一個新的pair對象，實例如下：

pair<string, string> example;
string first, second;
example = make_pair(first, second);

提示：pair類型定義較為繁瑣，適當使用typedef可以提高編程的效率。

4 關(guān)聯(lián)容器的操作

4.1 類型操作

關(guān)聯(lián)容器支持以下類型：

set<string>::value_type v1;          //v1是string類型
set<string>::key_type v2;            //v2是string類型
map<string, int>::value_type v3;     //v3是pair<string,int>類型
map<string, int>::key_type v4;       //v4是string類型
map<string, int>::mapped_type v5;    //v5是int類型

4.2 迭代器

當解引用一個關(guān)聯(lián)容器迭代器時，我們會得到一個類型為value_type的值的引用。對map而言，這是一個pair，其first是const的關(guān)鍵字，second成員保存值。對set而言，其迭代器是const的，其關(guān)鍵字不能修改，示例如下：

map<string, int> mWordCnt;
auto m_iter = mWordCnt.begin();
//*m_iter是指向pair<tring, int>對象的引用
//iter->first是const，不能修改；只能修改其關(guān)聯(lián)的值
m_iter->first = "new key";  //錯誤
++m_iter->second;            //正確
cout << m_iter->first << " " << m_iter->second;

set<string> sNames;
auto s_iter = sNames.begin();
*s_iter = "new key";          //錯誤，關(guān)鍵字不能修改

map和set都支持用begin和end函數(shù)問出首尾迭代器，并以此進行關(guān)聯(lián)容器的遍歷。由于關(guān)鍵字是const這一特性，我們不能將關(guān)聯(lián)容器傳遞給修改或者重排容器元素的算法。在實際編程中，我們不通常不對關(guān)聯(lián)容器使用泛型算法，即使使用，也只是將其作為一個源序列，或者當做一個目標位置來存放計算結(jié)果。

4.3 添加元素

關(guān)聯(lián)容器的inset成員可以向容器中添加一個元素或者一個元素的范圍。由于map和set不包含重復的關(guān)鍵字，因此插入一個已經(jīng)存在的元素沒有任何影響。

向map添加元素

在C++11中，使用insert函數(shù)添加單個元素通常有以下四種操作方式：

map<string, int> mWordCnt;
mWordCnt.insert({ "fiset", 1 });
mWordCnt.insert(make_pair("fiset", 1));
mWordCnt.insert(pair<string, int>("fiset", 1));
mWordCnt.insert(map<string, int>::value_type("fiset", 1));  

除上述的四種方式，標準庫還支持insert某個范圍的元素。需要注意的是：在插入單個元素時，insert函數(shù)會返回一個pair，first是當前成員的迭代器，second是一個bool變量，當插入成功是返回true，如果該元素已經(jīng)存在則返回false；在插入某個范圍的元素時，函數(shù)只返回void。詳細說明如下表：

向set添加元素

同樣，可以使用insert向set容器添加元素：

set<string> sStr; // empty set
sStr.insert("the"); // sStr now has one element
sStr.insert("and"); // sStr now has two elements

另一種用法是，調(diào)用insert函數(shù)時，提供一對迭代器實參，插入其標記范圍內(nèi)所有的元素。該版本的insert函數(shù)類似于形參為一對迭代器的構(gòu)造函數(shù)——對于一個鍵，僅插入一個元素：

vector<string> vStr = { "it`s", "a", "test" };
set<string> sStr2;  // empty set
sStr2.insert(vStr.begin(), vStr.end()); // sStr2 has 3 elements

4.4 刪除元素

關(guān)聯(lián)容器定義了三個版本的erase。與順序容器一樣，我們可以通過傳遞給erase一個迭代器或者迭代器對，來刪除一個元素或者一個元素的范圍。這與添加元素十分相似，不再贅述。

關(guān)聯(lián)容器提供了一個額外的erase，它接受一個key_type參數(shù)。此版本刪除所有匹配給定關(guān)鍵詞的元素，并返回實際刪除的數(shù)量。示例如下：

vector<string> vStr = { "a", "a", "a" };
multiset<string> sStr3;  // empty set
sStr3.insert(vStr.begin(), vStr.end()); // sStr2 has 3 elements
auto nCnt = sStr3.erase("a");// nCnt  == 3

4.5 map下標

set類型不支持下標，因為set中沒有關(guān)鍵字相關(guān)聯(lián)的“值”，“值”本身就是關(guān)鍵字。我們可以對map和unordermap容器進行下標運算符以及at函數(shù)的操作。但是，不能對multi的版本進行相應操作，因為后者可能出現(xiàn)多個值與一個關(guān)鍵字對應的情況。

與其他下標運算符不同的是，如果關(guān)鍵字不再map中，會為它創(chuàng)建一個元素并插入到map中，關(guān)鍵值將進行初始化。

map<string, int> mWordCnt;
mWordCnt["basketball"] = 1;

上述代碼將會執(zhí)行如下操作：

• 在mWordCnt中查找basketball關(guān)鍵字，未找到
• 將一個新的關(guān)鍵字-值對插入mWordCnt中，關(guān)鍵字是一個const string，保存basketball，并對second進行默認初始化（int初始化為0）
• 取出新插入的元素，并將1值賦予它

另外，需要注意的是，map下標運算法返回的是mapped_type對象，但在解引用一個map迭代器時，會得到一個value_type對象。

4.6 元素訪問

find函數(shù)可以返回指向元素的迭代器，如果元素不存在，則返回尾后迭代器。count返回元素的個數(shù)，如果不需要計數(shù)，只需要知道是否存在，建議使用find，`可以減少函數(shù)工作了，提供效率。

對于multi前綴的類型，一個關(guān)鍵字可能對應多個值，其訪問通常有三種方式：

• 1. 先用count問出數(shù)量，后用find問出第一個元素的位置，最后依次遍歷

auto nCnt = mWordCnt.count("basketball");
auto iter = mWordCnt.find("c");
while (nCnt){
    cout << iter->second << endl;
    ++iter;
    --nCnt;
}

• 2. 使用lower_bound和upper_bound問出關(guān)鍵字的上下界。注意：無需容器不支持這兩個函數(shù)

multimap<string, int> mWordCnt;
for (auto beg = mWordCnt.lower_bound("basketball"),
    end = mWordCnt.upper_bound("basketball");
    beg != end; ++beg){
        cout << beg->second << endl;
}

• 3. 使用equal_range函數(shù)，該函數(shù)返回一個迭代器pair類型，first是指向第一個元素的迭代器，second指向該關(guān)鍵字尾后迭代器的值。

multimap<string, int> mWordCnt;
for (auto range = mWordCnt.equal_range("basketball"); 
    range.first != range.second; ++range.first){
        cout << range.first->second << endl;
}