【C++】map和set的使用

map和set的使用

✨前言：我们经常需要高效地存储和查找数据。vector、list等序列式容器虽然好用，但在需要快速查找和自动排序的场景下就显得力不从心了。 这时，map和set这两个关联式容器就派上了用场。它们基于红黑树实现，提供了O(logN)时间复杂度的查找、插入和删除操作，并且能够自动维护数据的有序性。 本文将带你深入了解map和set的使用方法、特性差异以及实际应用场景，帮助你在合适的场景选择合适的数据结构。 📖专栏：【C++成长之旅】

一、序列式容器和关联式容器

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

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

我们下面主要是对map/set进行介绍，map和set底层是红黑树，红黑树是一颗平衡二叉搜索树。set是key搜索场景的结构，map是key/value搜索场景的结构。红黑树我后续会进行说明，关于key/value的说明我上篇文章中已经说明：【二叉搜索树】

2. set系列的使用

2.1 set和multiset参考文档

老样子，先贴参考文档【set和multiset参考文档】，我们的学习也是参考其中的。

2.2 set类的介绍

set 的声明形式：

在这里插入图片描述

• T 是底层关键字的类型。
• 默认情况下，set 要求类型 T 支持小于比较（< 运算符）。
• 若类型 T 不支持小于比较，或需自定义比较规则，可通过实现仿函数并传递给第二个模板参数来实现。
• set 底层存储数据的内存由空间配置器分配，若需自定义内存管理（如实现内存池），可传递给第三个模板参数。
• 通常，我们无需传递后两个模板参数，使用默认配置即可。
• set 底层采用红黑树（一种平衡二叉搜索树）实现。
• 其增、删、查操作的时间复杂度均为 (O(log N))，效率较高。
• 迭代器遍历时，遵循搜索树的中序遍历顺序，因此遍历结果是有序的。
• 在学习了 vector、list 等容器的使用后，我们会发现 STL 容器的接口设计高度相似。
• 因此，我们不再逐一介绍每个接口，而是通过查阅文档，重点介绍其中较为重要的接口。

2.3 set的构造和迭代器

构造很简单：

在这里插入图片描述

迭代器说明：

在这里插入图片描述

set的迭代器类型为双向迭代器，即仅仅支持++ 、--；

迭代器遍历默认按升序顺序，因为底层是二叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围for，set的iterator和const_iterator都不支持迭代器修改数据，修改关键字数据，破坏了底层搜索树的结构。

2.4 set的增删查

注意，没有改，修改key值，会破坏了底层搜索树的结构。

在介绍其它函数之前，我们先来看一下pair.

pair 介绍

pair<iterator,bool>

pair 是pair 一个模板类，用于将两个值组合成一个单一对象。基本定义：

template <class T1, class T2>
struct pair 
{
    T1 first;
    T2 second;
    
    // 构造函数和其他成员函数...
};

初始化：

在这里插入图片描述

pair 是在我们set和map中还是很常用的：

组合两个相关值； 函数返回多个值； 存储键值对；像后面要说的map底层红黑树节点中的数据，就是用pair<Key,T>存储键值对数据。 在map和set的使用以及后续map和set的模拟实现都会见到的。

set的增删查开始介绍： set 的成员函数还是只介绍常用的，其它的感兴趣参考前面的网站！！！

在这里插入图片描述

在这里插入图片描述

关于insert的说明：

1. 存在的值都不会进行插入；
2. 返回值为pair<iterator,bool>的解释如下：

• first - iterator 指向插入的元素：如果插入成功，指向新插入的元素 指向已存在的元素：如果元素已存在，指向集合中已有的那个元素
• second - bool true：插入成功（元素原本不在集合中） false：插入失败（元素已存在于集合中）

再来看一下以前没有见过的几个：

在这里插入图片描述

我们可以来使用一下：

#include<iostream>
#include<set>
using namespace std;

int main()
{
	std::set<int> myset;
	for (int i = 1; i < 10; i++)
		myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90
	for (auto e : myset)
	{
		cout << e << " ";
	}
	cout << endl;
	// 实现查找到的[itlow, itup)包含[30, 60]区间
	
	// 返回>= 30
	auto itlow = myset.lower_bound(30);
	// 返回> 60
	auto itup = myset.upper_bound(60);
	// 删除这段区间的值
	myset.erase(itlow, itup);
	for (auto e : myset)
	{
		cout << e << " ";
	}
	cout << endl;
	return 0;
}

输出：

在这里插入图片描述

我们再来简单看一下set其它函数：

在这里插入图片描述

在这里插入图片描述

当然，有时也可以利用count间接实现快速查找。

在这里插入图片描述

当然，我们还有些接口未说，有兴趣可自行查看，文档在上面。

2.5 multiset和set的差异

multiset和set的使用基本完全类似，主要区别点在于multiset支持值冗余，那么insert/find/count/erase都围绕着支持值冗余有所差异，具体参看下面的样例代码理解。

#include<iostream>
#include<set>
using namespace std;
int main()
{
	// 相比set不同的是，multiset是排序，但是不去重
	multiset<int> s = { 4,2,7,2,4,4,8,4,5,4,9 };
	auto it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl << "################" << endl;
	// 相比set不同的是，x可能会存在多个，find查找中序的第一个
	int x = 4;
	auto pos = s.find(x);
	while (pos != s.end() && *pos == x)
	{
		cout << *pos << " ";
		++pos;
	}
	cout << endl << "################" << endl;

	// 相比set不同的是，count会返回x的实际个数
	cout << s.count(x) << endl;
	cout << "################" << endl;
	// 相比set不同的是，erase给值时会删除所有的x
	s.erase(x);
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl << "################" << endl;

输出：

在这里插入图片描述

3. map系列的使用

3.1 map和multimap参考文献

同上，参考文档：【map和multimap参考文档】

3.2 map类的介绍

在这里插入图片描述

map的声明如下，与set类似，只是多了一直val类型。Key就是map底层关键字的类型，T是map底层value的类型，map默认要求Key支持小于比较，如果不支持或者需要的话可以自行实现仿函数传给第二个模版参数，map底层存储数据的内存是从空间配置器申请的。一般情况下，我们都不需要传后两个模版参数。map底层是用红黑树实现，增删查改效率是O(logN)，迭代器遍历是走的中序，所以是按key有序顺序遍历的。（同set） 注意，map支持修改value数据，不支持修改key数据

3.3 map的构造

在这里插入图片描述

3.4 map的增删查

map增接口，插入的pair键值对数据，跟set所有不同，但是查和删的接口只用关键字key跟set是完全类似的，不过find返回iterator，不仅仅可以确认key在不在，还找到key映射的value，同时通过迭代还可以修改value。 基本与set都相同，我们只强调一个点，对插入、删除、查找都是根据key值进行操作的。

3.5 map的数据修改

前面提到map支持修改value数据，不支持修改key数据，修改关键字数据，破坏了底层搜索树的结构。 map第一个支持修改的方式是通过迭代器，迭代器遍历时或者find返回key所在的iterator进行value修改，map还有一个非常重要的修改接口operator[]，但是operator[]不仅仅支持修改，还支持插入数据和查找数据，所以他是一个多功能复合接口。 需要注意从内部实现角度，map这里把我们传统说的value值，给的是T类型，typedef为mapped_type。而value_type是红黑树结点中存储的pair键值对值。日常使用我们还是习惯将这里的T映射值叫做value。

我们这里对operator[]再来进行说明，后续会在模拟实现的时候在进行论述，其实operator[]在底层封装了insert，主要就是为什么insert上文返回值会设计为pair<iterator,bool>了。所以，对于operator[]我们要分为两层来看：

1. 如果k不在map中，insert会插入key和val默认值，同时[]返回结点中存储val值的引用，那么我们可以通过引用改返映射值。所以[]具备了插入+修改功能
2. 如果key在map中，insert会插入失败，但是insert返回pair对象的first是指向key结点的迭代器，[]返回值同时返回结点中存储val值的引用，所以[]具备了查找+修改的功能。

3.6使用样例

#include<iostream>
#include<map>
using namespace std;
int main()
{
	// initializer_list构造及迭代遍历
	map<string, string> dict = { {"left", "左边"}, {"right", "右边"},
		{"insert", "插入"},{ "string", "字符串" } };

	//map<string, string>::iterator it = dict.begin();
	auto it = dict.begin();
	while (it != dict.end())
	{
		cout << (*it).first <<":"<<(*it).second << endl;
		// map的迭代基本都使用operator->,这里省略了一个->
		// 第一个->是迭代器运算符重载，返回pair*，第二个箭头是结构指针解引用取pair数据
		cout << it.operator->()->first << ":" << it.operator->()->second << endl;
		cout << it->first << ":" << it->second << endl;
		++it;
	}
	cout << endl;
	return 0;
}

3.7 multimap和map的差异

multimap和map的使用基本完全类似，主要区别点在于multimap支持关键值key冗余，那么insert/find/count/erase都围绕着支持关键值key冗余有所差异，这里跟set和multiset完全一样，比如find时，有多个key，返回中序第一个。其次就是multimap不支持[]，因为支持key冗余，[]就只能支持插入了，不能支持修改。