C++primer第十一章關聯容器 11.1使用關聯容器 11.2 關聯容器概述

關聯容器和順序容器有著根本的不同：關聯容器中的元素是按關鍵字來保存和訪問的。與之相對，順序容器中的元素是按它們在容器中的位置來順序保存和訪問的。
雖然關聯容器的很多行為與順序容器相同，但其不同之處反映了關鍵字的作用
關聯容器支持高效的關鍵字查找和訪問。兩個主要的關聯容器(associative-container)類型是map和set。map中的元素是一些關鍵字-值(key-value)對：關鍵字起到索引的作用，值則表示與索引相關聯的數據。set中每個元素只包含一個關鍵字；set支持高效的關鍵字查詢操作--檢查一個給定關鍵字是否在set中。例如，在某些文本處理過程中，可以用一個set來保存想要忽略的單詞。字典則是一個很好的使用map的例子：可以將單詞作為關鍵字，將單詞釋義作為值。
標準庫提供8個關聯容器，如表11.1所示。這8個容器間的不同體現在三個維度上：每個容器
(1)或者是一個set,或者是一個map；
(2)或者要求不重復的關鍵字，或者允許重復關鍵字；
(3)按順序保存元素，或無序保存。允許重復關鍵字的容器的名字中都包含單詞multi；不保持關鍵字按順序存儲的容器的名字都以單詞unordered開頭。因此一個unordered_multi_set是一個允許重復關鍵字，元素無序保存的集合，而一個set則是一個要求無重復關鍵字，有序存儲的集合。無序容器使用哈希函數來組織元素，我們將在11.4節(第394頁)中詳細介紹有關哈希函數的更多內容。
類型map和multimap定義在頭文件map中；set和multiset定義在頭文件set中；無序容器則定義在頭文件unordered_map和unordered_set中。

11.1使用關聯容器

雖然大多數程序員都熟悉諸如vector和list這樣的數據結構，但他們中很多人從未使用過關聯數據結構。在學習標準庫關聯容器類型的詳細內容之前，我們首先來看一個如何使用這類容器的例子，這對后續學習很有幫助。
map是關鍵字-值對的集合。例如，可以將一個人的名字作為關鍵字，將其電話號碼作為值。我們稱這樣的數據結構為"將名字映射到電話號碼”。map類型通常被稱為關聯數組。關聯數組與''正常”數組類似，不同之處在于其下標不必是整數。我們通過一個關鍵字而不是位置來查找值。給定一個名字到電話號碼的map,我們可以使用一個人的名字作為下標來獲取此人的電話號碼。
與之相對，set就是關鍵字的簡單集合。當只是想知道一個值是否存在時，set是最有用的。例如，一個企業可以定義一個名為bad_checks的set來保存那些曾經開過空頭支票的人的名字。在接受一張支票之前，可以查詢bad_checks來檢查顧客的名字是否在其中。

此程序讀取輸入，報告每個單詞出現多少次。
類似順序容器，關聯容器也是模板(參見3.3節，第86頁)。為了定義一個map,我們必須指定關鍵字和值的類型。在此程序中，map保存的每個元素中，關鍵字是string類型，值是size_t類型(參見3.5.2節，第103頁)。當對word_count進行下標操作時，我們使用一個string作為下標，獲得與此string相關聯的size_t類型的計數器。while循環每次從標準輸入讀取一個單詞。它使用每個單詞對word_count進行下標操作。如果word還未在map中，下標運算符會創建一個新元素，其關鍵字為word,值為0。不管元素是否是新創建的，我們將其值加1
一旦讀取完所有輸入，范圍for語句(參見3.2.3節，第81頁)就會遍歷map,打印每個單詞和對應的計數器。當從map中提取一個元素時，會得到一個pair類型的對象，我們將在11.2.3節(第379頁)介紹它。簡單來說，pair是一個模板類型，保存兩個名為first和second的(公有)數據成員。map所使用的pair用first成員保存關鍵字，用second成員保存對應的值。因此，輸出語句的效果是打印每個單詞及其關聯的計數器。

使用 set

上一個示例程序的一個合理擴展是：忽略常見單詞，如"the", "and", "or"等。我們可以使用set保存想忽略的單詞，只對不在集合中的單詞統計出現次數：

與其他容器類似，set也是模板。為了定義一個set,必須指定其元素類型，本例中是string。與順序容器類似，可以對一個關聯容器的元素進行列表初始化（參見9.2.4節，第300頁）。集合exclude中保存了12個我們想忽略的單詞。此程序與前一個程序的重要不同是，在統計每個單詞出現次數之前，我們檢查單詞是否在忽略集合中，這是在if語句中完成的：
find調用返回一個迭代器。如果給定關鍵字在set中，迭代器指向該關鍵字。否則，find 返回尾后迭代器。在此程序中，僅當word不在exclude中時我們才更新word的計數器。

1 1 .2 關聯容器概述

關聯容器（有序的和無序的）都支持9.2節（第 294頁）中介紹的普通容器操作（列于表9.2,第 295頁）。關聯容器不支持順序容器的位置相關的操作，例如push_front 或 push_back。原因是關聯容器中元素是根據關鍵字存儲的，這些操作對關聯容器沒有意義。而且，關聯容器也不支持構造函數或插入操作這些接受一個元素值和一個數量值的操作。
除了與順序容器相同的操作之外，關聯容器還支持一些順序容器不支持的操作（參見表 11.7,第 388頁）和類型別名（參見表11.3,第 381頁）。此外，無序容器還提供一些
用來調整哈希性能的操作，我們將在11.4節（第 394頁）中介紹。關聯容器的迭代器都是雙向的（參見10.5.1節，第 365頁）。

11.2.1定義關聯容器

如前所示，當定義一個map時，必須既指明關鍵字類型又指明值類型；而定義一個set時，只需指明關鍵字類型，因為set中沒有值。每個關聯容器都定義了一個默認構造函數，它創建一個指定類型的空容器。我們也可以將關聯容器初始化為另一個同類型容器的拷貝，或是從一個值范圍來初始化關聯容器，只要這些值可以轉化為容器所需類型就可以。在新標準下，我們也可以對關聯容器進行值初始化

與以往一樣，初始化器必須能轉換為容器中元素的類型。對于set,元素類型就是關鍵字類型。
當初始化一個map時，必須提供關鍵字類型和值類型。我們將每個關鍵字-值對包圍在花括號中：{key,value}來指出它們一起構成了map中的一個元素。在每個花括號中，關鍵字是第一個元素，值是第二個。因此，authors將姓映射到名，初始化后它包含三個元素。

初始化multimap或multiset

一個map或set中的關鍵字必須是唯一的，即，對于一個給定的關鍵字，只能有一個元素的關鍵字等于它。容器multimap和multiset沒有此限制，它們都允許多個元素具有相同的關鍵字。例如，在我們用來統計單詞數量的map中，每個單詞只能有一個元素。另一方面，在一個詞典中，一個特定單詞則可具有多個與之關聯的詞義。
下面的例子展示了具有唯一關鍵字的容器與允許重復關鍵字的容器之間的區別。首先，我們將創建一個名為ivec的保存int的vector,它包含20個元素：0到9每個整數有兩個拷貝。我們將使用此vector初始化一個set和一個multiset：

即使我們用整個ivec容器來初始化iset,它也只含有10個元素：對應ivec中每個不同的元素。另一方面，miset有 20個元素，與 ivec中的元素數量一樣多。

11.2.2關鍵字類型的要求

關聯容器對其關鍵字類型有一些限制。對于無序容器中關鍵字的要求，我們將在11.4節（第 396頁）中介紹。對于有序容器map、multimap, ?set以及multiset,關鍵字類型必須定義元素比較的方法。默認情況下，標準庫使用關鍵字類型的 < 運算符來比較兩個關鍵字。在集合類型中，關鍵字類型就是元素類型；在映射類型中，關鍵字類型是元素的第一部分的類型。因此，11.2節（第 377頁）中 word_count的關鍵字類型是 string.類似的，exclude的關鍵字類型也是string。
傳遞給排序算法的可調用對象（參見10.3.1節，第344頁）必須滿足與關聯容器中關鍵字一樣的類型要求。

有序容器的關鍵字類型

可以向一個算法提供我們自己定義的比較操作（參見10.3節，第344頁），與之類似，也可以提供自己定義的操作來代替關鍵字上的<運算符。所提供的操作必須在關鍵字類型
上定義一個嚴格弱序（strictweakordering）。可以將嚴格弱序看作"小于等于”，雖然實際定義的操作可能是一個復雜的函數。無論我們怎樣定義比較函數,它必須具備如下基本性質：
兩個關鍵字不能同時“小于等于”對方；如果kl"小于等于”k2,那么k2絕不能“小于等于”kl。
如果kl“小于等于”k2,且k2“小于等于”k3,那么kl必須“小于等于”k3。
如果存在兩個關鍵字，任何一個都不"小于等于"另一個，那么我們稱這兩個關鍵字是"等價”的。如果kl“等價于”k2,且k2“等價于”k3,那么kl必須“等價于”k3
如果兩個關鍵字是等價的（即，任何一個都不“小于等于”另一個），那么容器將它們視作相等來處理。當用作map的關鍵字時，只能有一個元素與這兩個關鍵字關聯，我們可以用兩者中任意一個來訪問對應的值。

使用關鍵字類型的比較函數

用來組織一個容器中元素的操作的類型也是該容器類型的一部分。為了指定使用自定義的操作，必須在定義關聯容器類型時提供此操作的類型。如前所述，用尖括號指出要定義哪種類型的容器，自定義的操作類型必須在尖括號中緊跟著元素類型給出。
在尖括號中出現的每個類型，就僅僅是一個類型而已。當我們創建一個容器（對象）時，才會以構造函數參數的形式提供真正的比較操作（其類型必須與在尖括號中指定的類型相吻合）

此處，我們使用decltype來指出自定義操作的類型。記住，當用decltype來獲得一個函數指針類型時，必須加上一個*來指出我們要使用一個給定函數類型的指針（參見6.7節，第223頁）。用comparelsbn來初始化bookstore對象，這表示當我們向bookstore添加元素時，通過調用comparelsbn來為這些元素排序。即bookstore中的元素將按它們的ISBN成員的值排序。可以用comparelsbn代替&comparelsbn作為構造函數的參數，因為當我們使用一個函數的名字時，在需要的情況下它會自動轉化為一個指針（參見6.7節，第221頁）。當然，使用&comparelsbn的效果也是一樣的。

11.2.3pair類型

在介紹關聯容器操作之前，我們需要了解名為pair的標準庫類型，它定義在頭文件utility中。
一個pair保存兩個數據成員。類似容器，pair是一個用來生成特定類型的模板。當創建一個pair時，我們必須提供兩個類型名，pair的數據成員將具有對應的類型。兩個類型不要求一樣：

pair的默認構造函數對數據成員進行值初始化（參見3.3.1節，第 88頁）。因此，anon是一個包含兩個空string的 pair, line保存一個空string和一個空vector。 word_count中的size_t成員值為0,而 string成員被初始化為空。我們也可以為每個成員提供初始化器：
pair<string, string> author（ "James", ”Joyce”};
這條語句創建一個名為author的pair,兩個成員被初始化為"James"和"Joyce”。與其他標準庫類型不同，pair的數據成員是public的（參見7.2節，第240頁）。兩個成員分別命名為first和second。我們用普通的成員訪問符號（參見1.5.2節，第20頁）來訪問它們，例如，在第375頁的單詞計數程序的輸出語句中我們就是這么做的：
cout<<w.first << " occurs" << w.second<<（（w.second>1）?"times":"time"）<<endl;
此處，w是指向map中某個元素的引用。map的元素是pair.在這條語句中，我們首先打印關鍵字元素的first成員，接著打印計數器second成員。標準庫只定義了有限的幾個pair操作，表11.2列出了這些操作。

創建pair對象的函數

用想象有一個函數需要返回一個pair。在新標準下，我們可以對返回值進行列表初始化（參見6.3.2節，第203頁）

pair<string, int>
process（vector<string> &v）
（
/ / 處理v
if (!v.empty())
return {v.back () , v.back () .size () }; // 列表初始化
else
return pair<stringz int> () ; // 隱式構造返回值
}