【C++】map和set的使用

目录

1. 序列式容器和关联式容器

2. set系列的使用

2.1 set和multiset参考文档 - C++ Reference

2.2 set类的介绍

2.3 set的构造和迭代器

2.4 set的增删查

2.5 insert和迭代器遍历使用样例：

2.6 find和erase使用样例：

2.7 multiset和set的差异

2.8.lower_bound和upper_bound

练习：2.8 349. 两个数组的交集 - 力扣（LeetCode）

2.9 142. 环形链表 II - 力扣（LeetCode）

3. map系列的使用

3.1 map和multimap参考文档- C++ Reference

3.2 map类的介绍

3.3 pair类型介绍

3.4 map的构造

3.5 map的增删查

3.6 map的数据修改

3.6.1关于operator[]底层实现的特殊说明

3.6.2关于operator[]底层实现的具体说明

3.7 构造遍历及增删查使用样例

3.8 map的迭代器和[]功能样例：

3.9 multimap和map的差异

练习

3.10 138. 随机链表的复制 - 力扣（LeetCode）

3.11 692. 前K个高频单词 - 力扣（LeetCode）

解决思路1：

解决思路2：

1. 序列式容器和关联式容器

前面我们已经接触过STL中的部分容器如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间一般没有紧密的关联关系，比如交换一下两个数据，它依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。

关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是非线性结构，两个位置有紧密的关联关系，交换一下两个数据，它数据间的逻辑关系被破坏了，存储结构就被破坏了。关联式容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。

本文章讲解的map和set底层是红黑树，红黑树是一颗平衡二叉搜索树（红黑树后文详细说明）。set是之前二叉树文章中讲过的key搜索场景的结构，map是key/value搜索场景的结构。

2. set系列的使用

2.1 set和multiset参考文档

- C++ Reference"> - C++ Reference

2.2 set类的介绍

• set的声明如下，T就是set底层关键字的类型（其实这里当年命名时，key-value的概念并不明晰，所以命名为T）

• set默认要求T支持小于比较,数据小的放在二叉搜索树的左边，大的数据放在二叉搜索树的右边，如果不支持或者想按自己的需求走可以自行实现仿函数传给第二个模版参数。

• set底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第三个参数。

• 一般情况下，我们都不需要传后两个模版参数。

• set底层是用红黑树实现，增删查效率是O(logN)，迭代器遍历是走的搜索树的中序，因为所以是有序的，并且因为set支持的是小于比较，所以中序遍历的结果是递增的。

• 前面部分我们已经学习了vector/list等容器的使用，STL容器接口设计，高度相似，所以这里我们就不再一个接口一个接口的介绍，而是挑比较重要的接口进行介绍。

template  class set;

2.3 set的构造和迭代器

set的构造我们关注以下几个接口即可。

set的支持正向和反向迭代遍历，因为底层是二叉搜索树，迭代器遍历走的中序，所以遍历默认按升序顺序。

支持迭代器就意味着支持范围for，但是set的iterator和const_iterator都不支持通过迭代器修改数据，因为修改关键字数据，就会破坏底层搜索树的结构。

// empty (1) 无参默认构造
explicit set(const key_compare& comp = key_compare(),
	const allocator_type& alloc = allocator_type());
// range (2) 迭代器区间构造
template 
set(InputIterator first, InputIterator last,
	const key_compare& comp = key_compare(),
	const allocator_type & = allocator_type());
// copy (3) 拷贝构造
set(const set& x);
// initializer list (5) initializer 列表构造
set(initializer_list il,
	const key_compare& comp = key_compare(),
	const allocator_type& alloc = allocator_type());
// 迭代器是一个双向迭代器
iterator->a bidirectional iterator to const value_type
// 正向迭代器
iterator begin();
iterator end();
// 反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();

2.4 set的增删查

set的增删查关注以下几个接口即可：

Member types
key_type->The first template parameter(T)
value_type->The first template parameter(T)
// 单个数据插入，如果已经存在则插入失败
pair insert(const value_type& val);
// 列表插入，已经在容器中存在的值不会插入
void insert(initializer_list il);
// 迭代器区间插入，已经在容器中存在的值不会插入
template 
void insert(InputIterator first, InputIterator last);
// 查找val，返回val所在的迭代器，没有找到返回end()
iterator find(const value_type& val);
// 查找val，返回Val的个数
size_type count(const value_type& val) const;
// 删除一个迭代器位置的值
iterator erase(const_iterator position);
// 删除val，val不存在返回0，存在返回1
size_type erase(const value_type& val);
// 删除一段迭代器区间的值
iterator erase(const_iterator first, const_iterator last);
// 返回大于等val位置的迭代器
iterator lower_bound(const value_type& val) const;
// 返回大于val位置的迭代器
iterator upper_bound(const value_type& val) const;

2.5 insert和迭代器遍历使用样例：

首先对于set来说，实际上分为multiset与set两种，set不允许key值重复，multiset允许，所以set插入时，如果插入的值，容器内已经有了，那么就不会再插入，也就是说set中的每一个值都是独一无二的。

所以当我们向set中插入一串数据时，重复的数不再插入，就可以起到去重的效果，并且根据底层二叉搜索树的特性加上迭代器中序遍历的设计，最后set容器就起到去重加排序的效果。

#include
#include
using namespace std;
int main()
{
	// 去重+升序排序
	set s;
	// 去重+降序排序（给一个大于的仿函数）
	//set s;
	s.insert(5);
	s.insert(2);
	s.insert(7);
	s.insert(5);
	//set::iterator it = s.begin();
	auto it = s.begin();
	while (it != s.end())
	{
		// error C3892: “it”: 不能给常量赋值
// *it = 1;
		cout " second  y.second;
		}
	};
	vector topKFrequent(vector& words, int k) {
		map countMap;
		for (auto& e : words)
		{
			countMap[e]++;
		}
		vector v(countMap.begin(), countMap.end());
		// 仿函数控制降序
		stable_sort(v.begin(), v.end(), Compare());
		//sort(v.begin(), v.end(), Compare());
		// 取前k个
		vector strV;
		for (int i = 0; i  
解决思路2：
 
将map统计出的次数的数据放到vector中排序，或者放到priority_queue中来选出前k个。利用仿函数强行控制次数相等的，字典序小的在前面。
 
class Solution {
public:
	struct Compare
	{
		bool operator()(const pair& x, const pair& y)
			const
		{
			return x.second > y.second || (x.second == y.second && x.first  
class Solution {
public:
	struct Compare
	{
		bool operator()(const pair& x, const pair& y)
			const
		{
			// 要注意优先级队列底层是反的，大堆要实现小于比较，所以这里次数相等，想要字典
			序小的在前面要比较字典序大的为真
				return x.second 
					y.first);
		}
	};
	vector topKFrequent(vector& words, int k) {
		map countMap;
		for (auto& e : words)
		{
			countMap[e]++;
		}
		// 将map中的放到priority_queue中，仿函数控制大堆，次数相同按照字典
		序规则排序
			priority_queue
			p(countMap.begin(), countMap.end());
		vector strV;
		for (int i = 0; i