C++ multimap,STL multimap详解
注意,不能直接修改 multimap 容器中的关键字。因为 multimap 中的元素是按照关键字排序的,当关键字被修改后,容器并不会自动重新调整顺序,于是容器的有序性就会被破坏,再在其上进行查找等操作就会得到错误的结果。
使用 multimap 必须包含头文件 map。multimap 的定义如下:
template class Key, class T, class Pred = less Key , class A = allocator T
class multimap
{
typedef pair const Key, T value_type;
};
multimap 中的元素都是 pair 模板类的对象。元素的 first 成员变量也叫 关键字 ,second 成员变量也叫 值 。multimap 容器中的元素是按关键字从小到大排序的。默认情况下,元素的关键之间用 less Key 比较大小,也就是用 运算符比较大小。multimap 允许多个元素的关键字相同。
multimap 中的 value_type 实际上就表示容器中元素的类型。C++ 允许在类的内部定义类型。
multimap 的成员函数(未列出每个函数的所有版本)如表 1 所示。
pair iterator, iterator equal_range (const Key val); 同时求得 lower_bound 和 upper_bound
删除 it 指向的元素,返回其后面的元素的迭代器(Visual Studio 2010 中如此,但是在 C++ 标准和 Dev C++ 中,返回值不是这样)
删除区间 [first, last),返回 last(Visual Studio 2010 中如此,但是在 C++ 标准和 Dev C++ 中,返回值不是这样)
multimap 及 map 中的 find 和 count 不用==运算符比较两个关键字是否相等。如果x比y小和y比x小同时为假,就认为 x 和 y 相等。
例题:一个学生成绩录入和查询系统接受以下两种输入:
1) Add name id score
2) Query score
name 是一个字符串,其中不包含空格,表示学生姓名。id 是一个整数,表示学号。score 是一个整数,表示分数。学号不会重复,分数和姓名都可能重复。
两种输入交替出现。
第二种输入表示要查询分数为 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
此题如果用 vector 存放所有学生的信息,然后进行顺序查找的话,在学生数量很大和查询很多的情况下非常费时,因为顺序查找的时间复杂度是 O(n)。将 vector 排序后再查找也不行,因为会不断插入新元素,每次插入新元素就要进行元素的移动,而这一步骤的时间复杂度是O(n),这会导致效率低下。
下面程序的思路是用 multimap 存放学生信息,使学生信息按照分数排序。
要添加学生时,就用 insert 成员函数插入学生记录,这步操作的时间复杂度是 O(log(n))。
输入一个要查询的分数 score 时,就用 lower_bound 求得该分数对应的下界 迭代器 p(这一步的时间复杂度是 O(log(n))。 *p 这个元素的分数是大于或等于 score 的,往前再找一个元素,其分数就是低于 score 的最高分了。继续往前遍历所有等于该分数的元素,找出 id 最大的元素输出即可。
解题程序如下:
#include iostream #include map //使用multimap需要包含此头文件 #include string using namespace std; class CStudent public: struct CInfo //类的内部还可以定义类 int id; string name; int score; CInfo info; //学生的其他信息 typedef multimap int, CStudent::CInfo MAP_STD; int main() MAP_STD mp; CStudent st; string cmd; while (cin cmd) { if (cmd == Add ) { cin st.info.name st.info.id st.score; mp.insert(MAP_STD::value_type(st.score, st.info)); else if (cmd == Query ) { int score; cin score; MAP_STD::iterator p = mp.lower_bound(score); if (p != mp.begin()) { --p; score = p- first; //比要查询分数低的最高分 MAP_STD::iterator maxp = p; int maxId = p- second.id; for (; p != mp.begin() p- first == score; --p) { //遍历所有成绩和score相等的学生 if (p- second.id maxId) { maxp = p; maxId = p- second.id; if (p- first == score) { //如果上面的循环因为 p == mp.begin() //而终止,则p指向的元素还要处理 if (p- second.id maxId) { maxp = p; maxId = p- second.id; cout maxp- second.name maxp- second.id maxp- first endl; else //lower_bound 的结果就是 begin,说明没有分数比查询分数低 cout Nobody endl; return 0; }
multimap 容器中的元素必须是 pair 类模板对象。本题需要用 multimap 来存放学生信息,然而学生信息由三部分组成:姓名、学号、分数,解决的办法就是将用于排序的 score 作为一个成员变量,而且把其他部分一起作为一个 CInfo 对象,这样,第 16 行实例化出来的类 multimap int, CStudent::CInfo 中的元素的类型就会是如下 pair 模板类:
class pair int, CStudent::CInfo
{
int first; //对应于CStudent::score
CStudent::CInfo second; //对应于 CStudent::info
};
第 26 行如下:
mp.insert( MAP_STD::value_type(st.score, st.info) );
参看 multimap 的定义,MAP_STD::value_type 就是容器中元素的类型,该类型是 pair int, CStudent::CInfo 。类型名后面跟构造函数的参数表就代表一个对象。因此,此条语句生成了一个 pair int, CStudent::CInfo 对象并将其插入 multimap 容器中。该对象内部存放的信息和 st 相同,first 对应于 st.score,second 对应于 st.info。
第 31 行,lower_bound 的返回结果 p 满足以下条件:[begin(), p) 中的分数都比查询分数低,但是 *p 的分数不比查询分数低。所以执行 p 操作之后,*p 的分数就是低于查询分数的最高分了。
21630.html
chtml相关文章
- C/C++指针详解之基础篇(史上最全最易懂指针学习指南!!!!)「建议收藏」
- C++之constexpr详解
- C++中STL-set详解
- C++ TCP winsock 多线程编程详解编程语言
- C++三大特性之继承详解编程语言
- C++STL中map容器的说明和使用技巧(杂谈)详解编程语言
- C++STL中set的使用策略(详解)编程语言
- C++11新特性之operator “” xxx(const char *, size_t n)详解编程语言
- 【转】c++中的new/delete详解编程语言
- Sunday 字符串匹配算法(C++实现)详解编程语言
- C++ queue(STL queue)用法详解
- C++ map插入数据(STL map插入数据)详解
- C++ multimap(STL multimap)的使用详解
- C++ set迭代器(STL set迭代器)详解
- C++ set_intersection(STL set_intersection)用法详解
- c++ set_difference(STL set_difference)算法详解
- C++ partial_sort(STL partial_sort)排序算法详解
- C++ upper_bound(STL upper_bound)二分查找算法详解
- C++输入流迭代器(STL输入流迭代器)详解
- C++重载插入运算符(<<)和提取运算符(>>)详解
- C++自增自减运算符(++和–)用法详解
- C++类对象作为函数参数传递详解
- 冒泡排序(C++)算法详解
- C++ share_ptr智能指针使用详解
- C++ STL list容器底层实现(详解版)