C++ Primer筆記（八）關聯容器

1、關聯容器和順序容器的本質差别在于：

關聯容器通過鍵存儲和讀取元素，而順序元素通過元素在容器中的位置順序存儲和通路元素。雖然關聯容器的大部分行為與順序容器相同，但其獨特之處在于支援鍵的使用。

2、關聯容器通過鍵來高效的查找和讀取元素，兩個基本的關聯容器為map和set。

map的元素以鍵--值對的形式組織，鍵用作元素在map中的索引，而值表示存儲和讀取的元素。set僅包含一個鍵，并有效地支援關于某個鍵是否存在的查詢。

3、如果希望存儲不同值的集合，使用set比較合适，而map容器更适用于需要存儲每個鍵所關聯的值得情況。如在做文本處理時，可使用set儲存忽略的單詞，而字典則是map的一種很好的應用。單詞本身是鍵，而其釋義則是值。

4、set和map類型的對象所包含的元素都具有不同的鍵，不允許為同一個鍵添加第二個元素。如果一個鍵必須對應多個執行個體，則需使用multimap或multiset類型，這兩種類型允許多個元素擁有相同的鍵。

5、pair類型包含兩個數值，是一種模闆類型。在utility頭檔案中定義。

在建立pair類型時必須提供兩個類型名。這兩個類型不必相同。如：

1 pair<T1,T2> p1;

2 pair<T1,T2> p1(v1,v2);

3 make_pair(v1,v2);  //以v1,v2的值建立新的pair對象。

1）如果在建立pair對象時不提供初始化式，則調用預設構造函數對其成員進行初始化。

2）pair類型的使用很繁瑣，如果需要定義多個相同的pair類型對象，可以使用typedef簡化其聲明：

typedef pari<string,string> author;

author  A("jim","green");

3）可以直接通路pair類的對象資料成員，其成員都是公有的。分别命名為first和second。

4）除了構造函數，标準庫還定義了一個make_pair函數，由傳遞給它的兩個實參生成一個新的pair對象。

6、關聯容器共享大部分但并非全部順序容器操作。如：

C<T> c;

C<T> c1(c2);

C<T>c(b,e);   //b,e為一對疊代器。

關聯容器無法通過容器大小來定義，因為那樣就無法知道鍵對應的值是什麼。

關聯容器不提供front、push_front、pop_front、back、push_back以及pop_back操作。

容器元素根據鍵的次序排列，是以在疊代器周遊關聯容器時，我們可確定按鍵的順序通路元素而與元素在容器的存放位置完全無關。

7、map可以了解為關聯數組。可使用鍵作為下标來擷取一個值。要使用map對象必須使用map頭檔案。同時必須分别指明鍵和值的類型。

在使用關聯容器時，鍵不但有一個類型，而且還有一個相關的比較函數。預設情況下，标準庫使用鍵類型定義的<操作符來實作鍵的比較。可以通過重寫預設的操作符，并提供自定義的操作符函數，在後面的模闆中會有介紹。

所用的比較函數必須在鍵類型定義嚴格弱排序。

8、對于鍵類型，唯一的要求就是必須支援<操作符，至于是否支援其他的關系或相等運算則不作要求。

比如，不能定義一個list<int>::iterator關聯int對象，因為list的iterator僅支援除==和！=運算符，不支援<運算符（list中的元素不是順序存儲，存儲位置不能作為在list中的相對位置）。而vector 和deque卻可以。

9、map對象的元素是鍵--值對。它包含兩個部分：鍵以及鍵關聯的值。map的value_type就反映這個事實。

value_type就是存儲元素的鍵以及值的pair類型，而且鍵為const。

map(T1,T2>::value_type    map對象元素類型。pari<T1,T2>

map(T1,T2>::mapped_type  鍵關聯的值得類型T2。

map(T1,T2>::key_type      用作索引的鍵的類型T1。

10、對map疊代器進行解引用将獲得一個引用，指向容器中一個value_type類型的值，其為pair。 pair的first存放鍵，但它為const，second成員存放值。

可以通過insert向map容器中添加元素。也可以通過鍵作為下标擷取元素，然後給擷取的元素指派。

11、通過以鍵作為下标通路map對象。注意：一個給定的鍵隻能對應于一個元素。

map<string,int>word_count;

word_cout["Jim"]=1;

将發生以下事情：

1）在word_count中查找鍵名為Jim的元素，沒有找到。

2）将一個新的鍵值對插入到word_count中。它的鍵是const string類型，儲存Jim，而它的值采用值初始化，為0。

3）将這個新的pair對象插入word_count。

4）讀取新插入的元素，修改為1。

是以使用鍵作為下标來通路不存在的元素将會導緻在map容器中添加新的元素，它的鍵即為該下标值。所關聯的值采取值初始化，類類型的元素用預設構造函數初始化，而内置類型将會被初始化為0。如果該鍵已存在則map的下标運算與vector的下标運算行為相同。

通常來說，下标操作符傳回左值。它傳回的左值是特定鍵所關聯的值。有别于vector或string類型，map下标操作符傳回的類型與對map疊代器進行解引用獲得的類型不相同。

12、map::insert成員函數使用：

m.insert(e);//e為pair對象。

m.insert(beg,end);//beg和end為一對疊代器

m.insert(iter,e);//e為pair對象。iter為疊代器。

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

2：word_count.insert(make_pair<string,int>("Jim",1));

3：word_count.insert(pair<string,int>("Jim",1));

其中1與3大同小異。因為value_type就是由pair<string,int>定義而來。

13、使用insert可以避免下标操作符帶來的副作用：不必要的初始化。

當要插入的元素的鍵值已經存在，則不作任何操作。是以當傳遞一對疊代器時，并不說明該疊代器範圍内的元素都被插入。

m.insert(e)将傳回一個pair類型的對象。

first為一疊代器，指向map中具有相應鍵的元素（pair類型），second為bool類型。如果該鍵已在容器中，則傳回的bool為false，如該鍵不在容器中，則插入新元素，bool值為true。即bool訓示是否插入該元素到容器中。

這兩種情況下傳回的疊代器都指向具有給定鍵的元素(pair類型)。如

map<string,int> word_count;

pari<map<string,int>::iterator,bool>ret

                    =word_count.insert(make_pari("Jim",1));

14、count和find用于檢查某個鍵是否存在而不會插入該鍵。

m.count(k);//傳回m中k出現的次數

m.find(k)//如果存在以k為索引的元素則傳回指向該元素的疊代器，否則指向超出末端疊代器

如：map<string,int>:: iterator it=word_count.find("Jim");

if(it!==word_count.end())

    //存在。 

因為map為單值映射，是以count的傳回值非0即1。這可以用于判斷某個鍵是否存在。而對于multimap，count的傳回值則可能會大于1；

find操作傳回指向元素的疊代器，如果元素不存在，則傳回end疊代器。如果希望當具有指定鍵的元素存在時，就擷取該元素的引用，否則就不在容器中建立新的元素，那麼應該使用find。

15、從map容器中删除元素的erase操作有三種變化形式：

1）m.erase(k);//删除鍵為k的元素，傳回删除個數。

2）m.erase(p);//删除疊代器p所指向的元素，傳回void。

3）m.erase(b,e);//删除一段疊代器範圍内元素。傳回void。

可向erase傳遞一個或一對疊代器，來删除單個或一段範圍内的元素。差別在于，map容器的erase操作傳回void，而順序容器的erase操作傳回一個疊代器，指向本删除元素後面的元素。

map還通過一種額外的erase操作，即參數是key-type類型的值，如果擁有該鍵的元素存在，則删除該元素。

16、map容器是鍵--值對的集合，好比是以人名為鍵的位址和電話号碼。而set僅是單純鍵的集合。

使用set必須包含set頭檔案，set不支援下标操作符，沒有定義mapped_type類型，value_type是與key_type相同的類型。都是指容器中的元素類型，且鍵值必須唯一不能修改。

set容器中的元素必須唯一，如果以一段範圍的疊代器初始化set容器，對于每個鍵，隻添加一個元素，重複的元素不再添加。如

char *name={"Jim","Hellen","Green","Tom","Kate","Jim","Tom"};

set<string> Name(name,name+7);

對于此句由于Jim和Tom均出現兩次，但插入到set容器内時，重複元素不會被添加多次。此時set有5個元素。

17、在set内添加元素使用insert，與map類似。

1）m.insert(a);//a為鍵值。傳回pair對象與map相同。

2）m.insert(b,e);//b,e為疊代器範圍。

set容器不提供下标操作符，要從容器内擷取元素可以使用find運算，它傳回指向該元素的疊代器（如果存在的話）。在獲得某元素的疊代器之後隻能對其做讀操作不能修改，因為鍵是const類型的。 count傳回值隻能為0或1。

18、multimap和multiset

在map和set容器中一個鍵隻能對應一個執行個體。而multimap和multiset則允許一個鍵對應多個執行個體。如在電話簿中，每個人可能有單獨的電話号碼清單。multimap和multiset與map和set具有相同的頭檔案分别為set和map。

multimap不支援下标運算，這一點是個例外。其他操作multimap和multiset與map和set操作相同。

insert和erase同樣适用于multiset和multimap。

erase将删除擁有該鍵的所有元素，并傳回删除元素個數。

19、關聯容器的元素是按順序存放的，而具有相同鍵的元素在容器中相鄰存放。這一點非常重要。如

multimap<string,string>::iterator iter=author.find("Jim");

for(unsigned i=0;i!=author.count();i++)

{

  cout<<iter->second<<endl;

   iter++;

   }

首先确定鍵為Jim的元素個數。然後獲得指向第一個該鍵所關聯的元素的疊代器。依次獲得具有該鍵的所有元素。

是以明白：在multimap中同一個鍵所關聯的元素必然相鄰存放是突破點。

count函數求出某鍵出現的次數，find操作則傳回一個疊代器，指向第一個擁有正在查找的鍵的執行個體。

20、另一個替代方案為：

m.lower_bound(k);//傳回疊代器，指向鍵不小于k的第一個元素。

m.upper_bound(k);//傳回疊代器，指向鍵大k的第一個元素

m.equal_bound(k);//傳回pair對象，first成員等價于m.lower_bound(k),而second成員等價于m.upper_bound(k)；

所有這些操作都需要傳遞一個鍵。

21、在同一個鍵上調用lower_bound和upper_bound将産生一個疊代器範圍，指出該鍵所關聯的所有元素。如該鍵在容器中存在，則将會獲得兩個不同的疊代器。如果該鍵不存在，這兩個操作将指向同一個疊代器，指向依據元素的排列順序應該插入的位置。

22、調用equal_range可以取代lower_bound和upper_bound函數。

它傳回存儲一對疊代器的pair對象。如果該值存在，則pair對象中的第一個疊代器指向該鍵關聯的第一個執行個體，第二個疊代器指向該鍵關聯的最後一個執行個體的下一位置。如果找不到比對的元素，則pair對象中的兩個疊代器都将指向此鍵應插入的位置。

23、練習執行個體：

文本查詢程式。在任意指定的文本檔案中，查詢某單詞出現的次數，并列出每次出現所在的行。