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;
}

例题的输出结果：

本节完