我们已经接触过 STL 中的部分容器，比如：vector、list、deque、forward_list 等，这些容器统称为 序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。至于 stack 和 queue，他们其实不能算是容器，而应该是容器适配器，是用 deque 封装的。
那什么是关联式容器？它与序列式容器有什么区别？
关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是 <key, value> 结构的键值对，在数据检索时比序列式容器效率更高。如 map、set、unordered_map、unordered_set 等等都是关联式容器。
Ⅱ. 树形结构的关联式容器
根据应用场景的不同，STL 总共实现了两种不同结构的管理式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种： map 、 set 、 multimap 、 multiset。这四种容器的共同点是：使用红黑树作为其底层结果，容器中的元素是一个有序的序列。下面一依次介绍每一个容器。
Ⅲ. 键值对的概念
用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量 key 和 value ， key 代表键值，value 表示与 key 对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义。
**SGI-STL**中关于 键值对 pair 的定义：
template <class T1, class T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(): first(T1()), second(T2())
{}
pair(const T1& a, const T2& b): first(a), second(b)
{}
}; 🐛 为什么要有键值对呢？
💡 解答： 因为考虑到如果后面 map<string, int> 中存的是两个变量，如果我们在迭代器遍历的时候想要打印它们的值也就是这里的 string 和 int，这个时候我们直接 cout << *it; 是没办法打印出来两个变量的，因为函数的返回值只能有一个，所以我们就得有键值对 pair 这个类单独出来解决这个问题，统一将一个类型变量命名为 first，第二个命名为 second，每次去取的时候需要我们用 it.first、it.second 去取才能达到效果！
这里我们还需要介绍的一个函数就是 make_pair<T1, T2>()：
其实 make_pair 就是为了方便我们去构造 map 等容器，因为我们平时在用 pair 时候需要指定类型，但是如果用 make_pair 的话就是就是让编译器用模板帮我们推类型，减少代码量，比如：
int main()
{
map<int, double> m;
// 调用pair的构造函数，构造一个匿名对象插入
m.insert(pair<int, double>(1, 1.1));
m.insert(pair<int, double>(5, 5.5));
m.insert(pair<int, double>(2, 2.2));
for (const auto& e : m)
cout << e.first << "/" << e.second << endl;
cout << endl;
// 调用函数模板，构造对象
m.insert(make_pair(3, 3.3));
for (const auto& e : m)
cout << e.first << "/" << e.second << endl;
return 0;
}
// 🚩 运行结果：
1/1.1
2/2.2
5/5.5
1/1.1
2/2.2
3/3.3
5/5.5🔺 注意： pair 是类，而 make_pair 是函数
Ⅳ. set
一、set的介绍
-
set是按照一定次序存储元素的容器 -
在
set中，元素的value也标识它，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。 -
在内部，
set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。 -
set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。 -
set在底层是用红黑树实现的。
注意事项
set中插入元素时，只需要插入value即可，不需要构造键值对。set中不允许键值重复 (因此可以使用set进行去重)。set中的元素默认按照小于来比较。set中查找某个元素，时间复杂度为：- 使用
set的迭代器遍历set中的元素，可以得到有序序列。 set中的元素不允许修改，为什么？-
因为
set的底层的迭代器是const_iterator。如果set中允许修改键值的话，那么首先需要删除该键，然后调节平衡，在插入修改后的键值，再调节平衡，如此一来，严重破坏了set的结构，导致iterator失效，不知道应该指向之前的位置，还是指向改变后的位置。所以STL中将set的迭代器设置成const，不允许修改迭代器的值。 -
因为
set存放的value实际上就是key的值，key的值是我们用来排序的，所以不允许修改。
-
二、set的使用
① 模板参数列表
-
T：set中存放元素的类型，实际在底层存储<value, value>的键值对 -
Compare：set中元素默认按照小于来比较 -
Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理
② 构造函数
| 函数声明 | 功能 |
|---|---|
| set (const Compare& comp = Compare(), const Allocator& = Allocator() ); | 构造空的 set |
| set (InputIterator first, InputIterator last, const Compare& comp = Compare(), const Allocator& = Allocator() ); | 用 [first, last) 区间中的元素构造 set |
| set ( const set<Key,Compare,Allocator>& x); | set 的拷贝构造 |
#include <iostream>
#include <set>
using namespace std;
bool fncomp(int left, int right) { return left < right; }
struct classcomp
{
bool operator() (const int& left, const int& right) const
{
return left < right;
}
};
int main()
{
set<int> first; // 存放int类型的空set
int myints[] = { 10,20,30,40,50 };
set<int> second(myints, myints + 5); // 迭代器构造区间set
set<int> third(second); // 拷贝构造set
set<int> fourth(second.begin(), second.end()); // 迭代器构造set.
set<int, classcomp> fifth; // 类作为比较器
bool(*fn_pt)(int, int) = fncomp;
set<int, bool(*)(int, int)> sixth(fn_pt); // 函数指针作为比较
return 0;
}③ 迭代器
| 函数声明 | 功能 |
|---|---|
| iterator begin() | 返回 set 中起始位置元素的迭代器 |
| iterator end() | 返回 set 中最后一个元素后面的迭代器 |
| reverse_iterator rbegin() | 返回 set 第一个元素的反向迭代器，即 end |
| reverse_iterator rend() | 返回 set 最后一个元素下一个位置的反向迭代器，即rbegin |
🍰 每个迭代器都还有 const 版本的，但是这里就不列举出来了，因为 set 其实底层用的就是 const_iterator，是无法修改的，但是我们平时一般都用 begin() 而不需要使用 cbegin() 。
int main()
{
// 用数组array中的元素构造set
int array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };
set<int> s(array, array + sizeof(array) / sizeof(array[0]));
// 1、第一种遍历方法：迭代器
set<int>::iterator it = s.begin();
while (it != s.end())
{
//*it = 1; ❌这是不能被修改的，因为set的迭代器底层是用const_iterator
cout << *it << " ";
it++;
}
cout << endl;
// 反向迭代器
set<int>::reverse_iterator rit = s.rbegin();
while (rit != s.rend())
{
cout << *rit << " ";
rit++;
}
cout << endl;
// 2、第二种遍历方式：范围for
for (const auto& e : s)
{
cout << e << " ";
}
cout << endl;
return 0;
}
// 🚩 运行结果：
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9④ 容量操作
| 函数声明 | 功能介绍 |
|---|---|
| bool empty() const | 检测 set 是否为空，空返回 true ，否则返回 true |
| size_type size() const | 返回 set 中有效元素的个数 |
| size_type count ( const key_type& x ) const | 返回 set 中值为 x 的元素的个数 |
💅 值得注意的是：set 不允许键值冗余，但是 multiset 允许重复的键值，所以 multiset 中重复的键值也是算入有效个数的！
⑤ 修改操作
| 函数声明 | 功能介绍 |
|---|---|
| pair<iterator,bool> insert ( const value_type& x ) | 在 set 中插入元素 x ，实际插入的是 <x, x> 构成的键值对， 如果插入成功，返回 < 该元素在 set 中的位置， true>, 如果 插入失败，说明 x 在 set 中已经存在，返回 <x 在 set 中的位 置， false> |
| void erase ( iterator position ) | 删除 set 中 position 位置上的元素 |
| size_type erase ( const key_type& x ) | 删除 set 中值为 x 的元素，返回删除的元素的个数 |
| void erase ( iterator first, iterator last ) | 删除 set 中 [first, last) 区间中的元素 |
| void swap ( set<Key,Compare,Allocator>& st ); | 交换 set 中的元素 |
| void clear ( ) | 将 set 中的元素清空 |
| iterator find ( const key_type& x ) const | 返回 set 中值为 x 的元素的位置，若没找到则返回 end() |
template<class T>
void Print(const set<T>& s)
{
for (const auto& e : s)
cout << e << " ";
cout << endl;
}
int main()
{
set<int> m;
m.insert(1);
m.insert(3);
m.insert(1); //重复的话set是不会插入的
m.insert(4);
m.insert(5);
m.insert(7);
m.insert(6);
Print(m);
//通过erase直接删
m.erase(1);
m.erase(3);
Print(m);
//通过find查找后删掉该迭代器位置的元素
set<int>::iterator pos = m.find(5);
m.erase(pos);
Print(m);
//删光set中的元素
m.clear();
Print(m);
return 0;
}
// 🚩 运行结果：
1 3 4 5 6 7
4 5 6 7
4 6 7📲 注意事项： 用 erase 的时候，如果要删的元素在 set 中的话，那么传迭代器和传值的效果是一样的，但是如果元素是不存在的话，那结果是不一样的！
- 若用的是 find + 迭代器 的话，那么会先查找元素，没找到的话也会去删，这样子就导致了报错，因为如果找不到的话
find会返回set的结尾即set.end()，导致最后的误删报错。 - 若用的是 直接传要删的元素进行删除 的话，那么该元素在
set中就删，不在的话则不会去删。
所以我们需要对第一种情况进行处理一下：
int main()
{
set<int> m;
m.insert(1);
m.insert(3);
m.insert(1); //重复的话set是不会插入的
m.insert(7);
m.insert(6);
Print(m);
//判断一下是否返回的是end()
auto position = m.find(199);
if (position != m.end())
{
m.erase(position);
}
Print(m);
//不存在的话就不会去删
m.erase(200);
Print(m);
return 0;
}
// 🚩 运行结果：
1 3 6 7
1 3 6 7
1 3 6 7Ⅴ. multiset
一、multiset 的介绍
-
multiset是按照特定顺序存储元素的容器，其中元素是可以重复的。 -
在
multiset中，multiset元素的值不能在容器中进行修改（因为元素总是const的），但可以从容器中插入或删除。 -
在内部，
multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。 -
multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢，但当使用迭代器遍历时会得到一个有序序列。 -
multiset底层结构为红黑树。
注意事项
-
multiset中再底层中存储的是<value, value>的键值对，与set是一样。 -
mtltiset的插入接口中只需要插入即可 -
与
set的唯一区别是，multiset中的元素可以重复，set中value是唯一的 -
使用迭代器对
multiset中的元素进行遍历，可以得到有序的序列 -
multiset中的元素不能修改，原因与set类似，可以参考set -
在
multiset中找某个元素，时间复杂度为 -
multiset的作用：可以对元素进行排序 -
multiset使用erase删除的是重复元素的话，会一并将所有的重复元素删除。 -
使用时与
set包含的头文件相同的：<set>
二、multiset 的使用
与 set 不同的就是 multiset 可以有重复元素，且 multiset 用 erase 后是删除全部的重复元素，所以这里只演示这个区别，其他的接口与 set 都是类似的，具体的查看文档或者参考 set 的用法。
int main()
{
int arr[] = { 1,3,1,4,5,1,5,6,8,7 };// 含有重复元素
int n = sizeof(arr) / sizeof(arr[0]);
// set会去重
set<int> s(arr, arr + n);
Print(s);
s.erase(1);
Print(s);
cout << endl;
// multiset重复的元素也会算入，一起删除
multiset<int> multis(arr, arr + n);
Print(multis);
// 会删除1的所有元素
multis.erase(1);
Print(s);
return 0;
}
// 🚩 运行结果：
1 3 4 5 6 7 8
3 4 5 6 7 8
1 1 1 3 4 5 5 6 7 8
3 4 5 6 7 8❓ 思考： 为什么 multiset 就能实现重复的元素？
💡 解析： 因为 STL 中对 multiset 和 multimap 都做了规定，规定他们如果出现了重复的元素，那么在这个已经存在的元素的节点的右子树插入这个重复的节点，让已经存在的那个节点元素保持在前面的位置，也在一定程度上维护了排序的稳定性！假设这里我们用 find 去查找 multiset 中的一个重复的元素，那么其找到的结果就是第一个遇到的中序的节点，如下图所示：
Ⅵ. map
一、map 的介绍
-
map是关联容器，它按照特定的次序按照key来比较，存储由键值key和值value而成的元素。 -
在
map中，键值key通常用于排序和唯一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为typedef pair<const Key, T> value_type; // 从这里也可看出key是常量不能修改的 -
在内部，
map中的元素总是按照键值key进行比较排序的。 -
map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代（即对map中的元素进行迭代时，可以得到一个有序的序列) -
map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。 -
map是红黑树实现的。
二、map 的使用
① 模板参数说明
key：键值对中key的类型
T： 键值对中value的类型
Compare：比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)
Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器
🐛 注意：在使用 map 时，需要包含头文件 <map>。
② 构造函数
| 函数声明 | 功能介绍 |
|---|---|
| map() | 构造一个空的 map |
| map (InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()) | 迭代器构造区间map |
| map (const map& x) | 拷贝构造map |
bool fncomp(char left, char right) { return left < right; }
struct classcomp
{
bool operator() (const char& left, const char& right) const
{
return left < right;
}
};
int main()
{
map<char, int> first; // 构造空的map
// 插入元素，使用[]即可
first['a'] = 10;
first['b'] = 30;
first['c'] = 50;
first['d'] = 70;
map<char, int> second(first.begin(), first.end()); // 迭代器构造map
map<char, int> third(second); // 拷贝构造map
map<char, int, classcomp> fourth; // 用类方法做比较
bool(*fn_pt)(char, char) = fncomp;
map<char, int, bool(*)(char, char)> fifth(fn_pt); // 用函数指针做比较
return 0;
}③ 迭代器
| 函数声明 | 功能介绍 |
|---|---|
| begin() 和 end() | begin: 首元素的位置， end 最后一个元素的下一个位置 |
| cbegin() 和 cend() | 与 begin 和 end 意义相同，但 cbegin 和 cend 所指向的元素不能修改 |
| rbegin() 和 rend() | 反向迭代器， rbegin 在 end 位置， rend 在 begin 位置，其 ++ 和 -- 操作与 begin 和 end 操作移动相反 |
| crbegin() 和 crend() | 与 rbegin 和 rend 位置相同，操作相同，但 crbegin 和 crend 所指向的元素不能修改 |
int main()
{
map<string, string> m;
m.insert(make_pair("liren", "利刃"));
m.insert(make_pair("apple", "苹果"));
m.insert(make_pair("banana", "香蕉"));
m.insert(make_pair("milk", "牛奶"));
// 遍历方式1：迭代器
map<string, string>::iterator it = m.begin();
while (it != m.end())
{
cout << it->first << " -> " << it->second << endl;
it++;
}
cout << endl;
// 反向迭代器
map<string, string>::reverse_iterator rit = m.rbegin();
while (rit != m.rend())
{
cout << rit->first << " -> " << rit->second << endl;
rit++;
}
cout << endl;
// 遍历方式2：范围for
// 注意这里的s其实就是pair的对象，所以我们得用s.first来访问而不是s->first
for (const auto& s : m)
{
cout << s.first << " -> " << s.second << endl;
}
cout << endl;
return 0;
}
// 🚩 运行结果：
apple -> 苹果
banana -> 香蕉
liren -> 利刃
milk -> 牛奶
milk -> 牛奶
liren -> 利刃
banana -> 香蕉
apple -> 苹果
apple -> 苹果
banana -> 香蕉
liren -> 利刃
milk -> 牛奶④ 容量与元素访问操作
| 函数声明 | 功能简介 |
|---|---|
| bool empty ( ) const | 检测 map 中的元素是否为空，是返回 true ，否则返回 false |
| size_type size() const | 返回 map 中有效元素的个数 |
| mapped_type& operator[] (const key_type& k) | 返回 key 对应的 value |
问题：当 key 不在 map 中时，通过 operator[] 获取对应 value 时会发生什么问题❓❓❓
这是值得我们深入了解的！
首先我们来看一下 operator[] 的文档:
我们从上面的函数内容可以看出原来 operator[] 是调用了 insert 函数实现的，那我们先来研究一下 insert 函数的特点！
可以看到 insert 的单元素版本返回的是 pair，所以我们就可以对 operator[] 的内容来剖析一下：
- 如果
key不在map中，先插入pair<key, value()>，然后再返回节点中value对象的引用 - 如果
key在map中，则返回key所在节点中value对象的引用
☔ 总结： 我们可以直接用 operator[] 对 map 的 value 进行访问以及修改，很方便，所以可以认为 insert 就是为了 operator[] 而生的！
🔺 **注意：**在元素访问时，有一个与 operator[] 类似的操作 at() (该函数不常用)函数，都是通过 key 找到与 key 对应的value 然后返回其引用，不同的是：当 key 不存在时， operator[] 用默认 value 与 key 构造键值对，然后插入，返回该默认 value ， at() 函数直接抛异常。
这里的例子与下面⑤的函数一起讲！
⑤ 元素修改
| 函数声明 | 功能简介 |
|---|---|
| pair<iterator,bool> insert ( const value_type& x ) | 在 map 中插入键值对 x ，注意 x 是一个键值对，返回值的也是键值对： iterator 代表新插入元素的位置， bool 代表释放插入成功 |
| void erase ( iterator position ) | 删除 position 位置上的元素 |
| size_type erase ( const key_type& x ) | 删除键值为 x 的元素 |
| void erase ( iterator first, iterator last ) | 删除 [first, last) 区间中的元素 |
| void swap ( map<Key,T,Compare,Allocator>& map ) | 交换两个 map 中的元素 |
| void clear ( ) | 将 map 中的元素清空 |
| iterator find ( const key_type& x ) | 在 map 中插入 key 为 x 的元素，找到返回该元素的位置的迭代器，否则返回 end |
| const_iterator find ( const key_type& x ) const | 在 map 中插入 key 为 x 的元素，找到返回该元素的位置的 const 迭代器，否则返回 cend |
| size_type count ( const key_type& x ) const | 返回 key 为 x 的键值在 map 中的个数，注意 map 中 key 是唯一的，因此该函数的返回值要么为 0 ，要么为 1 ，因此也可以用该函数来检测一个 key 是否在 map 中 |
insert 操作细节看 ④ 中的介绍，这里就不多说了！
测试代码：
int main()
{
map<string, string> m;
// 向map中插入元素的方式：
// 将键值对<"peach","桃子">插入map中，用pair直接来构造键值对
m.insert(pair<string, string>("peach", "桃子"));
// 将键值对<"peach","桃子">插入map中，用make_pair函数来构造键值对
m.insert(make_pair("banan", "香蕉"));
// 借用operator[]向map中插入元素
/*
operator[]的原理是：
用<key, T()>构造一个键值对，然后调用insert()函数将该键值对插入到map中
如果key已经存在，插入失败，insert函数返回该key所在位置的迭代器以及false
如果key不存在，插入成功，insert函数返回新插入元素所在位置的迭代器以及true
operator[]函数最后将insert返回值键值对中的value返回
*/
// 将<"apple", "">插入map中，插入成功，返回value的引用，将“苹果”赋值给该引用结果，
m["apple"] = "苹果"; // 插入+修改
m["water"]; // 插入
m["water"] = "水"; // 修改
m["liren"] = "利刃"; // 插入+修改
// key不存在时抛异常
//m.at("waterme") = "水蜜桃";
cout << m.size() << endl;
cout << m.count("peach") << endl;
// 用迭代器去遍历map中的元素，可以得到一个按照key排序的序列
for (auto& e : m)
cout << e.first << "--->" << e.second << endl;
cout << endl;
// map中的键值对key一定是唯一的，如果key存在将插入失败
// insert返回的是pair，所以这里auto的类型是 pair<map<string, string>::iterator, bool>
auto ret = m.insert(make_pair("peach", "桃色"));
if (ret.second)
cout << "<peach, 桃色>不在map中, 已经插入" << endl;
else
cout << "键值为peach的元素已经存在：" << ret.first->first << "--->" << ret.first->second << " 插入失败" << endl;
// 删除key为"apple"的元素
m.erase("apple");
if (1 == m.count("apple"))
cout << "apple还在" << endl;
else
cout << "apple被吃了" << endl;
return 0;
}
// 🚩 运行结果：
5
1
apple--->苹果
banan--->香蕉
liren--->利刃
peach--->桃子
water--->水
键值为peach的元素已经存在：peach--->桃子 插入失败
apple被吃了三、map 的应用实例
这里我们举个应用例子：统计出现的物品次数，并找出大家最喜欢（出现次数最多）的三种水果
这里有多种实现的方法，并且我们把统计和找出次数最多的步骤分开，我们一一列举出来：
对于统计次数
void Count1()
{
// 统计次数方式1：使用find+insert的方法
string arr[] = { "香蕉", "苹果", "山竹", "山竹", "葡萄", "葡萄", "山竹", "榴莲", "山竹", "葡萄", "香蕉" };
map<string, int> countMap;
// 因为string是自定义类型，若传值给e的话会多次调用拷贝构造，所以这里用传引用
for (const auto& e : arr)
{
map<string, int>::iterator it = countMap.find(e);
// 不为end()说明存在该节点，则让次数++
// 为end()说明不存在节点，则插入
if (it != countMap.end())
{
it->second++;
}
else
{
countMap.insert(make_pair(e, 1));
}
}
// 打印
for (const auto& e : countMap)
cout << e.first << ":" << e.second << endl;
}
void Count2()
{
//统计次数方式2：直接用insert
string arr[] = { "香蕉", "苹果", "山竹", "山竹", "葡萄", "葡萄", "山竹", "榴莲", "山竹", "葡萄", "香蕉" };
map<string, int> countMap;
for (const auto& e : arr)
{
// 因为insert返回的是pair，所以得用pair的对象接收
pair<map<string, int>::iterator, bool> res = countMap.insert(make_pair(e, 1));
// 通过返回的pair对象的second的bool值来判断是否插入成功
// 若成功则说明原来不存在该节点，则不需要做任何事
// 若失败则说明之前已经存在该节点了，则需要让次数++
if (res.second == false)
{
res.first->second++;
}
}
// 打印
for (const auto& e : countMap)
cout << e.first << ":" << e.second << endl;
}
void Count3()
{
// 统计次数方式3：直接用operator[]
string arr[] = { "香蕉", "苹果", "山竹", "山竹", "葡萄", "葡萄", "山竹", "榴莲", "山竹", "葡萄", "香蕉" };
map<string, int> countMap;
for (const auto& e : arr)
{
// 如果e不在countMap中，则先插入，再返回节点中value对象的引用
// 如果e在countMap中，则直接返回key所在节点中对应value对象的引用
countMap[e]++;
}
// 打印
for (const auto& e : countMap)
cout << e.first << ":" << e.second << endl;
}
int main()
{
Count3();
return 0;
}
// 🚩 运行结果：（三个都是一样的）
榴莲:1
苹果:1
葡萄:3
山竹:4
香蕉:2 可以看出第二种比第一种的效率要高，因为第一种既调用了 find 又 insert 了一遍，相当于遍历了两遍。
而这里的第三种方式是最简洁也是最常用的！直接用 operator[] 实现统计，而底层其实调用 insert，这个具体看上面 map 使用里面的解析。
对于出现次数最多的物品计算
这里对于统计次数，我们利用上面的方法三。
这里一共有四种方法，每种方法都不太一样也各有特点，也有很多细节要处理。
① 利用vector存放迭代器进行排序
- 为什么
vector要存迭代器而不是直接存pair呢？- 解答： 因为很明显发现，存
pair，也就是vector<pair<string, int>>的话，我们每次向vector里面插入数据都会去调用拷贝构造函数，而每pair<string, int>的大小可能很大；如果是存迭代器的话，也就是vector<map<string, int>::iterator>，它每次向vector里面插入数据，大小永远都是4/8个字节，这样子的话非常省空间，且多次的string的拷贝构造涉及深拷贝也会让效率变低。存迭代器就完美的避开了这个问题！
- 解答： 因为很明显发现，存
- 那为什么不存指针而是存迭代器呢？
- 解答： 因为为了保持平台可移植性，不同的平台的平衡树指针是不一样的名称的，但是可以确定的是迭代器一定是一样的！
- 在向
vector插入迭代器的时候为什么不使用vector的迭代器区间构造，即 (countMap.begin(),countMap.end()) 呢？- 解答： 这里要搞清楚的是，
vector的迭代器区间构造，它的底层其实是push_back(*iterator)，它存放的是迭代器区间的数据，而不是迭代器本身，所以我们不能直接用迭代器区间构造，需要我们自己完成迭代器的插入！
- 解答： 这里要搞清楚的是，
struct CountItCompareBig
{
// 注意这里最后要加const，否则有些地方调用的时候会报错
bool operator()(map<string, int>::iterator x, map<string, int>::iterator y) const
{
return x->second > y->second;
}
};
// 对所有物品次数排序的思路一: 对countMap的迭代器进行排序（需要自己写比较函数）
void Sort1()
{
// 统计次数方式3：直接用operator[]
string arr[] = { "香蕉", "苹果", "山竹", "山竹", "葡萄", "葡萄", "山竹", "榴莲", "山竹", "葡萄", "香蕉" };
map<string, int> countMap;
for (const auto& e : arr)
countMap[e]++;
// 对所有物品次数排序的思路一:
vector<map<string, int>::iterator> v;
// 先将迭代器插入到vector中（注意这里不能用vector的区间初始化，因为如果是区间初始化，那么放进去的是pair而不是迭代器）
map<string, int>::iterator Mapit = countMap.begin();
while (Mapit != countMap.end())
{
v.push_back(Mapit);
Mapit++;
}
// 接着对vector中的迭代器进行排序
sort(v.begin(), v.end(), CountItCompareBig());
// 打印前三名最多次数的
for (int i = 0; i < 3; ++i)
cout << "第" << i+1 << "名：" << v[i]->first << endl;
}② 利用map进行排序
- 为什么这里的 “草莓” 没有插入进
sortMap中？- 解答： 这是
map的特点，不允许键值冗余，也就是不允许key冗余，我们用sortMap来存countMap中的数据的时候，这里其实就是将他们两个的键值对交换了，让键值变成出现的次数，让值变成字符串。而当我们插入数据到sortMap中的时候，看的就是他们出现的次数，当出现第二个在countMap中次数是相同的时候，那么sortMap不会将其插入，因为sortMap是以次数为键值的，不允许键值冗余，所以其实这里用map来排序是不合适的，我们得用multimap，但是我们这里还没讲multimap，所以将就的用一下map，但要清楚这里用multimap更合适！
- 解答： 这是
- 这种方法是否比第一种方法优呢？
- 解答： 答案为否！因为这里我们用另一个
map来存排序的数据，其实中间插入数据的时候，都是拷贝构造，而对于string这类自定义类型涉及深拷贝，那么空间和时间消耗是比较大的；但是第一种方法中存的是迭代器，很好的避开了这种问题，所以综上所述，第一种方法会比第二种方法更好一点！
- 解答： 答案为否！因为这里我们用另一个
// 对所有物品次数排序的思路二: 利用map排序，用map<int, string>类型来反向存储，这样子就可以比较key值也就是次数
void Sort2()
{
// 统计次数方式3：直接用operator[]
string arr[] = { "香蕉", "草莓", "山竹", "山竹", "葡萄", "葡萄", "山竹", "榴莲", "山竹", "葡萄", "香蕉" };
map<string, int> countMap;
for (const auto& e : arr)
countMap[e]++;
// 对所有物品次数排序的思路二：
//multimap<int, string, greater<int>> sortMap 这里用multimap更合适
map<int, string, greater<int>> sortMap;
for (const auto& e : countMap)
{
sortMap.insert(make_pair(e.second, e.first));
}
// 打印前三名最多次数的
int i = 1;
for (const auto& e : sortMap)
{
if (i > 3)
break;
cout << "第" << i++ << "名：" << e.second << endl;
}
}③ 利用set进行排序
- 这种方法其实和方法一是大同小异的，这里也是用
set来存储map的迭代器，而不是存pair，避开了深拷贝的一些问题，所以这种方法和第一种是差不多的。 - 与方法一不同的是，这里利用
set插入的时候，会根据比较器去直接进行排序，省去了排序的步骤，会比方法一简洁，但是原理上来说都是差不多的。
struct CountItCompareBig
{
// 注意这里最后要加const，否则有些地方调用的时候会报错
bool operator()(map<string, int>::iterator x, map<string, int>::iterator y) const
{
return x->second > y->second;
}
};
// 对所有物品次数排序的思路三: 利用set存储pair的迭代器排序，类似第一种方式，这样子也能避免拷贝pair
void Sort3()
{
// 统计次数方式3：直接用operator[]
string arr[] = { "香蕉", "苹果", "山竹", "山竹", "葡萄", "葡萄", "山竹", "榴莲", "山竹", "葡萄", "香蕉" };
map<string, int> countMap;
for (const auto& e : arr)
countMap[e]++;
// 对所有物品次数排序的思路三:
set<map<string, int>::iterator, CountItCompareBig> sortSet;
map<string, int>::iterator countMapIt = countMap.begin();
while (countMapIt != countMap.end())
{
sortSet.insert(countMapIt);
countMapIt++;
}
// 打印前三名最多次数的
int i = 1;
for (const auto& e : sortSet)
{
if (i > 3)
break;
cout << "第" << i++ << "名：" << e->first << endl;
}
}④ 利用优先级队列进行排序
- 与上面三种方法不太一样的是，这里的比较器要用
less的，因为我们要建一个大堆，所以我们得传less的比较器给优先级队列，而前面三种都是传greater版本。 - 需要注意的是优先级队列里面并不是有序的，但是能确定的是堆顶是最大的那个，所以我们要求前几名的话就是取
top()，然后顺便pop()，这样子每次堆顶都是最大的那个，达到了我们的目的。
struct CountItCompareLess
{
bool operator()(map<string, int>::iterator x, map<string, int>::iterator y) const
{
return x->second < y->second;
}
};
// 对所有物品次数排序的思路四：利用优先级队列存放迭代器进行排序，注意用的是小堆根
void Sort4()
{
// 统计次数方式3：直接用operator[]
string arr[] = { "香蕉", "苹果", "山竹", "山竹", "葡萄", "葡萄", "山竹", "榴莲", "山竹", "葡萄", "香蕉" };
map<string, int> countMap;
for (const auto& e : arr)
countMap[e]++;
// 对所有物品次数排序的思路四：利用优先级队列存放迭代器进行排序，注意用的是小堆根
// 注意如果要传比较器的话，那么也得将vector也传过去，由于太长，所以我们用typedef简化
typedef map<string, int>::iterator M_IT;
priority_queue<M_IT, vector<M_IT>, CountItCompareLess> pq; //求最大的几个数所以要弄小堆
map<string, int>::iterator countMapIt = countMap.begin();
while (countMapIt != countMap.end())
{
pq.push(countMapIt);
countMapIt++;
}
// 打印前三名最多次数的
for (int i = 1; i <= 3; ++i)
{
cout << "第" << i << "名：" << pq.top()->first << endl;
pq.pop();
}
cout << endl;
}Ⅶ. multimap
一、 multimap 的介绍
-
Multimaps是关联式容器，它按照特定的顺序，存储由key和value映射成的键值对<key, value>，其中多个键值对之间的key是可以重复的。 -
在
multimap中，通常按照key排序和唯一地标识元素，而映射的value存储与key关联的内容。key和value的类型可能不同，通过multimap内部的成员类型value_type组合在一起，value_type是组合key和value的键值对：typedef pair<const Key, T> value_type; -
在内部，
multimap中的元素总是通过其内部比较对象，按照指定的特定严格弱排序标准对key进行排序的。 -
multimap通过key访问单个元素的速度通常比unordered_multimap容器慢，但是使用迭代器直接遍历multimap中的元素可以得到关于key有序的序列。 -
multimap在底层用红黑树实现。
🏖 注意： multimap 和 map 唯一的区别就是：map 中的 key 是唯一的，而 multimap 中 key 是可以重复的。
二、 multimap 的使用
multimap 与 map 的区别就是 key，所以其他的接口都是一致的，具体参考 map，以及参考 set 和 multiset 的区别，他们两两之间都是类似的。
🏖 注意：
multimap中的key是可以重复的。multimap中的元素默认将key按照小于来比较- 使用时与
map包含的头文件相同： multimap中没有重载operator[]操作，为什么？- 解答： 因为
multimap中允许重复的键值，如果修改的话，要修改多份，降低查找效率，和修改效率。STL是追求效率的
- 解答： 因为