四、C++中的multiset
- multiset的介绍：
multiset容器与set容器实现和接口基本一致，唯一区别就是，multiset允许键值冗余，即multiset容器当中存储的元素是可以重复的
注意：对于find来说multiset返回底层搜索树中序的第一个键值为key的元素的迭代器
- 示例：
void TestMSet() { int array[] = { 2, 1, 2, 1, 6, 0, 1, 6, 4, 7 }; // 允许键值冗余 multiset<int> s(array, array + sizeof(array) / sizeof(array[0])); for (auto& e : s) cout << e << " "; cout << endl; }
五、C++中的map
1、map的介绍
- 概念：
map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素
在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair:typedef pair value_type;
在内部map中的元素总是按照键值key进行比较排序以及查找
map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)
map支持下标访问符，即在[]中放入key，就可以找到与key对应的value（这里是在insert上的一个封装）
map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树)
注：set和map基本差不多，但是set是k模型，而map是kv模型，这导致在部分地方又有些不一样
2、map的使用
map的模板参数说明:
解释：
key: 键值对中key的类型
T： 键值对中value的类型
Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况
下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则
(一般情况下按照函数指针或者仿函数来传递)
Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器
注意：在使用map时，需要包含头文件map
map的构造：
- 示例：
void testmap1() { map<int, int> map1;//空构造 int num[] = { 1,5,9,4,8,2,3,1,5,4,5,7 }; for (auto e : num) { map1.insert(make_pair(e,e)); } map<int, int> map2(map1.begin(),map1.end());//迭代区间构造 map<int, int> map3(map2);//拷贝构造 for (auto& e : map3) { cout << e.first << ":" << e.second << endl; } }
- 示例：
void testmap2() { map<int, int> map1;//空构造 int num[] = { 1,5,9,4,8,2,3,1,5,4,5,7 }; for (auto e : num) { //map1.insert(pair<int,int>(e, e)); map1.insert(make_pair(e, e));//等同于 } //迭代器正向遍历 auto it1 = map1.begin(); while (it1 != map1.end()) { //cout << (*it1).first << ":"<<(*it1).second<<endl; cout << it1->first << ":"<<it1->second<<endl;//等同于 it1++; } //迭代器反向遍历 auto it2 = map1.rbegin(); while (it2 != map1.rend()) { cout << it2->first << ":" << it2->second << endl;//等同于 it2++; } }
- 解释：
在元素访问时，operator[]通过key找到与key对应的value然后返回其引用，当key不存在时，operator[]用默认value与key构造键值对然后插入，返回该默认value
- 示例：做统计
void testmap3() { int arr[] = { 1,4,8,5,9,6,4,2,9,6,4,1,8,5 }; map<int, int, greater<int>> countmap; for (auto e : arr) { countmap[e]++; //当不存在对应key则插入键值pair(e,int()),这里的int()即是0 返回0再++ //当存在对应key则返回对应的value，再++ } auto it1 = countmap.begin(); while (it1 != countmap.end()) { //cout << (*it1).first << ":"<<(*it1).second<<endl; cout << it1->first << ":" << it1->second << endl;//等同于 it1++; } }
- 示例：
void testmap4() { int num[] = { 1,8,4,5,3,9,2,6,7,4,5 }; map<int,int> map; for (int e : num)//插入 { auto ret = map.insert(make_pair(e,e)); if (ret.second == false) cout << e << "插入失败" << endl; } for (auto& e : map)//遍历 cout << e.first << ":" << e.second << endl; cout << "count 5:" << map.count(5) << endl; map.erase(map.find(8));//删除 for (auto& e : map)//遍历 cout << e.first << ":" << e.second << endl; }
六、C++中的multimap
multimap的介绍：
multimap容器与map容器的底层实现以及成员函数的接口都是基本一致，区别是multimap允许键值冗余，即multimap容器当中存储的元素是可以重复的
注意：
对于find来说multimap返回底层搜索树中序的第一个键值为key的元素的迭代器
由于multimap容器允许键值冗余，调用[ ]运算符重载函数时，应该返回键值为key的哪一个元素的value的引用存在歧义，因此在multimap容器当中没有实现[ ]运算符重载函数
示例：
void testMmap() { multimap<int, string> mm; //允许键值冗余 mm.insert(make_pair(2, "two")); mm.insert(make_pair(2, "double")); mm.insert(make_pair(2, "2")); mm.insert(make_pair(2, "second")); mm.insert(make_pair(1, "one")); mm.insert(make_pair(3, "three")); for (auto e : mm) { cout << e.first << ":" << e.second << endl; } cout << endl; //从第一个2找起，遍历到最后一个 auto pos = mm.find(2); while (pos != mm.end() && pos->first == 2) { cout << pos->first << ":" << pos->second << endl; pos++; } }
