STL中multimap容器簡(jiǎn)要介紹

文/崔馭 孫佳澤 焦靜頤

1 multimap容器的基本原理及與map的主要區(qū)別

Multimap是STL中的標(biāo)準(zhǔn)容器，它是一種關(guān)聯(lián)型容器，可以保存鍵值對(duì)，對(duì)數(shù)據(jù)進(jìn)行關(guān)聯(lián)性保存。Multimap與map一樣，底層使用了紅黑樹(shù)數(shù)據(jù)結(jié)構(gòu)來(lái)進(jìn)行數(shù)據(jù)數(shù)據(jù)管理。他們都可以根據(jù)key的排序準(zhǔn)則自動(dòng)將元素排序。他們的主要區(qū)別就是multimap允許重復(fù)元素，而map不允許。

使用multimap之前，需引入頭文件

2 multimap容器的操作函數(shù)

multimap容器的各項(xiàng)操作函數(shù)主要是用于進(jìn)行生成，復(fù)制，銷毀等各項(xiàng)操作

這里列出multimap容器最常用的幾種構(gòu)造函數(shù)和析構(gòu)函數(shù)：

multimap mm:創(chuàng)建空映射,不包含任何元素

multimap mm(op):以op為排序準(zhǔn)則，產(chǎn)生一個(gè)空的multimap

multimap m(const value_type *first, const value_type* last):復(fù)制[f irst, last)之間元素構(gòu)成新映射

m.~multimap():銷毀所有元素，釋放內(nèi)存

以上是常用的操作函數(shù)。對(duì)于multimap的構(gòu)造方法，在這里只講解最常用的一種形式

multimap<鍵值類型，值類型>對(duì)象名稱

例如：multimapM;

3 在multimap對(duì)象中插入數(shù)據(jù)

在multimap插入數(shù)據(jù)的常用方法有三種

（1）利用value_type 具體代碼如下：

typedef multimap StrIntMultimap;

StrIntMultimap M;

M.insert(StrIntMultimap:: value_type(“hello”,10));

（2）利用pair 具體代碼如下：

M.insert(pair (“world”,11));

（3）利用下標(biāo)操作符 具體代碼如下：

M[“hard”]=13;

4 multimap容器中的數(shù)據(jù)遍歷

multimap不支持元素直接存取，所以通過(guò)multimap迭代器來(lái)完成對(duì)multimap容器中數(shù)據(jù)的遍歷操作。

multimap的迭代器相關(guān)函數(shù)

M.begin() 返回一個(gè)雙向迭代器，指向首元素

M.end () 返回一個(gè)雙向迭代器，指向尾元素的下一個(gè)位置

對(duì)multimap容器數(shù)據(jù)遍歷的實(shí)現(xiàn)主要使用以下方法：

利用雙向迭代器進(jìn)行遍歷，具體代碼如下

multimap::iterator it;

for(it=M.begin;it!=M.end();it++)

cout<f irst<<” “<second<

5 multimap容器中的數(shù)據(jù)查找

由于multimap是可以出現(xiàn)重復(fù)鍵值的，所以與map相比在multimap容器中進(jìn)行數(shù)據(jù)查找，還需掌握查找相同鍵的鍵值對(duì)方法。

（1）使用f ind和count進(jìn)行查找

count(key)求出鍵key出現(xiàn)的次數(shù)

f ind(key)返回第一個(gè)擁有鍵key的元素

示例代碼：

int cnt=M.count(key);

multimap::iterator it;

it=M.f ind(key);

for(;cnt>=0;cnt--,it++)

cout<f irst<<” “<second<

（2）使 用lower_bound與upper_bound進(jìn)行查找

lower_bound(key)返回指向不小于key的第一個(gè)元素的迭代器

upper_bound(key)返回指向 大于key的第一個(gè)元素的迭代器

multimap::iterator itBeg=M. lower_bound(key);

multimap::iterator itEnd=M. upper_bound(key);

for(;itBeg!= itEnd;cnt--, itBeg ++)

cout<< itBeg ->first<<” “<< itBeg ->second<

6 multimap容器中的數(shù)據(jù)刪除

erase() 返回溢出元素的個(gè)數(shù)

（1）使用multimap容器中的關(guān)鍵字kry進(jìn)行數(shù)據(jù)刪除

int cnt;

cnt=M.erase(1);

因?yàn)閙ultimap內(nèi)含有重復(fù)的元素，這個(gè)方法會(huì)將重復(fù)元素都刪去，如果想刪除重復(fù)元素中的第一個(gè)元素，可以使用方法（2）

（2）使用multimap容器中迭代器進(jìn)行刪除

multimap::iterator it;

it=M.f ind(key);

if(it!=M.end())

M.erase(it);

7 結(jié)束語(yǔ)

Multimap是STL中標(biāo)準(zhǔn)容器之一，它的特性使它能夠完成很多map無(wú)法實(shí)現(xiàn)的操作。無(wú)論是在日常開(kāi)發(fā)還是在算法競(jìng)賽中，multimap都以它能夠關(guān)聯(lián)數(shù)據(jù)且允許重復(fù)元素的特性發(fā)揮著巨大作用。掌握好multimap容器對(duì)學(xué)習(xí)好STL其他容器和算法有很大幫助，并能提高學(xué)生的程序編程能力。