STL中multimap容器簡要介紹

文/崔馭 孫佳澤 焦靜頤

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

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

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

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

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

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

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

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

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

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

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

multimap<鍵值類型，值類型>對象名稱

例如：multimapM;

3 在multimap對象中插入數(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）利用下標操作符 具體代碼如下：

M[“hard”]=13;

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

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

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

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

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

對multimap容器數(shù)據(jù)遍歷的實現(xià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容器中進行數(shù)據(jù)查找，還需掌握查找相同鍵的鍵值對方法。

（1）使用f ind和count進行查找

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

f ind(key)返回第一個擁有鍵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進行查找

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

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

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() 返回溢出元素的個數(shù)

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

int cnt;

cnt=M.erase(1);

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

（2）使用multimap容器中迭代器進行刪除

multimap::iterator it;

it=M.f ind(key);

if(it!=M.end())

M.erase(it);

7 結(jié)束語

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