【C++】详解 set && multiset && map && multiset 的使用

利刃大大

发布于 2025-02-16 20:08:20

5500

代码可运行

文章被收录于专栏：csdn文章搬运csdn文章搬运

运行总次数：0

代码可运行

Ⅰ. 关联式容器

我们已经接触过 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 对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义。

pair的文档介绍

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 是按照一定次序存储元素的容器
在 set 中，元素的 value 也标识它，并且每个 value 必须是唯一的。set 中的元素不能在容器中修改(元素总是 const)，但是可以从容器中插入或删除它们。
在内部，set 中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
set 容器通过 key 访问单个元素的速度通常比 unordered_set 容器慢，但它们允许根据顺序对子集进行直接迭代。
set 在底层是用红黑树实现的。

注意事项

set 中插入元素时，只需要插入 value 即可，不需要构造键值对。
set 中 不允许键值重复 (因此可以使用 set 进行去重)。
set 中的元素默认按照小于来比较。
set 中查找某个元素，时间复杂度为：

log_2 n

使用 set 的迭代器遍历 set 中的元素，可以得到 有序序列。
set 中的元素不允许修改，为什么？
1. 因为 set 的底层的迭代器是 const_iterator。如果 set 中允许修改键值的话，那么首先需要删除该键，然后调节平衡，在插入修改后的键值，再调节平衡，如此一来，严重破坏了 set 的结构，导致 iterator 失效，不知道应该指向之前的位置，还是指向改变后的位置。所以 STL 中将 set 的迭代器设置成 const，不允许修改迭代器的值。
2. 因为 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 中，multiset 元素的值不能在容器中进行修改（因为元素总是 const 的），但可以从容器中插入或删除。
在内部，multiset 中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。
multiset 容器通过 key 访问单个元素的速度通常比 unordered_multiset 容器慢，但当 使用迭代器遍历时会得到一个有序序列。
multiset底层结构为红黑树。

注意事项

multiset 中再底层中存储的是 <value, value> 的键值对，与 set 是一样。
mtltiset 的插入接口中只需要插入即可
与 set 的唯一区别是，multiset 中的元素可以重复，set 中 value 是唯一的
使用迭代器对 multiset 中的元素进行遍历，可以得到有序的序列
multiset 中的元素不能修改，原因与 set 类似，可以参考 set
在 multiset 中找某个元素，时间复杂度为

log_2 n

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的文档简介

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 的介绍

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 是追求效率的