關(guān)聯(lián)容器支持通過鍵來高效地查找和讀取元素，兩個基本的關(guān)聯(lián)容器類型是map和set廉沮。map的元素以鍵-值（key-value）對的形式組織：鍵用于元素在map中的索引，而值則表示所存儲和讀取的數(shù)據(jù)徐矩。set僅包含一個鍵废封，并有效地支持關(guān)于某個鍵是否存在的查詢。map可理解為字典丧蘸，set可理解為一類元素的集合。

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

一般來說刽漂，如果希望有效地存儲不同值的集合，那么使用 set 容器比較合適弟孟，而 map 容器則更適用于需要存儲（乃至修改）每個鍵所關(guān)聯(lián)的值的情況贝咙。在做某種文本處理時，可使用 set 保存要忽略的單詞拂募。而字典則是 map 的一種很好的應(yīng)用：單詞本身是鍵庭猩，而它的解釋說明則是值。

set 和 map 類型的對象所包含的元素都具有不同的鍵陈症，不允許為同一個鍵添加第二個元素蔼水。如果一個鍵必須對應(yīng)多個實例，則需使用 multimap 或 multi set录肯，這兩種類型允許多個元素?fù)碛邢嗤逆I趴腋。

1 pair類型

pair 包含兩個數(shù)據(jù)值。在創(chuàng)建 pair 對象時论咏，必須提供兩個類型名：pair 對象所包含的兩個數(shù)據(jù)成員各自對應(yīng)的類型名字优炬。如果在創(chuàng)建 pair 對象時不提供初始化式，則調(diào)用默認(rèn)構(gòu)造函數(shù)對其成員采用值初始化厅贪。也可在定義時為每個成員提供初始化式蠢护。

pair <string, int> word_count;
pair <string, string> author("James", "Joy");

pair 類型的使用相當(dāng)繁瑣，因此养涮，如果需要定義多個相同的 pair 類型對象葵硕，可考慮利用 typedef 簡化其聲明：

typedef pair<string, string> Author; 
Author joyce("James", "Joyce");

與其他標(biāo)準(zhǔn)庫類型不同，對于 pair 類单寂，可以直接訪問其數(shù)據(jù)成員：其成員都是僅有的贬芥，分別命名為 first 和 second。只需使用普通的點操作符（成員訪問標(biāo)志）即可訪問其成員：

string firstBook; 
if (author.first == "James" && author.second == "Joyce") 
    firstBook = "Stephen Hero"; 

除了構(gòu)造函數(shù)宣决，標(biāo)準(zhǔn)庫還定義了一個 make_pair 函數(shù)蘸劈，由傳遞給它的兩個實參生成一個新的 pair 對象∽鸱校可如下使用該函數(shù)創(chuàng)建新的 pair 對象威沫，并賦給已存在的 pair 對象：

pair<string, string> next_auth; 
string first, last; 
while (cin >> first >> last) { 
    next_auth = make_pair(first, last); 
} 

2 map類型

map 是鍵－值對的集合。map 類型通惩葑ǎ可理解為關(guān)聯(lián)數(shù)組（associative array）：可使用鍵作為下標(biāo)來獲取一個值棒掠，正如內(nèi)置數(shù)組類型一樣。而關(guān)聯(lián)的本質(zhì)在于元素的值與某個特定的鍵相關(guān)聯(lián)屁商，而并非通過元素在數(shù)組中的位置來獲取烟很。在使用關(guān)聯(lián)容器時，它的鍵不但有一個類型，而且還有一個相關(guān)的比較函數(shù)雾袱。默認(rèn)情況下恤筛，標(biāo)準(zhǔn)庫使用鍵類型定義的 < 操作符來實現(xiàn)鍵的比較。

2.1 map對象的定義

map的構(gòu)造函數(shù)

map 對象的元素是鍵－值對芹橡，也即每個元素包含兩個部分：鍵以及由鍵關(guān)聯(lián)的值毒坛。map 的 value_type 就反映了這個事實。該類型比前面介紹的容器所使用的元素類型要復(fù)雜得多：value_type 是存儲元素的鍵以及值的 pair 類型林说，而且鍵為 const煎殷。例如，word_count 數(shù)組的 value_type 為 pair<const string, int> 類型腿箩。

map <string,int> word_count;
word_count.insert( make_pair("James", "Joyce") );
map<string, int>::iterator map_it = word_count.begin(); 
 cout << map_it->first; 
 cout << " " << map_it->second;

2.2 給 map 添加元素

定義了 map 容器后豪直，下一步工作就是在容器中添加鍵－值元素對。該項工作可使用 insert 成員實現(xiàn)度秘；或者顶伞，先用下標(biāo)操作符獲取元素，然后給獲取的元素賦值剑梳。在這兩種情況下唆貌，一個給定的鍵只能對應(yīng)于一個元素這一事實影響了這些操作的行為。

用下標(biāo)操作符來獲取該鍵所關(guān)聯(lián)的值垢乙。如果該鍵已在容器中锨咙，則返回該鍵所關(guān)聯(lián)的值。只有在所查找的鍵不存在時追逮，map 容器才為該鍵創(chuàng)建一個新的元素酪刀，并將它插入到此 map 對象中。此時钮孵，所關(guān)聯(lián)的值采用值初始化：類類型的元素用默認(rèn)構(gòu)造函數(shù)初始化骂倘，而內(nèi)置類型的元素初始化為 0。

map<string, int> word_count; // empty map from string to int 
string word; 
while (cin >> word) 
    ++word_count[word]; 

使用下標(biāo)給 map 容器添加新元素時巴席，元素的值部分將采用值初始化历涝。通常，我們會立即為其賦值漾唉，其實就是對同一個對象進行初始化并賦值荧库。而插入元素的另一個方法是：直接使用 insert 成員，其語法更緊湊：

word_count.insert(map<string, int>::value_type("Anna", 1)); 
word_count.insert(make_pair("Anna", 1)); 

map 對象中一個給定鍵只對應(yīng)一個元素赵刑。如果試圖插入的元素所對應(yīng)的鍵已在容器中分衫，則 insert 將不做任何操作。但是般此，帶有一個鍵－值 pair 形參的 insert 版本將返回一個值：包含一個迭代器和一個 bool 值的 pair 對象蚪战，其中迭代器指向 map 中具有相應(yīng)鍵的元素牵现，而 bool 值則表示是否插入了該元素。如果該鍵已在容器中邀桑，則其關(guān)聯(lián)的值保持不變施籍，返回的 bool 值為 true。在這兩種情況下概漱，迭代器都將指向具有給定鍵的元素。

map<string, int> word_count; 
string word; 
while (cin >> word) { 
    // inserts element with key equal to word and value 1; 
    // if word already in word_count, insert does nothing 
    pair<map<string, int>::iterator, bool> ret =  
         word_count.insert(make_pair(word, 1)); 
    if (!ret.second)          // word already in word_count 
        ++ret.first->second;  // increment counter 
} 

2.3 查找并讀取 map 中的元素

不能使用下標(biāo)來查找map中的某一元素是否存在喜喂，因為如果該鍵不在 map 容器中瓤摧，那么下標(biāo)操作會插入一個具有該鍵的新元素。map 容器提供了兩個操作：count 和 find玉吁，用于檢查某個鍵是否存在而不會插入該鍵照弥。

對于 map 對象，count 成員的返回值只能是 0 或 1进副。map 容器只允許一個鍵對應(yīng)一個實例这揣，所以 count 可有效地表明一個鍵是否存在。find 操作返回指向元素的迭代器影斑，如果元素不存在给赞，則返回 end 迭代器。

int occurs = 0;
map <string, int>::iterator it = word_count.find("foobar");
if(it != wor_count.end() )
    occurs = it->second;

2.4 從 map 對象中刪除元素

從 map 對象中刪除元素

if (word_count.erase(removal_word)) 
    cout << "ok: " << removal_word << " removed\n"; 
else cout << "oops: " << removal_word << " not found!\n"; 

2.5 map 對象的迭代遍歷

與其他容器一樣矫户，map 同樣提供 begin 和 end 運算片迅，以生成用于遍歷整個容器的迭代器。例如皆辽，可如下將 map 容器 word_count 的內(nèi)容輸出：

map<string, int>::const_iterator it = word_count.begin();
while(it != word_count.end()){
    cout<< it->first <<" occurs "
            << it->second << " times " <<endl;
    ++it;
}

3 set類型

map 容器是鍵－值對的集合柑蛇，好比以人名為鍵的地址和電話號碼。相反地驱闷，set 容器只是單純的鍵的集合耻台。例如，某公司可能定義了一個名為 bad_checks 的 set 容器空另，用于記錄曾經(jīng)給本公司發(fā)空頭支票的客戶盆耽。當(dāng)只想知道一個值是否存在時，使用 set 容器是最適合的痹换。例如征字，在接收一張支票前，該公司可能想查詢 bad_checks 對象娇豫，看看該客戶的名字是否存在匙姜。

set 容器支持大部分的 map 操作，包括上面描述的構(gòu)造函數(shù)冯痢、 insert 操作氮昧、 count 和 find 操作框杜、 erase 操作等。但是袖肥， 不支持下標(biāo)操作符咪辱，而且沒有定義 mapped_type 類型。在 set 容器中椎组，value_type 不是 pair 類型油狂，而是與 key_type 相同的類型貌虾。它們指的都是 set 中存儲的元素類型灰粮。這一差別也體現(xiàn)了 set 存儲的元素僅僅是鍵高每，而沒有所關(guān)聯(lián)的值禾锤。與 map 一樣码党，set 容器存儲的鍵也必須唯一窃这，而且不能修改算撮。

vector<int> ivec;
for( vector<int>::size_type i = 0; i !=10; ++i){
    ivec.push_back(i);
    ivec.push_back(i);
}
set<int> iset(ivec.begin(), ivec.end());
cout << ivec.size() << endl;      // prints 20 
cout << iset.size() << endl;      // prints 10 

set<string> set1;
set1.insert("the");

set<int> iset2;
iset2. insert( ivec.begin(), ivec.end() );     // iset2 has 10 elements

iset.find(1);     // returns iterator that refers to the element with key == 1
iset.find(11);   // returns iterator == iset.end() 
 iset.count(1);    // returns 1 

set<int>::iterator set_it = isec.find(1);
cout<< *set_it <<endl;

正如不能修改 map 中元素的鍵部分一樣抖坪，set 中的鍵也為 const溪烤。在獲得指向 set 中某元素的迭代器后味咳，只能對其做讀操作，而不能做寫操作檬嘀。

4 multimap 和 multiset 類型

map 和 set 容器中槽驶，一個鍵只能對應(yīng)一個實例。而 multiset 和 multimap 類型則允許一個鍵對應(yīng)多個實例枪眉。例如捺檬，在電話簿中，每個人可能有單獨的電話號碼列表贸铜。在作者的文章集中堡纬，每位作者可能有單獨的文章標(biāo)題列表。multimap 和 multiset 類型與相應(yīng)的單元素版本具有相同的頭文件定義：分別是 map 和 set 頭文件蒿秦。

multimap 和 multiset 所支持的操作分別與 map 和 set 的操作相同烤镐，只有一個例外：multimap 不支持下標(biāo)運算。不能對 multimap 對象使用下標(biāo)操作棍鳖，因為在這類容器中炮叶，某個鍵可能對應(yīng)多個值。為了順應(yīng)一個鍵可以對應(yīng)多個值這一性質(zhì)渡处，map 和 multimap镜悉，或 set 和 multiset 中相同的操作都以不同的方式做出了一定的修改。在使用 multimap 或 multiset 時医瘫，對于某個鍵侣肄，必須做好處理多個值的準(zhǔn)備，而非只有單一的值醇份。

由于鍵不要求是唯一的稼锅，因此每次調(diào)用 insert 總會添加一個元素吼具。

帶有一個鍵參數(shù)的 erase 版本將刪除擁有該鍵的所有元素，并返回刪除元素的個數(shù)矩距。而帶有一個或一對迭代器參數(shù)的版本只刪除指定的元素拗盒，并返回 void 類型。

關(guān)聯(lián)容器 map 和 set 的元素是按順序存儲的锥债， multimap 和 multset 也一樣陡蝇。因此，在 multimap 和 multiset 容器中哮肚，如果某個鍵對應(yīng)多個實例毅整，則這些實例在容器中將相鄰存放。 在 multimap 和 multiset 中查找元素有三種策略绽左，而且三種策略都基于一個事實——在 multimap 中，同一個鍵所關(guān)聯(lián)的元素必然相鄰存放艇潭。

• 使用 find 和 count 操作

• lower_bound 和 upper_bound
• enual_range 函數(shù)

返回迭代器的關(guān)聯(lián)容器操作

equal_range 函數(shù)返回存儲一對迭代器的 pair 對象拼窥。如果該值存在，則 pair 對象中的第一個迭代器指向該鍵關(guān)聯(lián)的第一個實例蹋凝，第二個迭代器指向該鍵關(guān)聯(lián)的最后一個實例的下一位置鲁纠。如果找不到匹配的元素，則 pair 對象中的兩個迭代器都將指向此鍵應(yīng)該插入的位置鳍寂。

pair<authors_it, authors_it> pos = authors.equal_range(search_item); 
while (pos.first != pos.second) { 
    cout << pos.first->second << endl; 
    ++pos.first; 
}