概述

Map是標(biāo)準(zhǔn)關(guān)聯(lián)式容器（associative container）之一，一個(gè)map是一個(gè)鍵值對(duì)序列，即（key ,value）對(duì)。它提供基于key的快速檢索能力，在一個(gè)map中key值是唯一的。map提供雙向迭代器，即有從前往后的（iterator），也有從后往前的（reverse_iterator）。

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

map中key值是唯一的，如果馬匹中已存在一個(gè)鍵值對(duì)(昵稱,密碼):("skynet",407574364)，而我們還想插入一個(gè)鍵值對(duì)("skynet",472687789)則會(huì)報(bào)錯(cuò)（不是報(bào)錯(cuò)，準(zhǔn)確的說(shuō)是，返回插入不成功！）。而我們又的確想這樣做，即一個(gè)鍵對(duì)應(yīng)多個(gè)值，幸運(yùn)的是multimap可是實(shí)現(xiàn)這個(gè)功能。

下面我們用實(shí)例來(lái)深入介紹map、multimap，主要內(nèi)容如下：

• 1、例子引入
• 2、map中的類型定義
• 3、map中的迭代器和鍵值對(duì)
• 4、map中的構(gòu)造函數(shù)與析構(gòu)函數(shù)
• 5、map中的操作方法
• 6、再議map的插入操作
• 7、[]不僅插入
• 8、multimap
• 9、總結(jié)

1、例子引入

有一個(gè)服務(wù)器manager維護(hù)著接入服務(wù)器的client信息，包括clinetId、scanRate、socketAddr等等。我們定義一個(gè)結(jié)構(gòu)體保存scanRate、socketAddr信息。如下：

typedef    int    clientId;
typedef struct{
int scanRate;
string socketAddr;
}clientInfo;

我們用map保存這些信息：clientId為鍵key，clientInfo為值。這樣我們可以通過(guò)clientId快速檢索到client的相關(guān)信息，我們可以這樣定義：

map<clientId,clientInfo> clientMap;

這樣我們定義了一個(gè)clientMap，如果我們要定義多個(gè)這樣的map，需要多次寫(xiě)map<clientId,clientInfo> 變量名。為了避免這樣情況，我們通常為map<clientId,clientInfo>定義個(gè)別名，如：

typedef map<clientId,clientInfo> clientEdp;
clientEdp clientMap;

之后我們就可以像定義clientMap一樣定義map<clientId,clientInfo>對(duì)象，這樣的好處還有：如果我們需要修改map的定義，只需要在一處修改即可，避免修改不徹底造成的不一致現(xiàn)象。

我們這就完成了需要的map的定義，如果不定義或沒(méi)有在它上面的操作的話，就像定義類而沒(méi)有方法一樣，意義不大或毫無(wú)意義。幸運(yùn)的是，STL提供了這些常用操作：排序（注：map是不能也不要排序的，因?yàn)閙ap本身已經(jīng)排好序了）、打印、提取子部分、移除元素、添加元素、查找對(duì)象，就像數(shù)據(jù)庫(kù)的增刪改查操作！現(xiàn)在我們?cè)敿?xì)介紹這些操作，并逐步引入hash_map、multimap。

2、map中的類型定義

關(guān)聯(lián)數(shù)組（associative array）是最有用的用戶定義類型之一，經(jīng)常內(nèi)置在語(yǔ)言中用于文本處理等。一個(gè)關(guān)聯(lián)數(shù)組通常也稱為map，有時(shí)也稱字典（dictionary），保存一對(duì)值。第一個(gè)值稱為key、第二個(gè)稱為映射值mapped-value。

標(biāo)準(zhǔn)map是定義在std命名空間中的一個(gè)模板，并表示為<map>。它首先定義了一組標(biāo)準(zhǔn)類型名字：

template<class Key,class T,class Cmp=less<key>,
class A=allocator<pair<const Key,T>>
class std::map
{
public:
//types
typedef Key    key_type;
typedef T    mapped_type;
typedef pair<const Key,T>    value_type;
typedef    Cmp    key_compare;
typedef A    allocator_type;
typedef    typename    A::reference    reference;
typedef    typename    A::const_reference    const_reference;
typedef    implementation_define1    iterator;
typedef implementation_define2    const_iterator;
typedef    typename    A::size_type    size_type;
typedef    typename    A::difference_type    difference_type;
typedef    std::reverse_iterator<iterator>    reverse_iterator;
typedef    std::reverse_iterator<const_iterator>    const_reverse_iterator;
//...
}

注意：map的value_type是一個(gè)(key,value)對(duì)，映射值的被認(rèn)為是mapped_type。因此，一個(gè)map是一個(gè)pair<const Key,mapped_type>元素的序列。從const Key可以看出，map中鍵key是不可修改的。

不得不提的是map定義中Cmp和A都是可選項(xiàng)。Cmp是定義在元素之間的比較方法，默認(rèn)是<操作；A即allocator用來(lái)分配和釋放map總鍵值對(duì)所需使用的內(nèi)存，沒(méi)有指定的話即默認(rèn)使用的是STL提供的，也可以自定義allocator來(lái)管理內(nèi)存的使用。多數(shù)情況，我們不指定這兩個(gè)選項(xiàng)而使用默認(rèn)值，這樣我們定義map就像下面這樣：

map<int,clientInfo> clientMap;

Cmp和A都缺省。 通常，實(shí)際的迭代器是實(shí)現(xiàn)定義的，因?yàn)閙ap很像使用了樹(shù)的形式，這些迭代器通常提供樹(shù)遍歷的某種形式。逆向迭代器是使用標(biāo)準(zhǔn)的reverse_iterator模板構(gòu)造的。

3、map中的迭代器和鍵值對(duì)

map提供慣常的返回迭代器的一組函數(shù)，如下所示：

template<class Key,class T,class Cmp=less<key>,
class A=allocator<pair<const Key,T>>
class std::map
{
public:
//...
//iterators
iterator    begin();
const_iterator    begin()    const;
iterator    end();
const_iterator    end()    const;
reverse_iterator    rbegin();
const_reverse_iterator    rbegin()    const;
reverse_iterator    rend();
const_reverse_iterator    rend()    const;
//...
}

map上的迭代器是pair<const Key,mapped_type>元素序列上簡(jiǎn)單的迭代。例如，我們可能需要打印出所有的客戶端信息，像下面的程序這樣。為了實(shí)現(xiàn)這個(gè)，我們首先向《例子引入》中定義的clientEdp中插入數(shù)據(jù)，然后打印出來(lái)：

#include<iostream>
#include<map>
#include<string>
using namespace std;
typedef    int    clientId;
typedef struct{
int scanRate;
string socketAddr;
}clientInfo;
int main(int argc,char** argv)
{
typedef map<clientId,clientInfo> clientEdp;
typedef map<clientId,clientInfo>::const_iterator iterator;
clientEdp clients;
clientInfo client[100];
char str[10];
string strAddr("socket addr client ");
for(int i=0;i<100;i++)
{
client[i].scanRate=i+1;
//convert int to char*
itoa(i+1,str,10);
//concatenate strAddr and str
client[i].socketAddr=strAddr+str;
cout<<client[i].socketAddr<<endl;
clients.insert(
make_pair(i+1,client[i]));
}
delete str;
for(iterator i=clients.begin();i!=clients.end();i++)
{
cout<<"clientId:"<<i->first<<endl;
cout<<"scanRate:"<<i->second.scanRate<<endl;
cout<<"socketAddr:"<<i->second.socketAddr<<endl;
cout<<endl;
}
}

一個(gè)map迭代器以key升序方式表示元素，因此客戶端信息以cliendId升序的方式輸出。運(yùn)行結(jié)果可以證明這一點(diǎn)，運(yùn)行結(jié)果如下所示：

圖1、程序運(yùn)行結(jié)果

我們以first引用鍵值對(duì)的key，以second引用mapped value，且不用管key和mapped value是什么類型。其實(shí)pair在std的模板中是這樣定義的：

template <class    T1,class T2>struct std::pair{
typedef    T1    first_type;
typedef    T2    second_type;
T1    first;
T2    second;
pair():first(T1()),second(T2()){}
pair(const T1& x,const T2& y):first(x),second(y){}
template<class U,class V>
pair(const pair<U,V>& p):first(p.first),second(p.second){}
}

即map中，key是鍵值對(duì)的第一個(gè)元素且mapped value是第二個(gè)元素。pair的定義可以在<utility>中找到，pair提供了一個(gè)方法方便創(chuàng)建鍵值對(duì)：

template <class T1,class T2>pair<T1,T2>
std::make_pair(const T1& t1,const T2& t2)
{
return pair<T1,T2>(t1,t2);
}

上面的例子中我們就用到了這個(gè)方法來(lái)創(chuàng)建(clientId,clientInfo)對(duì)，并作為Insert()方法的參數(shù)。每個(gè)pair默認(rèn)初始化每個(gè)元素的值為對(duì)應(yīng)類型的默認(rèn)值。

4、map中的構(gòu)造函數(shù)與析構(gòu)函數(shù)

map類慣常提供了構(gòu)造函數(shù)和析構(gòu)函數(shù)，如下所示：

template<class Key,class T,class Cmp=less<key>,
class A=allocator<pair<const Key,T>>
class std::map
{
//...
//construct/copy/destroy
explicit map(const Cmp&=Cmp(),const A&=A());
template<class In>map(In first,In last,
const Com&=Cmp(),const A&=A());
map(const map&);
~map();
map& operator=(const map&);
//...
}

復(fù)制一個(gè)容器意味著為它的每個(gè)元素分配空間，并拷貝每個(gè)元素值。這樣做是性能開(kāi)銷是很大的，應(yīng)該僅當(dāng)需要的時(shí)候才這樣做。因此，map傳的是引用。

5、map中的操作方法

前面我們已經(jīng)說(shuō)過(guò)，如果map中僅定義了一些key、mapped value類型的信息而沒(méi)有操作方法，就如定義個(gè)僅有字段的類意義不大甚至毫無(wú)意義。由此可見(jiàn)map中定義操作方法非常重要！前面的例子我們就用到了不少方法，如返回迭代器的方法begin()、end()，鍵值對(duì)插入方法insert()。下面我們對(duì)map中的操作方法做個(gè)全面的介紹：

template<class Key,class T,class Cmp=less<key>,
class A=allocator<pair<const Key,T>>
class std::map
{
//...
//map operations
//find element with key k
iterator find(const key_type& k);
const_iterator find(const key_type& k) const;
//find number of elements with key k
size_type count() const;
//find first element with key k
iterator lower_bound(const key_type& k);
const_iterator lower_bound(const key_type& k) const;
//find first element with key greater than k
iterator upper_bound(const key_type& k);
const_iterator upper_bound(const key_type& k) const;
//insert pair(key,value)
pair<iterator,bool>insert(const value_type& val);
iterator insert(iterator pos,const value_type& val);
template<class In>void insert(In first,In last);
//erase element
void erase(iterator pos);
size_type erase(const key_type& k);
void erase(iterator first,iterator last);
void clear();
//number os elements
size_type size() const;
//size of largest possible map
size_type max_size() const;
bool empty() const{return size()==0;}
void swap(map&);
//...
}

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

• find(k)方法簡(jiǎn)單地返回鍵值為k的元素的迭代器；如果沒(méi)有元素的鍵值為k，則返回map的end()迭代器。由于map是按鍵key升序排列，所有查找的復(fù)雜度只有O(logN)。因此，我們通常會(huì)這樣用這個(gè)方法：
  

  #include<iostream>
      #include<map>
      #include<string>
      using namespace std;
      typedef    int    clientId;
      typedef struct{
      int scanRate;
      string socketAddr;
      }clientInfo;
      int main(int argc,char** argv)
      {
      typedef map<clientId,clientInfo> clientEdp;
      typedef map<clientId,clientInfo>::const_iterator iterator;
      clientEdp clients;
      clientInfo client[100];
      char* str=new char[10];
      string strAddr("socket addr client ");
      for(int i=0;i<100;i++)
      {
      client[i].scanRate=i+1;
      //convert int to char*
      itoa(i+1,str,10);
      //concatenate strAddr and str
      client[i].socketAddr=strAddr+str;
      clients.insert(
      make_pair(i+1,client[i]));
      }
      delete str;
          clientId id=10;
      iterator i=clients.find(id);
      if(i!=clients.end()){
      cout<<"clientId: "<<id
      <<" exists in clients"<<endl;
      }
      else{
      cout<<"clientId: "<<id
      <<" doesn't exist in clients"<<endl;
      }
      }

• insert()方法 試圖將一個(gè)（Key,T）鍵值對(duì)加入map。因?yàn)殒I時(shí)唯一的，所以僅當(dāng)map中不存在鍵值為k的鍵值對(duì)時(shí)插入才成功。該方法的返回值為pair<iterator,bool>，如果插入成功bool值為T(mén)RUE，iterator指向插入map中后的鍵值對(duì)。如下代碼：
  

  #include<iostream>
      #include<map>
      #include<string>
      using namespace std;
      typedef    int    clientId;
      typedef struct{
      int scanRate;
      string socketAddr;
      }clientInfo;
      int main(int argc,char** argv)
      {
      typedef map<clientId,clientInfo> clientEdp;
      typedef map<clientId,clientInfo>::const_iterator iterator;
      clientEdp clients;
      clientId id=110;
      clientInfo cltInfo;
      cltInfo.scanRate=10;
      cltInfo.socketAddr="110";
      pair<clientId,clientInfo> p110(id,cltInfo);
      pair<iterator,bool> p=clients.insert(p110);
      if(p.second){
      cout<<"insert success!"<<endl;
      }
      else{
      cout<<"insert failed!"<<endl;
      }
      //i points to clients[110];
      iterator i=p.first;
      cout<<i->first<<endl;
      cout<<i->second.scanRate<<endl;
      cout<<i->second.socketAddr<<endl;
      }

上面我們看出，這里我們插入鍵值對(duì)是首先聲明一個(gè)鍵值對(duì)pair<clientId,clientInfo> p110(id,cltInfo); 然后再插入，這個(gè)我們之前make_pair方法不一樣，make_pair方法用的比較多。

• erase()方法用法比較簡(jiǎn)單，比如像清除clientId為110的鍵值對(duì)，我們只需要對(duì)clients調(diào)用erase方法：clients.erase(clients.find(110));或者我們想清除clientId從1到10的鍵值對(duì)，我們可以這樣調(diào)用erase()方法：clients.erase(clients.finds(1),clients.find(10));簡(jiǎn)單吧！別得意，你還需要注意，如果find(k)返回的是end()，這樣調(diào)用erase()方法則是一個(gè)嚴(yán)重的錯(cuò)誤，會(huì)對(duì)map造成破壞操作。

6、再議map的插入操作

前面我們介紹了利用map的插入方法insert()，聲明鍵值對(duì)pair或make_pair生成鍵值對(duì)然后我們可以輕松的將鍵值對(duì)插入map中。其實(shí)map還提供了更方便的插入操作利用下標(biāo)（subscripting，[]）操作，如下：

clientInfo cltInfo;
cltInfo.scanRate=10;
cltInfo.socketAddr="110";
clients[110]=cltInfo;

這樣我們就可以簡(jiǎn)單地將鍵值對(duì)插入到map中了。下標(biāo)操作在map中式這樣定義的：

template<class Key,class T,class Cmp=less<key>,
class A=allocator<pair<const Key,T>>
class std::map
{
//...
//access element with key k
mapped_type& operator[](const key_type& k);
//...
}

我們來(lái)分析一下應(yīng)用[]操作，插入鍵值對(duì)的過(guò)程：檢查鍵k是否已經(jīng)在map里。如果不，就添加上，以v作為它的對(duì)應(yīng)值。如果k已經(jīng)在map里，它的關(guān)聯(lián)值被更新成v。這里首先，查找110不在map中則創(chuàng)建一個(gè)鍵為110的鍵值對(duì)，并將映射值設(shè)為默認(rèn)值，這里scanRate為0，socketAddr為空；然后將映射值賦為cltInfo。 如果110在map中已經(jīng)存在的話，則只是更新以110為鍵的映射值。

從上面的分析可知：如果大量這樣插入數(shù)據(jù)，會(huì)嚴(yán)重影響效率！如果你考慮效率問(wèn)題，請(qǐng)使用insert操作。insert方法，節(jié)省了三次函數(shù)調(diào)用：一個(gè)建立臨時(shí)的默認(rèn)映射值的對(duì)象，一個(gè)銷毀那個(gè)臨時(shí)的對(duì)象和一個(gè)對(duì)映射值的賦值操作。

Note1：如果k已經(jīng)存在map中，[]效率反而比insert的效率高，而且更美觀！如果能夠兼顧這兩者那豈不是很美妙！其實(shí)我們重寫(xiě)map中的[]操作：首先判斷k是否已經(jīng)在map中，如果沒(méi)有則調(diào)用insert操作，否則調(diào)用內(nèi)置的[]操作。如下列代碼：

//////////////////////////////////////////////
///@param MapType-map的類型參數(shù)
///@param KeyArgType-鍵的類型參數(shù)
///@param ValueArgtype-映射值的類型參數(shù)
///@return 迭代器，指向鍵為k的鍵值對(duì)
//////////////////////////////////////////////
template<typename MapType,
typename KeyArgType,
typename ValueArgtype>
typename MapType::iterator
efficientAddOrUpdate(MapType& m,
const KeyArgType& k,
const ValueArgtype& v)
{
typename MapType::iterator Ib =    m.lower_bound(k);
if(Ib != m.end()&&!(m.key_comp()(k,Ib->first))) {
//key已經(jīng)存在于map中做更新操作
Ib->second = v;
return Ib;
}
else{
//key不存在map中做插入操作
typedef typename MapType::value_type MVT;
return m.insert(Ib, MVT(k, v));
}
}

Note2：我們視乎還忽略了一點(diǎn)，如果映射值mapped value的類型沒(méi)有默認(rèn)值，怎么辦？這種情況請(qǐng)勿使用[]操作插入。

7、[]不僅插入

通過(guò)[]操作不僅僅是插入鍵值對(duì)，我們也可以通過(guò)鍵key檢索出映射值mapped value。而且我們利用[]操作可以輕松地統(tǒng)計(jì)信息，如有這樣這樣一些鍵值對(duì)（book-name，count）對(duì)：

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

我們計(jì)算每種book的數(shù)量總和。我們可以這樣做：將它們讀入一個(gè)map<string,int>：

#include<iostream>
#include<map>
#include<string>
using namespace std;
int main(int argc,char** argv)
{
map<string,int> bookMap;
string book;
int count;
int total=0;
while(cin>>book>>count)
bookMap[book]+=count;
map<string,int>::iterator i;
for(i=bookMap.begin();i!=bookMap.end();i++)
{
total+=i->second;
cout<<i->first<<'\t'<<i->second<<endl;
}
cout<<"total count:"<<total<<endl;
}

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

圖2、程序運(yùn)行結(jié)果

8、multimap

前面介紹了map，可以說(shuō)已經(jīng)非常清晰了。如果允許clientId重復(fù)的話，map就無(wú)能為力了，這時(shí)候就得multimap上場(chǎng)了！multimap允許鍵key重復(fù)，即一個(gè)鍵對(duì)應(yīng)多個(gè)映射值。其實(shí)除此之外，multimap跟map是很像的，我們接下來(lái)在map的基礎(chǔ)上介紹multimap。

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

• multimap不支持[]操作；但map支持
• multimap的insert方法返回的是一個(gè)迭代器iterator，沒(méi)有bool值；而map值（iterator，bool）的元素對(duì)
• 對(duì)應(yīng)equal_range()、方法：

  pair<iterator,iterator> equal_range(const key_type& k);
      pair<const_iterator,const_iterator>
      equal_range(const key_type& k) const;
      //find first element with key k
      iterator lower_bound(const key_type& k);
      const_iterator lower_bound(const key_type& k) const;
      //find first element with key greater than k
      iterator upper_bound(const key_type& k);
      const_iterator upper_bound(const key_type& k) const;

  雖然在map和multimap都有，顯然對(duì)multimap有更多的意義！equal_range()方法返回一個(gè)鍵key對(duì)應(yīng)的多個(gè)映射值的上界和下界的鍵值對(duì)的迭代器、lower_bound()方法返回鍵multimap中第一個(gè)箭為key的鍵值對(duì)迭代器、upper_bound()方法返回比key大的第一個(gè)鍵值對(duì)迭代器。

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

#include<iostream>
#include<map>
#include<string>
using namespace std;
typedef int clientId;
typedef struct{
int scanRate;
string socketAddr;
}clientInfo;
int main(int argc,char** argv)
{
typedef multimap<clientId,clientInfo> clientEdp;
typedef multimap<clientId,clientInfo>::const_iterator iterator;
clientEdp clients;
clientInfo client[20];
char* str=new char[10];
string strAddr("socket addr client ");
for(int i=0;i<10;i++)
{
client[i].scanRate=i+1;
//convert int to char*
itoa(i+1,str,10);
//concatenate strAddr and str
client[i].socketAddr=strAddr+str;
clients.insert(
make_pair(10,client[i]));
}
for(int i=10;i<20;i++)
{
client[i].scanRate=i+1;
//convert int to char*
itoa(i+1,str,10);
//concatenate strAddr and str
client[i].socketAddr=strAddr+str;
clients.insert(
make_pair(i+1,client[i]));
}
delete str,strAddr;
    //find elements with key 10
iterator lb=clients.lower_bound(10);
iterator ub=clients.upper_bound(10);
for(iterator i=lb;i!=ub;i++)
{
cout<<"clientId:"<<i->first<<endl;
cout<<"scanRate:"<<i->second.scanRate<<endl;
cout<<"socketAddr:"<<i->second.socketAddr<<endl;
cout<<endl;
}
}

（說(shuō)明：實(shí)際上，一般是不允許clientId重復(fù)的，這里只是為了舉例。）這樣是不是感覺(jué)很丑呢！事實(shí)上，我們可以更簡(jiǎn)單的這樣：

//find elements with key 10
pair<iterator,iterator> p=clients.equal_range(10);
for(iterator i=p.first;i!=p.second;i++)
{
cout<<"clientId:"<<i->first<<endl;
cout<<"scanRate:"<<i->second.scanRate<<endl;
cout<<"socketAddr:"<<i->second.socketAddr<<endl;
cout<<endl;
}

總結(jié)

map是一類關(guān)聯(lián)式容器。它的特點(diǎn)是增加和刪除節(jié)點(diǎn)對(duì)迭代器的影響很小，除了那個(gè)操作節(jié)點(diǎn)，對(duì)其他的節(jié)點(diǎn)都沒(méi)有什么影響。對(duì)于迭代器來(lái)說(shuō)，可以修改實(shí)值，而不能修改key。

map的功能：

• 自動(dòng)建立Key －value的對(duì)應(yīng)。key 和value可以是任意你需要的類型。
• 根據(jù)key值快速查找記錄，查找的復(fù)雜度基本是Log(N)。
• 快速插入Key - Value 記錄。
• 快速刪除記錄
• 根據(jù)Key 修改value記錄。
• 遍歷所有記錄。

展望：本文不知不覺(jué)寫(xiě)了不少字了，但仍未深入涉及到map定義的第3個(gè)和第4個(gè)參數(shù)，使用的都是默認(rèn)值。

template<class Key,class T,class Cmp=less<key>,
    class A=allocator<pair<const Key,T>>

感興趣者，請(qǐng)查找相關(guān)資料or下面留言希望看到單獨(dú)開(kāi)篇介紹map第3個(gè)和第4個(gè)參數(shù)。您的支持，我的動(dòng)力！PS：在此文的原因，在與公司做項(xiàng)目用到了map特此總結(jié)出來(lái)與大家共享，不過(guò)在進(jìn)行個(gè)人總結(jié)過(guò)程中，難免會(huì)有疏漏或不當(dāng)之處，請(qǐng)不吝指出。

參考文獻(xiàn)：

【1】《The C++ Programming Language (Special Edition)》

【2】《Effective STL》