一、 map
头文件 #include<map>
1)map的定义：
map<键数据类型,值数据类型> m;
或者
typedef map <数据类型,值数据类型> M;
M m;
2)元素的插入
map<int,int> m;
最常用的 m[key]=value; //m[1]=2;
m.insert(pair<int,string>(1,2));
3)元素的查找
find()函数 返回一个迭代器指向键值为key的元素，如果没找到就返回指向map尾部的迭代器。
map<int,int> ::iterator it;
it=m.find(1);
if(it==m.end())
cout<<"Not Found"<<endl;
这里要注意一个问题
M m;
cout<<m.size()<<endl;
m[1];
cout<<m.size()<<endl;
即使我们不对m[1]赋值，这是也相当于在map容器里插入了一个数据键为1，
所以有时候判断这个元素是否存在是千万不能用m[xx]!=0因为如果不存在的话，map的大小会加1
4)元素的删除
erase
可以删除指定元素
也可以删除迭代器指定的元素
#include <iostream>
#include<map>
using namespace std;
typedef map<int,int> Map;
int main()
{
Map m;
for(int i=10;i<20;i++)
m[i]=i*2;
m.erase(18);
Map::iterator it;
it=m.find(19);
if(it==m.end())
cout<<"NOT"<<endl;
else
m.erase(it);
for(it=m.begin();it!=m.end();it++)
{
cout<<it->first<<" "<<it->second<<endl;
}
return 0;
}
5)swap() 完成2个map容器的交换
map中的元素按照键值的大小升序排列
6) map中可以按照键值的从大到小输出
map<int,int> m; m[2]=1; m[1]=2; m[3]=7; map<int,int>::reverse_iterator it; for(it=m.rbegin();it!=m.rend();it++){ cout<<it->first<<" "<<it->second<<endl; }
二 、multimap
- multimap多重映照容器:容器的数据结构采用红黑树进行管理
- multimap的所有元素都是pair:第一元素为键值(key),不能修改;第二元素为实值(value),可被修改
- multimap特性以及用法与map完全相同，唯一的差别在于:
- 允许重复键值的元素插入容器(使用了RB-Tree的insert_equal函数)
- 因此: 键值key与元素value的映照关系是多对多的关系
- 没有定义[]操作运算
1)定义
multimap<int,int> a;
2)插入元素
multimap<int,int> a;
a.insert(pair<int,int>(1,1)) ;
a.insert(pair<int ,int>(1,2));
a.insert(pair<int,int>(1,3));
a.insert(pair<int,int>(2,3));
a.insert(pair<int,int>(2,4));
a.insert(pair<int,int>(2,5));
a.insert(pair<int,int>(3,6));
a.insert(pair<int,int>(3,7));
3)删除元素
erase(key)：会删除以这个key为键的所有值
4)查找元素
#include <iostream>
#include<map>
using namespace std;
typedef map<int,int> Map;
int main()
{
multimap<int,int> a;
a.insert(pair<int,int>(1,1)) ;
a.insert(pair<int ,int>(1,2));
a.insert(pair<int,int>(1,3));
a.insert(pair<int,int>(2,3));
a.insert(pair<int,int>(2,4));
a.insert(pair<int,int>(2,5));
a.insert(pair<int,int>(3,6));
a.insert(pair<int,int>(3,7));
a.erase(1);
pair<multimap<int,int>::iterator,multimap<int,int>::iterator> ret;
multimap<int,int> ::iterator it;
for(it=a.begin();it!=a.end();){
cout<<it->first<<":";
ret=a.equal_range(it->first);
for(it=ret.first;it!=ret.second;it++){
cout<<(*it).second<<" ";
}
cout<<endl;
}
return 0;
}
如果将上面的访问容器那一部分改为:
multimap<int,int> ::iterator it;
for(it=a.begin();it!=a.end();it++){
cout<<it->first<<": ";
cout<<it->second<<endl;
}
结果将是：
这说明我们用这种方式也可以访问。
下面是一道UVA的题目
Your non-profit organization (iCORE - international Confederation of Revolver Enthusiasts)
coordinates a very successful foreign student exchange program. Over the last few years, demand
has sky-rocketed and now you need assistance with your task.
The program your organization runs works as follows: All candidates are asked for their original
location and the location they would like to go to. The program works out only if every student has
a suitable exchange partner. In other words, if a student wants to go from A to B, there must be
another student who wants to go from B to A. This was an easy task when there were only about 50
candidates, however now there are up to 500000 candidates!
Input
The input file contains multiple cases. Each test case will consist of a line containing n - the
number of candidates (1≤n≤500000), followed by n lines representing the exchange information for
each candidate. Each of these lines will contain 2 integers, separated by a single space, representing
the candidate's original location and the candidate's target location respectively. Locations will be
represented by nonnegative integer numbers. You may assume that no candidate will have his or
her original location being the same as his or her target location as this would fall into the domestic
exchange program. The input is terminated by a case where n = 0; this case should not be
processed.
Output
For each test case, print "YES" on a single line if there is a way for the exchange program to work
out, otherwise print "NO".
这是UVA 10763 题目大意是：有n个学生想要交换到其他学校，为了简单起见，规定，每个想从A到B的学生必须找一个想从B到A的搭档，学校就会同意他们的交换，给出n个学生的初始学校和他们想要换到的学校，问是否能都满足学生。
这个题目是典型的多对多的关系，所以用 multimap
#include <iostream>
#include<map>
using namespace std;
typedef multimap<int,int> Map;
int main()
{
Map m;
int a,b,n;
bool flag;
while(cin>>n){
if(n==0) break;
m.clear();
for(int i=0;i<n;i++){
flag=true;
cin>>a>>b;
Map::iterator it;
for(it=m.find(b);it!=m.end()&&it->first==b;it++)
if(it->second==a){
flag=false;
m.erase(it);
break;
}
if(flag==true)
m.insert(pair<int,int>(a,b));
}
if(m.empty())
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}