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其他容器和算法有很大帮助，并能提高学生的程序编程能力。