STL中multimap容器簡要介紹

文/崔馭 孫佳澤 焦靜頤

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

Multimap是STL中的標準容器，它是一種關聯型容器，可以保存鍵值對，對數據進行關聯性保存。Multimap與map一樣，底層使用了紅黑樹數據結構來進行數據數據管理。他們都可以根據key的排序準則自動將元素排序。他們的主要區別就是multimap允許重復元素，而map不允許。

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

2 multimap容器的操作函數

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

這里列出multimap容器最常用的幾種構造函數和析構函數：

multimap mm:創建空映射,不包含任何元素

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

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

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

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

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

例如：multimapM;

3 在multimap對象中插入數據

在multimap插入數據的常用方法有三種

（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容器中的數據遍歷

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

multimap的迭代器相關函數

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

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

對multimap容器數據遍歷的實現主要使用以下方法：

利用雙向迭代器進行遍歷，具體代碼如下

multimap::iterator it;

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

cout<f irst<<” “<second<

5 multimap容器中的數據查找

由于multimap是可以出現重復鍵值的，所以與map相比在multimap容器中進行數據查找，還需掌握查找相同鍵的鍵值對方法。

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

count(key)求出鍵key出現的次數

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容器中的數據刪除

erase() 返回溢出元素的個數

（1）使用multimap容器中的關鍵字kry進行數據刪除

int cnt;

cnt=M.erase(1);

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

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

multimap::iterator it;

it=M.f ind(key);

if(it!=M.end())

M.erase(it);

7 結束語

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