STL之Map

map是标準關聯式容器（associative container）之一，一個map是一個鍵值對序列，即（key ,value）對。它提供基于key的快速檢索能力，在一個map中key值是唯一的。map提供雙向疊代器，即有從前往後的（iterator），也有從後往前的（reverse_iterator）。

map要求能對key進行<操作，且保持按key值遞增有序，是以map上的疊代器也是遞增有序的。如果對于元素并不需要保持有序，可以使用hash_map。

map中key值是唯一的，如果馬匹中已存在一個鍵值對(昵稱,密碼):("skynet",407574364)，而我們還想插入一個鍵值對("skynet",472687789)則會報錯（不是報錯，準确的說是，傳回插入不成功！）。而我們又的确想這樣做，即一個鍵對應多個值，幸運的是multimap可是實作這個功能。

下面我們用執行個體來深入介紹map、multimap，主要内容如下：

1、例子引入

2、map中的類型定義

3、map中的疊代器和鍵值對

4、map中的構造函數與析構函數

5、map中的操作方法

6、再議map的插入操作

7、[]不僅插入

8、multimap

9、總結

有一個伺服器manager維護着接入伺服器的client資訊，包括clinetid、scanrate、socketaddr等等。我們定義一個結構體儲存scanrate、socketaddr資訊。如下：

<code>typedef</code> <code>int</code> <code>clientid;</code>

<code>typedef</code> <code>struct</code><code>{</code>

<code> </code><code>int</code> <code>scanrate;</code>

<code> </code><code>string socketaddr;</code>

<code>}clientinfo;</code>

我們用map儲存這些資訊：clientid為鍵key，clientinfo為值。這樣我們可以通過clientid快速檢索到client的相關資訊，我們可以這樣定義：

<code>map<clientid,clientinfo> clientmap;</code>

這樣我們定義了一個clientmap，如果我們要定義多個這樣的map，需要多次寫map<clientid,clientinfo> 變量名。為了避免這樣情況，我們通常為map<clientid,clientinfo>定義個别名，如：

<code>typedef</code> <code>map<clientid,clientinfo> clientedp;</code>

<code>clientedp clientmap;</code>

之後我們就可以像定義clientmap一樣定義map<clientid,clientinfo>對象，這樣的好處還有：如果我們需要修改map的定義，隻需要在一處修改即可，避免修改不徹底造成的不一緻現象。

我們這就完成了需要的map的定義，如果不定義或沒有在它上面的操作的話，就像定義類而沒有方法一樣，意義不大或毫無意義。幸運的是，stl提供了

這些常用操作：排序（注：map是不能也不要排序的，因為map本身已經排好序了）、列印、提取子部分、移除元素、添加元素、查找對象，就像資料庫的增删

改查操作！現在我們詳細介紹這些操作，并逐漸引入hash_map、multimap。

關聯數組（associative array）是最有用的使用者定義類型之一，經常内置在語言中用于文本處理等。一個關聯數組通常也稱為map，有時也稱字典（dictionary），儲存一對值。第一個值稱為key、第二個稱為映射值mapped-value。

标準map是定義在std命名空間中的一個模闆，并表示為<map>。它首先定義了一組标準類型名字：

<code>template</code><code><</code><code>class</code> <code>key,</code><code>class</code> <code>t,</code><code>class</code> <code>cmp=less<key>,</code>

<code> </code><code>class</code> <code>a=allocator<pair<</code><code>const</code> <code>key,t>></code>

<code>class</code> <code>std::map</code>

<code>public</code><code>:</code>

<code> </code><code>//types</code>

<code> </code><code>typedef</code> <code>key key_type;</code>

<code> </code><code>typedef</code> <code>t mapped_type;</code>

<code> </code><code>typedef</code> <code>pair<</code><code>const</code> <code>key,t> value_type;</code>

<code> </code><code>typedef</code> <code>cmp key_compare;</code>

<code> </code><code>typedef</code> <code>a allocator_type;</code>

<code> </code><code>typedef</code> <code>typename</code> <code>a::reference reference;</code>

<code> </code><code>typedef</code> <code>typename</code> <code>a::const_reference const_reference;</code>

<code> </code><code>typedef</code> <code>implementation_define1 iterator;</code>

<code> </code><code>typedef</code> <code>implementation_define2 const_iterator;</code>

<code> </code><code>typedef</code> <code>typename</code> <code>a::size_type size_type;</code>

<code> </code><code>typedef</code> <code>typename</code> <code>a::difference_type difference_type;</code>

<code> </code><code>typedef</code> <code>std::reverse_iterator<iterator> reverse_iterator;</code>

<code> </code><code>typedef</code> <code>std::reverse_iterator<const_iterator> const_reverse_iterator;</code>

注意：map的value_type是一個(key,value)對，映射值的被認為是mapped_type。是以，一個map是一個

pair<const key,mapped_type>元素的序列。從const key可以看出，map中鍵key是不可修改的。

不得不提的是map定義中cmp和a都是可選項。cmp是定義在元素之間的比較方法，預設是<操作；a即allocator用來配置設定和釋放map總鍵值對所需使用的記憶體，沒有指定的話即預設使用的是stl提供的，也可以自定義allocator來管理記憶體的使用。多數情況，我們不指定這兩個選項而使用預設值，這樣我們定義map就像下面這樣：

<code>map<</code><code>int</code><code>,clientinfo> clientmap;</code>

cmp和a都預設。通常，實際的疊代器是實作定義的，因為map很像使用了樹的形式，這些疊代器通常提供樹周遊的某種形式。逆向疊代器是使用标準的reverse_iterator模闆構造的。

map提供慣常的傳回疊代器的一組函數，如下所示：

<code>public</code><code>: </code>

<code> </code><code>//iterators</code>

<code> </code><code>iterator begin();</code>

<code> </code><code>const_iterator begin() </code><code>const</code><code>;</code>

<code> </code><code>iterator end();</code>

<code> </code><code>const_iterator end() </code><code>const</code><code>;</code>

<code> </code><code>reverse_iterator rbegin();</code>

<code> </code><code>const_reverse_iterator rbegin() </code><code>const</code><code>;</code>

<code> </code><code>reverse_iterator rend();</code>

<code> </code><code>const_reverse_iterator rend() </code><code>const</code><code>;</code>

map上的疊代器是pair<const key,mapped_type>元素序列上簡單的疊代。例如，我們可能需要列印出所有的用戶端資訊，像下面的程式這樣。為了實作這個，我們首先向《例子引入》中定義的clientedp中插入資料，然後列印出來：

<code>#include<iostream></code>

<code>#include<map></code>

<code>#include<string></code>

<code>using</code> <code>namespace</code> <code>std;</code>

<code> </code><code>typedef</code> <code>map<clientid,clientinfo> clientedp;</code>

<code> </code><code>typedef</code> <code>map<clientid,clientinfo>::const_iterator iterator;</code>

<code> </code><code>clientedp clients;</code>

<code> </code><code>clientinfo client[100];</code>

<code> </code><code>string straddr(</code><code>"socket addr client "</code><code>);</code>

<code> </code><code>client[i].scanrate=i+1; </code>

<code> </code><code>//convert int to char*</code>

<code> </code><code>//concatenate straddr and str</code>

<code> </code><code>client[i].socketaddr=straddr+str;</code>

<code> </code><code>clients.insert(</code>

<code> </code><code>make_pair(i+1,client[i])); </code>

<code> </code><code>delete</code> <code>str;</code>

<code> </code><code>for</code><code>(iterator i=clients.begin();i!=clients.end();i++)</code>

<code> </code><code>cout<<</code><code>"clientid:"</code><code><<i->first<<endl;</code>

<code> </code><code>cout<<</code><code>"scanrate:"</code><code><<i->second.scanrate<<endl;</code>

<code> </code><code>cout<<</code><code>"socketaddr:"</code><code><<i->second.socketaddr<<endl;</code>

一個map疊代器以key升序方式表示元素，是以用戶端資訊以cliendid升序的方式輸出。運作結果可以證明這一點，運作結果如下所示：

圖1、程式運作結果

我們以first引用鍵值對的key，以second引用mapped value，且不用管key和mapped value是什麼類型。其實pair在std的模闆中是這樣定義的：

<code>template</code> <code><</code><code>class</code> <code>t1,</code><code>class</code> <code>t2></code><code>struct</code> <code>std::pair{</code>

<code> </code><code>typedef</code> <code>t1 first_type;</code>

<code> </code><code>typedef</code> <code>t2 second_type;</code>

<code> </code><code>t1 first;</code>

<code> </code><code>t2 second;</code>

<code> </code><code>pair():first(t1()),second(t2()){}</code>

<code> </code><code>pair(</code><code>const</code> <code>t1& x,</code><code>const</code> <code>t2& y):first(x),second(y){}</code>

<code> </code><code>template</code><code><</code><code>class</code> <code>u,</code><code>class</code> <code>v></code>

<code> </code><code>pair(</code><code>const</code> <code>pair<u,v>& p):first(p.first),second(p.second){}</code>

即map中，key是鍵值對的第一個元素且mapped value是第二個元素。pair的定義可以在<utility>中找到，pair提供了一個方法友善建立鍵值對：

<code>template</code> <code><</code><code>class</code> <code>t1,</code><code>class</code> <code>t2>pair<t1,t2></code>

<code> </code><code>std::make_pair(</code><code>const</code> <code>t1& t1,</code><code>const</code> <code>t2& t2)</code>

<code> </code><code>return</code> <code>pair<t1,t2>(t1,t2);</code>

上面的例子中我們就用到了這個方法來建立(clientid,clientinfo)對，并作為insert()方法的參數。每個pair預設初始化每個元素的值為對應類型的預設值。

map類慣常提供了構造函數和析構函數，如下所示：

<code> </code><code>//construct/copy/destroy</code>

<code> </code><code>explicit</code> <code>map(</code><code>const</code> <code>cmp&=cmp(),</code><code>const</code> <code>a&=a());</code>

<code> </code><code>template</code><code><</code><code>class</code> <code>in>map(in first,in last,</code>

<code> </code><code>const</code> <code>com&=cmp(),</code><code>const</code> <code>a&=a());</code>

<code> </code><code>map(</code><code>const</code> <code>map&);</code>

<code> </code><code>map& operator=(</code><code>const</code> <code>map&);</code>

複制一個容器意味着為它的每個元素配置設定空間，并拷貝每個元素值。這樣做是性能開銷是很大的，應該僅當需要的時候才這樣做。是以，map傳的是引用。

前面我們已經說過，如果map中僅定義了一些key、mapped

value類型的資訊而沒有操作方法，就如定義個僅有字段的類意義不大甚至毫無意義。由此可見map中定義操作方法非常重要！前面的例子我們就用到了不少

方法，如傳回疊代器的方法begin()、end()，鍵值對插入方法insert()。下面我們對map中的操作方法做個全面的介紹：

<code> </code><code>//map operations</code>

<code> </code><code>//find element with key k</code>

<code> </code><code>iterator find(</code><code>const</code> <code>key_type& k);</code>

<code> </code><code>const_iterator find(</code><code>const</code> <code>key_type& k)</code><code>const</code><code>;</code>

<code> </code><code>//find number of elements with key k</code>

<code> </code><code>size_type count()</code><code>const</code><code>;</code>

<code> </code><code>//find first element with key k</code>

<code> </code><code>iterator lower_bound(</code><code>const</code> <code>key_type& k);</code>

<code> </code><code>const_iterator lower_bound(</code><code>const</code> <code>key_type& k)</code><code>const</code><code>;</code>

<code> </code><code>//find first element with key greater than k</code>

<code> </code><code>iterator upper_bound(</code><code>const</code> <code>key_type& k);</code>

<code> </code><code>const_iterator upper_bound(</code><code>const</code> <code>key_type& k)</code><code>const</code><code>;</code>

<code> </code><code>//insert pair(key,value)</code>

<code> </code><code>pair<iterator,</code><code>bool</code><code>>insert(</code><code>const</code> <code>value_type& val);</code>

<code> </code><code>iterator insert(iterator pos,</code><code>const</code> <code>value_type& val);</code>

<code> </code><code>template</code><code><</code><code>class</code> <code>in></code><code>void</code> <code>insert(in first,in last);</code>

<code> </code><code>//erase element</code>

<code> </code><code>void</code> <code>erase(iterator pos);</code>

<code> </code><code>size_type erase(</code><code>const</code> <code>key_type& k);</code>

<code> </code><code>void</code> <code>erase(iterator first,iterator last);</code>

<code> </code><code>void</code> <code>clear();</code>

<code> </code><code>//number os elements</code>

<code> </code><code>size_type size()</code><code>const</code><code>;</code>

<code> </code><code>//size of largest possible map</code>

<code> </code><code>size_type max_size()</code><code>const</code><code>;</code>

<code> </code><code>bool</code> <code>empty()</code><code>const</code><code>{</code><code>return</code> <code>size()==0;}</code>

上面這些方法基本都能顧名思義（ps.由此可見，命名有多重要，我們平時要養成好的命名習慣，當然注釋也必不可少！）。雖然已經非常清楚了了，但我還是想講解一下以消除不惜要的誤解和更好地應用這些方法。

find(k)方法簡單地傳回鍵值為k的元素的疊代器；如果沒有元素的鍵值為k，則傳回map的end()疊代器。由于map是按鍵key升序排列，所有查找的複雜度隻有o(logn)。是以，我們通常會這樣用這個方法：

<code><code>"color: #ff0000;"</code><code>> <code>"color: #ff0000;"</code><code>>clientid id=10;</code>

<code> </code><code>iterator i=clients.find(id);</code>

<code> </code><code>if</code><code>(i!=clients.end()){</code>

<code> </code><code>cout<<</code><code>"clientid: "</code><code><<id</code>

<code> </code><code><<</code><code>" exists in clients"</code><code><<endl;</code>

<code> </code><code><<</code><code>" doesn't exist in clients"</code><code><<endl;</code>

insert()方法

試圖将一個（key,t）鍵值對加入map。因為鍵時唯一的，是以僅當map中不存在鍵值為k的鍵值對時插入才成功。該方法的傳回值為

pair<iterator,bool>，如果插入成功bool值為true，iterator指向插入map中後的鍵值對。如下代碼：

<code> </code><code>clientid id=110;</code>

<code> </code><code>clientinfo cltinfo;</code>

<code> </code><code>cltinfo.scanrate=10;</code>

<code> </code><code>cltinfo.socketaddr=</code><code>"110"</code><code>;</code>

<code> </code><code>pair<clientid,clientinfo> p110(id,cltinfo);</code>

<code> </code><code>pair<iterator,</code><code>bool</code><code>> p=clients.insert(p110);</code>

<code> </code><code>if</code><code>(p.second){</code>

<code> </code><code>cout<<</code><code>"insert success!"</code><code><<endl;</code>

<code> </code><code>cout<<</code><code>"insert failed!"</code><code><<endl;</code>

<code> </code><code>//i points to clients[110];</code>

<code> </code><code>iterator i=p.first;</code>

<code> </code><code>cout<<i->first<<endl;</code>

<code> </code><code>cout<<i->second.scanrate<<endl;</code>

<code> </code><code>cout<<i->second.socketaddr<<endl;</code>

上面我們看出，這裡我們插入鍵值對是首先聲明一個鍵值對pair<clientid,clientinfo> p110(id,cltinfo); 然後再插入，這個我們之前make_pair方法不一樣，make_pair方法用的比較多。

erase()方法用法比較簡單，比如像清除clientid為110的鍵值對，我們隻需要對clients調用erase方法：clients.erase(clients.find(110));或者我們想清除clientid從1到10的鍵值對，我們可以這樣調用erase()方法：clients.erase(clients.finds(1),clients.find(10));簡單吧！别得意，你還需要注意，如果find(k)傳回的是end()，這樣調用erase()方法則是一個嚴重的錯誤，會對map造成破壞操作。

前面我們介紹了利用map的插入方法insert()，聲明鍵值對pair或make_pair生成鍵值對然後我們可以輕松的将鍵值對插入map中。其實map還提供了更友善的插入操作利用下标（subscripting，[]）操作，如下：

<code>clientinfo cltinfo;</code>

<code>cltinfo.scanrate=10;</code>

<code>cltinfo.socketaddr=</code><code>"110"</code><code>;</code>

<code>clients[110]=cltinfo;</code>

這樣我們就可以簡單地将鍵值對插入到map中了。下标操作在map中式這樣定義的：

<code> </code><code>//access element with key k</code>

<code> </code><code>mapped_type& operator[](</code><code>const</code> <code>key_type& k);</code>

我們來分析一下應用[]操作，插入鍵值對的過程：檢查鍵k是否已經在map裡。如果不，就添加上，以v作為它的對應值。如果k已經在map

裡，它的關聯值被更新成v。這裡首先，查找110不在map中則建立一個鍵為110的鍵值對，并将映射值設為預設值，這裡scanrate為

0，socketaddr為空；然後将映射值賦為cltinfo。如果110在map中已經存在的話，則隻是更新以110為鍵的映射值。

從上面的分析可知：如果大量這樣插入資料，會嚴重影響效率！如果你考慮效率問題，請使用insert操作。insert方法，節省了三次函數調用：一個建立臨時的預設映射值的對象，一個銷毀那個臨時的對象和一個對映射值的指派操作。

note1：如果k已經存在map中，[]效率反而比insert的效率高，而且更美觀！如果能夠兼顧這兩者那豈不是很美妙！其實我們重寫map中的[]操作：首先判斷k是否已經在map中，如果沒有則調用insert操作，否則調用内置的[]操作。如下列代碼：

<code>///@param maptype-map的類型參數</code>

<code>///@param keyargtype-鍵的類型參數</code>

<code>///@param valueargtype-映射值的類型參數</code>

<code>///@return 疊代器，指向鍵為k的鍵值對</code>

<code>template</code><code><</code><code>typename</code> <code>maptype,</code>

<code> </code><code>typename</code> <code>keyargtype,</code>

<code> </code><code>typename</code> <code>valueargtype></code>

<code>typename</code> <code>maptype::iterator</code>

<code> </code><code>efficientaddorupdate(maptype& m,</code>

<code> </code><code>const</code> <code>keyargtype& k,</code>

<code> </code><code>const</code> <code>valueargtype& v)</code>

<code> </code><code>typename</code> <code>maptype::iterator ib = m.lower_bound(k);</code>

<code> </code><code>if</code><code>(ib != m.end()&&!(m.key_comp()(k,ib->first))) {</code>

<code> </code><code>//key已經存在于map中做更新操作</code>

<code> </code><code>ib->second = v; </code>

<code> </code><code>return</code> <code>ib; </code>

<code> </code><code>//key不存在map中做插入操作</code>

<code> </code><code>typedef</code> <code>typename</code> <code>maptype::value_type mvt;</code>

<code> </code><code>return</code> <code>m.insert(ib, mvt(k, v)); </code>

note2：我們視乎還忽略了一點，如果映射值mapped value的類型沒有預設值，怎麼辦？這種情況請勿使用[]操作插入。

通過[]操作不僅僅是插入鍵值對，我們也可以通過鍵key檢索出映射值mapped value。而且我們利用[]操作可以輕松地統計資訊，如有這樣這樣一些鍵值對（book-name，count）對：

(book1,1)、(book2,2)、(book1,2)、(book3,1)、(book3,5)

我們計算每種book的數量總和。我們可以這樣做：将它們讀入一個map<string,int>：

<code> </code><code>map<string,</code><code>int</code><code>> bookmap;</code>

<code> </code><code>string book;</code>

<code> </code><code>int</code> <code>count;</code>

<code> </code><code>int</code> <code>total=0;</code>

<code> </code><code>while</code><code>(cin>>book>>count)</code>

<code> </code><code>bookmap[book]+=count;</code>

<code> </code><code>map<string,</code><code>int</code><code>>::iterator i;</code>

<code> </code><code>for</code><code>(i=bookmap.begin();i!=bookmap.end();i++)</code>

<code> </code><code>total+=i->second;</code>

<code> </code><code>cout<<i->first<<</code><code>'\t'</code><code><<i->second<<endl;</code>

<code> </code><code>cout<<</code><code>"total count:"</code><code><<total<<endl;</code>

結果如下所示：（注意按住ctrl+z鍵結束輸入）

圖2、程式運作結果

前面介紹了map，可以說已經非常清晰了。如果允許clientid重複的話，map就無能為力了，這時候就得multimap上場了！multimap允許鍵key重複，即一個鍵對應多個映射值。其實除此之外，multimap跟map是很像的，我們接下來在map的基礎上介紹multimap。

multimap在std中的定義跟map一樣隻是類名為multimap，multimap幾乎有map的所有方法和類型定義。

multimap不支援[]操作；但map支援

multimap的insert方法傳回的是一個疊代器iterator，沒有bool值；而map值（iterator，bool）的元素對

對應equal_range()、方法：

雖然在map和multimap都有，顯然對multimap有更多的意義！equal_range()方法傳回一個鍵key對應的多個映射值的上界和下

界的鍵值對的疊代器、lower_bound()方法傳回鍵multimap中第一個箭為key的鍵值對疊代器、upper_bound()方法傳回比

key大的第一個鍵值對疊代器。

假設我們想取出鍵為key的所有映射值，我們可以這樣做：

<code>typedef</code> <code>int</code> <code>clientid;</code>

<code> </code><code>typedef</code> <code>multimap<clientid,clientinfo> clientedp;</code>

<code> </code><code>typedef</code> <code>multimap<clientid,clientinfo>::const_iterator iterator;</code>

<code> </code><code>clientinfo client[20];</code>

<code> </code><code>make_pair(10,client[i])); </code>

<code> </code><code>delete</code> <code>str,straddr;</code>

<code> </code><code>//find elements with key 10</code>

<code> </code><code>iterator lb=clients.lower_bound(10);</code>

<code> </code><code>iterator ub=clients.upper_bound(10);</code>

<code> </code><code>for</code><code>(iterator i=lb;i!=ub;i++)</code>

（說明：實際上，一般是不允許clientid重複的，這裡隻是為了舉例。）這樣是不是感覺很醜呢！事實上，我們可以更簡單的這樣：

<code>//find elements with key 10</code>

<code>pair<iterator,iterator> p=clients.equal_range(10);</code>

<code>for</code><code>(iterator i=p.first;i!=p.second;i++)</code>

<code> </code><code>cout<<</code><code>"clientid:"</code><code><<i->first<<endl;</code>

<code> </code><code>cout<<</code><code>"scanrate:"</code><code><<i->second.scanrate<<endl;</code>

<code> </code><code>cout<<</code><code>"socketaddr:"</code><code><<i->second.socketaddr<<endl;</code>

map是一類關聯式容器。它的特點是增加和删除節點對疊代器的影響很小，除了那個操作節點，對其他的節點都沒有什麼影響。對于疊代器來說，可以修改實值，而不能修改key。

map的功能：

自動建立key －value的對應。key 和value可以是任意你需要的類型。

根據key值快速查找記錄，查找的複雜度基本是log(n)。

快速插入key - value 記錄。

快速删除記錄

根據key 修改value記錄。

周遊所有記錄。

展望：本文不知不覺寫了不少字了，但仍未深入涉及到map定義的第3個和第4個參數，使用的都是預設值。

template<class key,class t,class cmp=less<key>,

class a=allocator<pair<const key,t>>

感興趣者，請查找相關資料or下面留言希望看到單獨開篇介紹map第3個和第4個參數。您的支援，我的動力！ps：在此文的原因，在與公司做項目用到了map特此總結出來與大家共享，不過在進行個人總結過程中，難免會有疏漏或不當之處，請不吝指出。

STL之Map

繼續閱讀

C語言第四章自述2第四章選擇結構程式設計

面試題:vector和map的差別，異同。空間分布，100萬資料存哪個比較合适。一、疊代器差別二、vector三、Map、Set四、vector_map 為什麼比map效率高五、如何選擇六、容器選擇原則七、效率對比

C++ 多線程用條件變量确定線程的執行順序而不是使用 sleep(1)

POJ 1284 Primitive Roots (歐拉函數&原根定理)

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

成員函數初始化清單

2021-08-13c++——類之操作符重載

swmm與lisflood-fp源碼如何一起編譯 CMake指令

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述