STL之multimap

multimap的用法

multimap容器里的元素，都是pair形式的

multimap<T1,T2> mp;

则mp里的元素都是如下类型的：

struct {
	T1 first; 		//关键字
	T2 second; 		//值
}

multimap中的元素按照first进行排序，并可以按first进行查找

**缺省的排序规则是a.first < b.first**时为true,则a排在b前面

multimap的应用

#include<iostream>
#include<map>//使用multimap和map需要次头文件 
#include<cstring>
using namespace std;
struct StudentInfo {
	int id;
	char name[20];
};
struct Student {
	int score;
	StudentInfo info;
};
typedef multimap<int, StudentInfo> MAP_STD; //取别名 
int main()
{
	MAP_STD mp;
	Student st;
	char cmd[20];
	while( cin >> cmd ) {//输入，根据首字母判断是Add还是Query 
		if( cmd[0] == 'A' ) {//Add,添加数据 
			cin>>st.info.name >> st.info.id>> st.score;
			mp.insert(make_pair(st.score, st.info));
			//make_pair生成了一个pair<int, StudentInfo>变量，其first等于st.score,second等于st.info 
		}
		else if( cmd[0] == 'Q'){//Query,查找数据 
			int score;
			cin>>score;
			MAP_STD::iterator p = mp.lower_bound (score);
			if( p != mp.begin()) {//查找成功，存在比score分数低的学生 
				--p;
				score = p->first;//比查询分数低的最高分 
				MAP_STD::iterator maxp = p;
				int maxId = p->second.id;
				while(p!= mp.begin() && p->first == score){//遍历所有成绩和score相等的学生 
					if(p->second.id > maxId ){//同分找学号最大的 
						maxp = p;
						maxId = p->second.id;
					}
					p--;
				}
				if(p->first == score){//上面循环因p == mp.begin()终止，但此时p指向mp的第一个元素，仍需要进行处理 
					if(p->second.id > maxId ){ 
						maxp = p;
						maxId = p->second.id;
				}
			}
			cout<< maxp->second.name <<' '<< maxp->second.id <<' '<< maxp->first <<endl;
		}
		else cout<< "Nobody" << endl;//未查找到 
	}
	}
	return 0;
}