11.3關聯容器操作

除了表9.2(第295頁)中列出的類型，關聯容器還定義了表11.3中列出的類型。這些類型表示容器關鍵字和值的類型。

對于set類型，key_type和value type是一樣的；set中保存的值就是關鍵字。
在一個map中，元素是關鍵字_值對。即每個元素是一個pair對象，包含一個關鍵字和一個關聯的值。由于我們不能改變一個元素的關鍵字，因此這些pai匕的關鍵字部分是const的：

與順序容器一樣(參見9.2.2節，第297頁)，我們使用作用域運算符來提取一個類型的成員----例如，map<stringf int>: :key_type
只有 map 類型 (unordered_map 、unordered_multimap、?multimap 和 map)才定義了 mapped_type

11.3.1關聯容器迭代器

當解引用一個關聯容器迭代器時，我們會得到一個類型為容器的value_type的值的引用。對 map而言，value_type是一個pair類型，其 first成員保存const的關鍵字，second成員保存值：
/ / 獲得指向word_count中一個元素的迭代器
auto map_it = word_count.begin(); // *map_it 是指向一個 pair<const string, size_t>對象的引用
cout ? map_it->first; / / 打印此元素的關鍵字
cout ? " ” ? map_it->second; // 打印此元素的值
map_it->first = "new key"; // 錯誤：關鍵字是 const 的
++map_it->second; / / 正確：我們可以通過迭代器改變元素
必須記住，一個map的value_type是一個pair,我們可以改變pair的值，但不能改變關鍵字成員的數值

set的迭代器是const的

雖然set類型同時定義了 iterator和 const_iterator類型，但兩種類型都只允許只讀訪問set中的元素。與不能改變一個map元素的關鍵字一樣，一個set中的關鍵字也是const的。可以用一個set迭代器來讀取元素的值，但不能修改：

遍歷關聯容器

map和set類型都支持表9.2(第295頁)中的begin和end操作。與往常一樣，我們可以用這些函數獲取迭代器，然后用迭代器來遍歷容器。例如，我們可以編寫一個循環來打印第375頁中單詞計數程序的結果，如下所示

while的循環條件和循環中的迭代器遞增操作看起來很像我們之前編寫的打印一個vector或一個string的程序。我們首先初始化迭代器map_it,讓它指向word_count中的首元素。只要迭代器不等于end,就打印當前元素并遞增迭代器。輸出語句解引用map_it 來獲得pair的成員，否則與我們之前的程序一樣。
本程序的輸出是按字典序排列的。當使用一個迭代器遍歷一個map、multimap、set或 multiset時，迭代器按關鍵字升序遍歷元素，

關聯容器和算法

我們通常不對關聯容器使用泛型算法(參見第10章)。關鍵字是const這一特性意味著不能將關聯容器傳遞給修改或重排容器元素的算法，因為這類算法需要向元素寫入值，而 set類型中的元素是const的，map中的元素是pair,其第一個成員是const的。關聯容器可用于只讀取元素的算法。但是，很多這類算法都要搜索序列。由于關聯容器中的元素不能通過它們的關鍵字進行(快速)查找，因此對其使用泛型搜索算法幾乎總是個壞主意。例如，我們將在11.3.5節 (第 388頁)中看到，關聯容器定義了一個名為find的成員，它通過一個給定的關鍵字直接獲取元素。我們可以用泛型find算法來查找一個元素，但此算法會進行順序搜索。使用關聯容器定義的專用的find成員會比調用泛型find快得多。
在實際編程中，如果我們真要對一個關聯容器使用算法，要么是將它當作一個源序列，要么當作一個目的位置。例如，可以用泛型copy算法將元素從一個關聯容器拷貝到另一個序列。類似的，可以調用inserter將一個插入器綁定(參見10.4.1節，第 358頁) 到一個關聯容器。通過使用inserter,我們可以將關聯容器當作一個目的位置來調用另一個算法。

11.3.2添加元素

關聯容器的insert成員(見表1L4,第 384頁)向容器中添加一個元素或一個元素范圍。由于map和 set (以及對應的無序類型)包含不重復的關鍵字，因此插入一個已存在的元素對容器沒有任何影響:

insert有兩個版本，分別接受一對迭代器，或是一個初始化器列表，這兩個版本的行為類似對應的構造函數(參見11.2.1節，第 376頁 )—— 對于一個給定的關鍵字，只有第一個帶此關鍵字的元素才被插入到容器中。

向 map添加元素

對一個map進行insert操作時，必須記住元素類型是pair。通常，對于想要插入的數據，并沒有一個現成的pair對象。可以在insert的參數列表中創建一個pair：

如我們所見，在新標準下，創建一個pair最簡單的方法是在參數列表中使用花括號初始化。也可以調用make_pair或顯式構造pair。?最后一個insert調用中的參數：
map<string, size_t>::value_type(s, 1)
構造一個恰當的pair類型，并構造該類型的一個新對象，插入到map中。

檢測 insert的返回值

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

展開遞增語句

在這個版本的單詞計數程序中，遞增計數器的語句很難理解。通過添加一些括號來反映出運算符的優先級(參見4.1.2節，第 121頁)，會使表達式更容易理解一些：
++ ( (ret. first) ->second) ; // 等價的表達式
下面我們一步一步來解釋此表達式：

向 multiset或 multimap添加元素

我們的單詞計數程序依賴于這樣一個事實：一個給定的關鍵字只能出現一次。這樣，任意給定的單詞只有一個關聯的計數器。我們有時希望能添加具有相同關鍵字的多個元素。例如，可能想建立作者到他所著書籍題目的映射。在此情況下，每個作者可能有多個條目，因此我們應該使用multimap而不是map。由于一個multi容器中的關鍵字不必唯一，在這些類型上調用insert總會插入一個元素

11 .3 .3 刪除元素

關聯容器定義了三個版本的erase,如表11.5所示。與順序容器一樣，我們可以通過傳遞給erase 一個迭代器或一個迭代器對來刪除一個元素或者一個元素范圍。這兩個版本的erase與對應的順序容器的操作非常相似：指定的元素被刪除，函數返回void。關聯容器提供一個額外的erase操作，它接受一個key_type參數。此版本刪除所有匹配給定關鍵字的元素(如果存在的話)，返回實際刪除的元素的數量。我們可以用此版本在打印結果之前從word_count中刪除一個特定的單詞：

對于保存不重復關鍵字的容器，erase的返回值總是0或 1。若返回值為0,則表明想要刪除的元素并不在容器中
對允許重復關鍵字的容器，刪除元素的數量可能大于1：auto ent = authors . erase (*'Barth, John"); 如果authors是我們在11.3.2節 (第 386頁)中創建的multimap,則 ent的值為2。

11.3.4 map的下標操作

map和unordered_map容器提供了下標運算符和一個對應的at函數(參見9.3.2節，第311頁)，如表11/所示。set類型不支持下標，因為set中沒有與關鍵字相關聯的"值”。元素本身就是關鍵字，因此“獲取與一個關鍵字相關聯的值”的操作就沒有意義了。我們不能對一個multimap或一個unordered_multimap進行下標操作，因為這些容器中可能有多個值與一個關鍵字相關聯。
類似我們用過的其他下標運算符，map下標運算符接受一個索引(即，一個關鍵字)，獲取與此關鍵字相關聯的值。但是，與其他下標運算符不同的是，如果關鍵字并不在map中，會為它創建一個元素并插入到map中，關聯值將進行值初始化(參見3.3.1節，第88頁)。例如，如果我們編寫如下代碼
map〈string,size_t>word_count;〃emptymap
word_count["Anna"]=1;??//插入一個關鍵字為Anna的元素，關聯值進行值初始化；然后將1賦予它
將會執行如下操作：
在word_count中搜索關鍵字為Anna的元素，未找到。
將一個新的關鍵字值對插入到word_count中。關鍵字是一個const string,保存Anna.值進行值初始化，在本例中意味著值為0。
提取出新插入的元素，并將值1賦予它。
由于下標運算符可能插入一個新元素，我們只可以對非const的map使用下標操作。
使對用一一個map使用下標操作，其行為與數組或vector上的下標操作很不相同：使用一個不在容器中的關鍵字作為下標，會添加一個具有此關鍵字的元素到map中

使用下標操作的返回值

map的下標運算符與我們用過的其他下標運算符的另一個不同之處是其返回類型。通常情況下，解引用一個迭代器所返回的類型與下標運算符返回的類型是一樣的。但對map 則不然：當對一個map進行下標操作時，會獲得一個mapped_type對象；但當解引用—個 map迭代器時，會得到一個value_type對象（參見11.3節’第 381頁）。?
與其他下標運算符相同的是，map的下標運算符返回一個左值（參見4.L1節，第 121 頁）。由于返回的是一個左值，所以我們既可以讀也可以寫元素：

如果關鍵字還未在map中，下標運算符會添加一個新元素，這一特性允許我們編寫出異常簡潔的程序，例如單詞計數程序中的循環（參見11.1節，第 375頁）。另一方面，有時只是想知道一個元素是否已在map中，但在不存在時并不想添加元素。在這種情況下，就不能使用下標運算符。

1 1 .3 .5 訪問元素

關聯容器提供多種查找一個指定元素的方法，如表11.7所示。應該使用哪個操作依賴于我們要解決什么問題。如果我們所關心的只不過是一個特定元素是否已在容器中，可能find是最佳選擇。對于不允許重復關鍵字的容器，可能使用find還是count沒什么區別。但對于允許重復關鍵字的容器，count還會做更多的工作：如果元素在容器中，它還會統計有多少個元素有相同的關鍵字。如果不需要計數，最好使用find：

在 multimap或 multiset中查找元素

在一個不允許重復關鍵字的關聯容器中查找一個元素是一件很簡單的事情—— 元素要么在容器中，要么不在。但對于允許重復關鍵字的容器來說，過程就更為復雜：在容器中可能有很多元素具有給定的關鍵字。如果一個multimap或 multiset中有多個元素具有給定關鍵字，則這些元素在容器中會相鄰存儲。
例如，給定一個從作者到著作題目的映射，我們可能想打印一個特定作者的所有著作。可以用三種不同方法來解決這個問題。最直觀的方法是使用find和 count：

首先調用count確定此作者共有多少本著作，并調用find獲得一個迭代器，指向第一個關鍵字為此作者的元素。for循環的迭代次數依賴于count的返回值。特別是，如果 count返回0.則循環一次也不執行。
當我們遍歷一個multimap或 multiset時，保證可以得到序列中所有具有給定關鍵字的元素

一種不同的，面向迭代器的解決方法

我們還可以用lower_bound和 upper_bound來解決此問題。這兩個操作都接受一個關鍵字，返回一個迭代器。如果關鍵字在容器中，lower_bound返回的迭代器將指向第一個具有給定關鍵字的元素，而 upper_bound返回的迭代器則指向最后一個匹配給定關鍵字的元素之后的位置。如果元素不在multimap中，則lower_bound和 upper_bound會返回相等的迭代器—— 指向一個不影響排序的關鍵字插入位置。
因此，用相同的關鍵字調用lower_bound和 upper_bound會得到一個迭代器范圍(參見9.2.1節，第296頁)，表示所有該關鍵字的元素的范圍。
?當然，這兩個操作返回的迭代器可能是容器的尾后迭代器。如果我們查找的元素具有容器中最大的關鍵字，則此關鍵字的upper_bound返回尾后迭代器。如果關鍵字不存在，且大于容器中任何關鍵字，則 lowe_bound返回的也是尾后迭代器。
lower_bound返回的迭代器可能指向一個具有給定關鍵字的元素，但也可能不指向。如果關鍵字不在容器中，則 lower_bound會返回關鍵字的第一個安全插入點—— 不影響容器中元素順序的插入位置

此程序與使用count和find的版本完成相同的工作，但更直接。對lower_bound的調用將beg定位到第一個與search_item匹配的元素(如果存在的話)。如果容器中沒有這樣的元素，beg將指向第一個關鍵字大于search_item的元素，有可能是尾后迭代器。upper_bound調用將end指向最后一個匹配指定關鍵字的元素之后的元素。這兩個操作并不報告關鍵字是否存在，重要的是它們的返回值可作為一個迭代器范圍(參見9.2.1節，第296頁)。
如果沒有元素與給定關鍵字匹配，則lower_bound和upper_bound會返回可相等的迭代器--都指向給定關鍵字的插入點，能保持容器中元素順序的插入位置。
假定有多個元素與給定關鍵字匹配，beg將指向其中第一個元素。我們可以通過遞增beg來遍歷這些元素。end中的迭代器會指出何時完成遍歷當beg等于end時，就表明已經遍歷了所有匹配給定關鍵字的元素了。
由于這兩個迭代器構成一個范圍，我們可以用一個for循環來遍歷這個范圍。循環可能執行零次，如果存在給定作者的話，就會執行多次，打印出該作者的所有項。如果給定作者不存在，beg和end相等，循環就一次也不會執行。否則，我們知道遞增beg最終會使它到達end,在此過程中我們就會打印出與此作者關聯的每條記錄。
如果lower_bound和 upper_bound返回相同的迭代器，則給定關鍵字不在容器中

equal_range 函數

解決此問題的最后一種方法是三種方法中最直接的：不必再調用upper bound和lower_bound,直接調用equal_range即可。此函數接受一個關鍵字，返回一個迭代器 pair。
若關鍵字存在，則第一個迭代器指向第一個與關鍵字匹配的元素，第二個迭代器指向最后一個匹配元素之后的位置。若未找到匹配元素，則兩個迭代器都指向關鍵字可以插入的位置。

此程序本質上與前一個使用upper_bound和 lower_bound的程序是一樣的。不同之處就是，沒有用局部變量beg和 end來保存元素范圍，而是使用了 equal_range返回的 pair。此 pair的 first成員保存的迭代器與lower_bound返回的迭代器是一樣的， second保存的迭代器與upper_bound的返回值是一樣的。因此，在此程序中， pos.first 等價于 beg, pos , second 等價于 end。

11.3.6 一個單詞轉換的map

我們將以一個程序結束本節的內容，它將展示map 的創建、搜索以及遍歷。這個程序的功能是這樣的：給定一個string,將它轉換為另一個string。程序的輸入是兩個文件。第一個文件保存的是一些規則，用來轉換第二個文件中的文本。每條規則由兩部分組成：一個可能出現在輸入文件中的單詞和一個用來替換它的短語。表達的含義是，每當第一個單詞出現在輸入中時，我們就將它替換為對應的短語。第二個輸入文件包含要轉換的文本。

1 1 .4 無序容器

新標準定義了 4 個無序關聯容器(unordered associative container)o 這些容器不是使用比較運算符來組織元素，而是使用一個哈希函數(hash function)和關鍵字類型的==運算貿符。在關鍵字類型的元素沒有明顯的序關系的情況下，無序容器是非常有用的。在某些應用中，維護元素的序代價非常高昂，此時無序容器也很有用。
雖然理論上哈希技術能獲得更好的平均性能，但在實際中想要達到很好的效果還需要進行一些性能測試和調優工作。因此，使用無序容器通常更為簡單(通常也會有更好的性能)。
如果關鍵字類型固有就是無序的，或者性能測試發現問題可以用哈希技術解決，就可以使用無序容器」

使用無序容器

除了哈希管理操作之外，無序容器還提供了與有序容器相同的操作(find,insert等)。這意味著我們曾用于map和set的操作也能用于unordered_map和unordered_seto類似的，無序容器也有允許重復關鍵字的版本。因此，通常可以用一個無序容器替換對應的有序容器，反之亦然。但是，由于元素未按順序存儲，一個使用無序容器的程序的輸出(通常)會與使用有序容器的版本不同。
例如，可以用unordered_map重寫最初的單詞計數程序(參見11.1節，第375頁)：

此程序與原程序的唯一區別是word_count的類型。輸出不按照字典順序進行排列

管理桶

無序容器在存儲上組織為一組桶，每個桶保存零個或多個元素。無序容器使用一個哈希函數將元素映射到桶。為了訪問一個元素，容器首先計算元素的哈希值，它指出應該搜索哪個桶。容器將具有一個特定哈希值的所有元素都保存在相同的桶中。如果容器允許重復關鍵字，所有具有相同關鍵字的元素也都會在同一個桶中。因此，無序容器的性能依賴于哈希函數的質量和桶的數量和大小。
對于相同的參數，哈希函數必須總是產生相同的結果。理想情況下，哈希函數還能將每個特定的值映射到唯一的桶。但是，將不同關鍵字的元素映射到相同的桶也是允許的。當一個桶保存多個元素時，需要順序搜索這些元素來查找我們想要的那個。計算一個元素的哈希值和在桶中搜索通常都是很快的操作。但是，如果一個桶中保存了很多元素，那么查找一個特定元素就需要大量比較操作。
無序容器提供了一組管理桶的函數，如表11.8所示。這些成員函數允許我們查詢容器的狀態以及在必要時強制容器進行重組。

無序容器對關鍵字類型的要求

默認情況下，無序容器使用關鍵字類型的==運算符來比較元素，它們還使用一個hash<key_type>類型的對象來生成每個元素的哈希值。標準庫為內置類型(包括指針)提供了hash模板。還為一些標準庫類型，包括string和我們將要在第12章介紹的智能指針類型定義了hash。因此，我們可以直接定義關鍵字是內置類型(包括指針類型)、string還是智能指針類型的無序容器。.但是，我們不能直接定義關鍵字類型為自定義類類型的無序容器。與容器不同，不能直接使用哈希模板，而必須提供我們自己的hash模板版本。我們將在16.5節(第626頁)中介紹如何做到這一點。我們不使用默認的hash,而是使用另一種方法，類似于為有序容器重載關鍵字類型的默認比較操作(參見11.2.2節，第 378頁)。為了能將Sale_data用作關鍵字，我們需要提供函數來替代==運算符和哈希值計算函數。我們從定義這些重載函數開始：

小結

關聯容器支持通過關鍵字高效查找和提取元素。對關鍵字的使用將關聯容器和順序容器區分開來，順序容器中是通過位置訪問元素的。
標準庫定義了8個關聯容器，每個容器
是一個map或是yi個set。map保存關鍵字-值對；set保存關鍵字。
要求關鍵字唯一或不要求
保持關鍵字有序或不保證有序。
有序容器使用比較函數來比較關鍵字，從而將元素按順序存儲。默認情況下，比較操作是用關鍵字類型的<運算符。無序容器使用關鍵字類型的==運算符和一個hash<key_type>類型的對象來組織元素。
允許重復關鍵字的容器的名字中都包含multi；而使用哈希技術的容器的名字都以unordered開頭。例如，set是一個有序集合，其中每個關鍵字只可以出現一次；unordered_multiset則是一"無序的關鍵字集合，其中關鍵字可以出現多次。關聯容器和順序容器有很多共同的元素。但是，關聯容器定義了一些新操作，并對一些和順序容器和關聯容器都支持的操作重新定義了含義或返回類型。操作的不同反映出關聯容器使用關鍵字的特點。
有序容器的迭代器通過關鍵字有序訪問容器中的元素。無論在有序容器中還是在無序容器中，具有相同關鍵字的元素都是相鄰存儲的。

術語表

關聯數組元素通過關鍵字而不是位置來索引的數組。我們稱這樣的數組將一個關鍵字映射到其關聯的值。
關聯容器(associativecontainer)類型，保存對象的集合，支持通過關鍵字的高效查找。
hash 特殊的標準庫模板，無序容器用它來管理元素的位置。
哈希函數 (hashfunction)將給定類型的值映射到整形(size_t)值的函數。相等的值必須映射到相同而整數：不相等的值應盡可能映射到不同整數。
key_type關聯容器定義的類型，用來保存和提取值的關鍵字的類型。對于一個map,key_type是用來索引map的類型。對于 set,key_type 和 value_type 是一樣的
map關聯容器類型，定義了一個關聯數組。類似 vector, map是一個類模板。但是，一個map要用兩個類型來定義：關鍵字的類型和關聯的值的類型.在一個map中，一個給定關鍵字只能出現一次。每個關鍵字關聯一個特定的值。解引用一個map迭代器會生成一個pair,它保存一個const關鍵字及其關聯的值。
mapped_type映射類型定義的類型，就是映射中關鍵字關聯的值的類型。
multimap關聯容器類型，類似map,不同之處在于，在一個multimap中，一個給定的關鍵字可以出現多次。multimap不支持下標操作。
multiset保存關鍵字的美聯容器類型。在一個multiset中，一個給定關鍵字可以出現多次。
pair類型，保存名為first和second的public數據成員.pair類型是模板類型，接受兩個類型參數，作為其成員的類型。
set? 保存關鍵字的關聯容器。在一個set 中，一個給定的關鍵字只能出現一次。
嚴格弱序? 關聯容器所使用的關鍵字間的關系。在一個嚴格弱序中，可以比較任意兩個值并確定哪個更小。若任何一個都不小于另一個，則認為兩個值相等。
無序容器? 關聯容器，用哈希技術而不是比較操作來存儲和訪問元素。這類容器的性能依賴于哈希函數的質量。
unordered_map保存關鍵字-值對的容器，不允許重復關鍵字。
unordered_multimap保存關鍵字-值對的容器，允許重復關鍵字。
unordered_multiset保存關鍵字的容器，允許重復關鍵字。
unordered_set保存關鍵字的容器，不允許重復關鍵字。
value_type容器中元素的類型。對于set和multiset,value_type和key_type是一樣的。對于map和multimap.此類型是一個pair,其first成員類型為constkey_type,second成員類型為mapped_type。
*運算符解引用運算符。當應用于map、set、multimap或multiset的迭代器時，會生成一個value_type值。注意，對map和multimap,value_type是一個pair
[]運算符下標運算符。只能用于map和unordered_map類型的非const對象。對于映射類型，[]接受一個索引，必須是一個key_type值(或者是能轉換為key_type的類型)。生成一個
mapped_type值。