C++ STL熟悉并巩固（十二）------multimap
本文中的一些重要概念摘自C语言中文网
链接：http://c.biancheng.net/view/388.html
multimap 是一种关联容器，它的每一个元素都是一个键值对。容器中的元素是按关键字（也就是键的值）排好序的。允许有多个关键字的值相同。
同样，作为一个关联容器，我们不能随意更改关键字的值，因为它并不会自动给容器中的元素进行重新排序，因此想要修改容器中的值，应该先删除这个元素，再插入一个元素。
想要使用multimap就必须要包含头文件map
multimap中的元素都是pair模板类对象，把pair对象中的first当做键名，把second当做键值
multimap的成员函数
注：find 和 count 不用==运算符比较两个关键字是否相等。如果x比y小和y比x小同时为假，就认为 x 和 y 相等。
了解了这些有用的成员函数之后呢，我们来看一下下面的例题：
例题：一个学生成绩录入和查询系统接受以下两种输入：
1) Add name id score
2) Query score
name 是一个字符串，其中不包含空格，表示学生姓名。id 是一个整数，表示学号。score 是一个双精度浮点数，表示分数。学号不会重复，分数和姓名都可能重复。
两种输入交替出现。
第一种输入表示要添加一个学生的信息，碰到这种输入，就记下学生的姓名、id 和分数。
第二种输入表示要查询分数为 score 的学生的信息，碰到这种输入，就输出已有记录中分数比查询分数低的最高分获得者的姓名、学号和分数。如果有多个学生满足条件，则输出学号最大的学生的信息。如果找不到满足条件的学生，则输出“Nobody”。
输入样例：
Add Jack 12 78
Query 78
Query 81
Add Percy 9 81
Add Marry 8 81
Query 82
Add Tom 11 79
Query 80
Query 81
输出结果样例：
Nobody
Jack 12 78
Percy 9 81
Tom 11 79
Tom 11 79
从题目要求中我们可以看到，这个业务对插入和查询操作需求量比较大，所以肯定不能用顺序容器，因为本身顺序容器是没有排好序的，进行查询操作会比较耗时，是O(n)的时间复杂度，同时由于顺序容器的内存是连续分配的，所以插入效率也不高。这时候我们就要想到关联容器了，由于这里的查找操作是根据分数score来进行的，而分数肯定是可以重复的，所以这时候我们要想到用multimap,让score做键名，让学号和姓名组成的结构做键值。
下面是实现的代码：
#include<iostream>
#include<string>
#include<map>
using namespace std;
class Student
{
public:
struct stu_info{ //C++支持在类中定义结构
string name;
int id;
};
Student() {}
stu_info st;
double score;
};
typedef multimap<double, Student> Stu_info;
int main()
{
Stu_info students;
string cmd;
while(cin >> cmd)
{
if(cmd == "Add")
{
Student student;
cin >> student.st.name >> student.st.id >> student.score;
pair<double, Student> s(student.score, student);
students.insert(s);
}
else if(cmd == "Query")
{
double sco = 0;
cin >> sco;
Stu_info::iterator i = students.lower_bound(sco);
if(i != students.begin())
{
--i;
Stu_info::iterator maxp = i;
int maxid = i->second.st.id;
for(; i != students.begin() && i->first == sco; --i)
{
if(i->second.st.id > maxid)
{
maxid = i->second.st.id;
maxp = i;
}
}
if(i->first == sco)
{
maxp = i;
maxid = i->second.st.id;
}
cout << maxp->second.st.name << " " << maxp->second.st.id
<< " " << maxp->first << endl;
}
else
{
cout << "Nobody" << endl;
}
}
}
return 0;
}例题的输出结果：
本节完
