【C++进阶】2024年了set、map还搞不懂底层细节？

一、前情提要

在学习set和map之前，我们首先来了解一下 关联式容器 和 键值对 这两个概念。

1、什么是关联式容器？

前面我们学习过的vector、List、deque、forward_list等都是序列式容器，底层为线性序列的数据结构，里面存储的是元素本身。 关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器里面存的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高。

基于红黑树的关联容器：

• set：存储唯一键的集合
• multiset：存储可以有重复键的集合
• map：存储唯一键及其关联值的映射
• multimap：存储可以有重复键及其关联值的映射
• 特点：内部以红黑树实现，元素默认按键的升序排列，支持快速查找、插入和删除操作

2、键值对又是什么？

键值对是一种将两个相关的值组合在一起的数据结构，具有一一对应的关系，该结构一般只包含两个成员变量key和Value，key代表键值，Value代表与key对应的信息。

特点：

• 唯一性：在大多数情况下，键（Key）是唯一的，这意味着一个键只能映射到一个值（Value）。然而，在某些特殊情况下（如multimap或unordered_multimap），一个键可以映射到多个值
• 无序性：键值对的存储顺序通常不是由键或值的顺序决定的，除非使用了某种特定的排序算法或数据结构（如基于红黑树的map或set）。然而，有些容器（如unordered_map或unordered_set）确实提供了基于哈希表的快速查找，但它们的元素是无序的
• 灵活性：键值对可以存储几乎任何类型的数据，只要键和值的数据类型在容器声明时指定或兼容

SGI-STL中键值对的定义：

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)
{}
};

通过上面简单的介绍了解一下关联式容器和键值对，我们再学习set和map会相对清晰一些。

二、树形结构的关联式容器

根据应用场景的不同，STL总共实现了两种不同结构的管理式容器：树形结构和哈希结构。本篇文章我们学习树形结构。

树形结构关联式容器主要包括map、set、multimap和multiset。这些容器通过键值对（key-value）的形式存储数据，并且基于树型结构（平衡搜索树，即红黑树）来实现，确保了容器中的元素是有序的。

1、set

1.1 set 介绍

• set 文档介绍。
• 使用set需要包头文件<set>

| set的底层使用二叉搜索树（红黑树）实现的，所以set具有以下的性质：

• 元素唯一： set中的每个元素都是唯一的，不允许有重复的元素。如果尝试插入一个已存在的元素，该插入操作将被忽略，即set的大小不会增加
• 快速查找： 由于 set 内部使用平衡二叉树（如红黑树）实现，因此它查找的速度很快，时间复杂度为O(LogN)
• 元素不可修改： set中的元素不能在容器中修改(元素总是const)（因为这可能会破坏容器的排序顺序），但是可以从容器中插入或删除
• 有序： 使用set的迭代器中序遍历set中的元素，可以得到有序序列（结合元素唯一和有序，set可以做到去重+排序）

| 另外还有一些细节值得注意：

• set中插入元素时，只需要插入value即可，不需要构造键值对
• 与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放value，但在底层实际存放的是由<value, value>构成的键值对

1.2 set 模版参数列表

• T： set中存放元素的类型，实际在底层存的是<value, value>的键值对
• Compare： set中元素默认按小于比较，如果想要按大于比较可以传相应的仿函数
• Alloc： set中元素空间的管理方式，使用STL提供的空间配置器管理

1.3 set 的相关操作

set的构造、迭代器、容量等函数比较简单，使用起来不是很复杂，童鞋们参考上面提供的文档介绍自己看一下哈，这里就不浪费篇幅了哈，我们介绍一下set的插入、删除、查找等操作。

void test1()
{
	构造空的set
	//set<int> s;
	//s.insert(1);
	//s.insert(3);
	//s.insert(1);
	//s.insert(6);
	//s.insert(2);
	//s.insert(3);
	//s.insert(5);
	//s.insert(8);

	int arr[] = { 3,4,9,6,5,7,1,5,6,4,6,4,2,4,6,8,5,4,1,5,6,6,3,2 };
	//迭代器区间构造
	set<int> s(arr, arr + sizeof(arr) / sizeof(int));

	//迭代器遍历
	//去重+排序
	auto it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	//删除最小的元素
	s.erase(s.begin());

	//范围for遍历
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
}

2、multiset

2.1 multiset 介绍

• multiset 文档介绍
• 使用multiset也需要包含头文件<set>

multiset与set的操作、使用大致相同，所以这里也就不再赘述了（又能偷懒了），只是在某些方面有一些区别：

• multiset也是按照特定顺序存储元素的容器，不过其元素是可以重复的
• multiset的插入接口只需要插入即可，因为理论上multiset的插入操作一定会成功
• multiset不会对数据去重，所以可以真正意义上的排序

另外multiset和set也存在接口上的一些区别。

2.2 count 接口

• count的作用是： 给一个值，返回这个值在当前容器中的个数。

set中也有count接口，不过set中的count接口用处不是很明显，可以用来判断某一个值在当前set中存不存在：

v

相比而言multiset中的count才能发挥它真正的作用：

在这里插入图片描述

2.3 find 接口

与set中的find接口类似，multiset中的find接口作用也是在容器中搜索等效于val 的元素，如果找到，则返回指向val的迭代器，否则返回multiset::end。

不过multiset中可能存在多个给定的val，而这时的find返回的是中序遍历的第一个val的迭代器，这么做的目的是能把所有的val都找出来。

找出multiset中所有的val：

int main()
{
	int arr[] = { 3,4,9,6,5,7,1,5,6,4,6,4,2,4,6,8,5,4,1,5,6,6,3,2 };
	multiset<int> mts(arr, arr + sizeof(arr) / sizeof(int));
	int x = 0;
	cin >> x;
	int y = mts.count(x);
	while (y--)
	{
		cout << *(mts.find(x)) << " ";
	}
	return 0;
}

在这里插入图片描述

2.4 erase 接口

支持通过迭代器、元素值、迭代器区间来删除元素。

multiset的erase接口和set的erase虽然看起来好像一样，但实际上有不小的差别。

来看下面三种删除操作：

void test2()
{
	//传迭代器删除
	cout << "传迭代器删除" << endl;
	int arr1[] = { 3,4,9,6,5,7,1,5,6,4,6,4,2,4,6,8,5,4,1,5,6,6,3,2 };
	multiset<int> mts1(arr1, arr1 + sizeof(arr1) / sizeof(int));
	for (auto e : mts1)
	{
		cout << e << " ";
	}
	cout << endl;

	mts1.erase(mts1.find(6));
	multiset<int>::iterator it = mts1.begin();
	while (it != mts1.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	//传值删除
	cout << "传值删除" << endl;
	int arr2[] = { 3,4,9,6,5,7,1,5,6,4,6,4,2,4,6,8,5,4,1,5,6,6,3,2 };
	multiset<int> mts2(arr2, arr2 + sizeof(arr2) / sizeof(int));
	for (auto e : mts2)
	{
		cout << e << " ";
	}
	cout << endl;

	mts2.erase(6);
	for (auto e : mts2)
	{
		cout << e << " ";
	}
	cout << endl;

	//传迭代器区间删除
	cout << "传迭代器区间删除" << endl;
	int arr3[] = { 3,4,9,6,5,7,1,5,6,4,6,4,2,4,6,8,5,4,1,5,6,6,3,2 };
	multiset<int> mts3(arr3, arr3 + sizeof(arr3) / sizeof(int));
	for (auto e : mts3)
	{
		cout << e << " ";
	}
	cout << endl;

	mts3.erase(mts3.equal_range(6).first, mts3.equal_range(6).second);
	for (auto e : mts3)
	{
		cout << e << " ";
	}
	cout << endl;
}

通过结果我们不难得出：如果multiset中存在多个val，则传迭代器只会删除一个，传值和传迭代器区间会将multiset中所有的val删除。

这点是我们在平时使用时容易忽略的。

3、map

3.1 map介绍

• map 文档介绍
• 使用map需要包头文件<map>

| map的底层也是二叉平衡树（红黑树）实现的，所以其也具有以下性质：

• 有序： map是关联容器，它按照特定的次序存储由键值key和值value组合而成的元素，map中的元素只按照键值key进行比较排序
• 唯一： 每个键在map中都是唯一的（值可以不唯一），不允许有重复键。如果尝试插入一个已存在的键，则不会插入该元素，并返回此现有元素的迭代器
• 时间复杂度： map的查找、插入和删除操作的时间复杂度通常是O(logN)

其实map和set还是非常相似的，甚至函数接口等，这里就不再过多列举了，可以对比set学习。 下面我们着重介绍map的键值对存储和[]重载。

3.2 map的元素存储

在map中，键值key通常用于排序和唯一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair：

• typedef pair<const key, T> value_type;

文章开头我们简单地了解了下键值对，可以看出pair 是一个模板结构体，它包含两个值，分别称为 first 和 second，分别对应于键（Key）和值（Value）在 map 中的位置。

当你向 map 插入一个元素时，你实际上是在插入一个 std::pair<Key, Value> 对象。同样地，当你从 map 中检索元素时，你得到的是一个 std::pair<const Key, Value> 的引用（或迭代器指向的对象），其中 Key 是 const 的，因为 map 的键在插入后不应该被修改。

3.3 map的几种初始化方式

• 创建有名对象
• 使用匿名对象
• 使用make_pair构建一个匿名对象
• 隐式类型转换

int main()
{
	map<string, string> m;

	//创建有名对象
	pair<string, string> p("front", "前");
	m.insert(p);

	//使用匿名对象
	m.insert(pair<string, string>("behind", "后"));
	
	//使用make_pair构建一个匿名对象
	m.insert(make_pair("left", "左"));
	
	//隐式类型转换
	m.insert({ "right", "右" });

	for (const auto& e : m)
	{
		cout << e.first << "->" << e.second << endl;
	}
	cout << endl;

	return 0;
}

从运行结果可以看出，我们插入的键值对是按照 “键”（英文单词）排序过的。

| 对其中make_pair和隐式类型转换做如下解释：

• make_pair是 C++ 标准库中的一个非常有用的函数模板，它定义在头文件<utility> 中，make_pair 的主要作用是创建一个 std::pair类型的对象

template <class T1,class T2>
pair<T1,T2> make_pair (T1 x, T2 y)
{
    return ( pair<T1,T2>(x,y) );
}

• 使用make_pair的好处是可以自动推导类型，不需要我们指定了
• 单参数的构造函数支持隐式类型转换，多参数也支持，只需要用{}括起来就可

除了以上的四种初始化方法，还有一种更为方便的方法。

| initializer_list：

C++11支持了使用initializer_list初始化列表来直接初始化map对象：

其中value_type是pair<const key_type, mapped_type>的别名。

initializer_list是C++11标准中引入的一种新类型，它提供了一种统一且方便的方式来初始化对象，特别是用于构造函数和函数参数中，以允许传递一个初始化元素列表。

• 它表示一个特定类型的值的数组，是一种轻量级的包装器，用于在编译时捕获花括号初始化的列表]
• 提供了一种灵活且统一的方式来初始化对象和处理多个同类型值的列表

int main()
{
	map<string, string> m = { {"front", "前"},{"behind", "后"}, 
	{"left", "左"},{"right", "右"} };

	//范围for遍历
	for (const auto& e : m)
	{
		cout << e.first << "->" << e.second << endl;
	}
	cout << endl;

	//迭代器遍历
	map<string, string>::iterator it = m.begin();
	while (it != m.end())
	{
		cout << it->first << "->" << it->second << endl;
		++it;
	}

	return 0;
}

花括号外层是initializer_list，内层是隐式类型转换。

3.4 使用map计数

• 假设我们需要统计字符出现的次数。

计数的规则是：key存储对应的字符，value为字符出现的次数。在map中找给定的字符，如果没找到就插入这个字符和出现的次数1；如果在map中找到了这个字符，我们就++对应的value。

这里简单介绍一下map中的find函数接口：find函数用于查找具有指定键的元素。如果找到了该元素，find函数会返回一个指向该元素的迭代器；如果没有找到，返回迭代器map::end()。

void test1()
{
	char arr[] = { 'a','d','h','a','b','a','h','a','b','d','a',
	'h','d','b','d' };
	map<char, int> m;
	for (auto ch : arr)
	{
		map<char, int>::iterator it = m.find(ch);
		//没找到就插入
		if (it == m.end())
		{
			m.insert({ ch, 1 });
		}
		//找到就++对应的value
		else
		{
			++it->second;
		}
	}
	for (auto e : m)
	{
		cout << e.first << "->" << e.second << endl;
	}
}

除了上面的计数方法，还有一种更为简单的方法也可以实现计数：

void test2()
{
	char arr[] = { 'a','d','h','a','b','a','h','a','b','d','a',
	'h','d','b','d' };
	map<char, int> m;
	for (auto ch : arr)
	{
		m[ch]++;
	}
	for (auto e : m)
	{
		cout << e.first << "->" << e.second << endl;
	}
}

上面的计数实现依赖于map中重载了运算符[]。我们看到上面的实现过程似乎很简洁，那这个运算符重载究竟是怎么只用了一行简短的代码就实现了计数的呢？答案就在下面，我们接着往下看。

3.5 [ ]运算符重载

下面是运算符[]重载的函数原型：

• mapped_type —> value
• key_type —> key

简单来说[]的使用规则是传入key，返回对应value的引用。那要是传入的key在当前的map中没有呢？

如果map中没有key，则会插入一个由key和value（默认值）组成的键值对，最后返回刚插入的value的引用。

对[]的调用等价于：

（*（（this->insert（make_pair（k，mapped_type（））））.first））.second

是不是有点意外，[]的重载竟然不是复用find函数，而是复用insert函数。 []重载实现的关键是利用了insert函数的返回值（前面想着map的函数接口和set差不多，打算偷懒不重复介绍了，看来前面欠的这里终归要还呜呜…），来看：

insert的返回值是一个迭代器，如果插入成功（map中原本没有key），则返回一个由指向新插入元素的迭代器和bool值（插入成功为true，失败为false） 组成的键值对；如果插入失败（map中原本有key），则返回一个由map中已存在元素的迭代器和bool值 组成的键值对。

然后.first访问到的是新插入的、或原本元素的迭代器，再解引用.second访问到的就是我们想要的key对应的value了。

这里的逻辑有点绕，我大概画一下其中的指向关系：

在这里插入图片描述

简单总结就是：key存在，返回对应的value；key不存在，插入key和value（默认）。 看到这里相信我们就理解了上面调用[]重载计数的原理。

void test3()
{
	map<string, string> m;

	//插入
	m.insert(make_pair("front", "前"));

	//插入 <"behind", "">
	m["behind"];

	//插入+修改
	m["left"] = "左";

	//查找
	cout << m["right"] << endl;
}

虽然[]这样重载确实在某些场景方便了我们，但也存在不好的一面。比如我们原本想查找，但如果map中没有这个元素，那就会把这个元素插入进入。所以[]固然好用，但要谨慎使用哦！

4、multimap

4.1 multimap 介绍

• multimap文档介绍
• multimap也声明在头文件<map>中

其实multimap也没什么可介绍的了，无非就是相比较与map，multimap允许键值冗余，再结合multiset，multimap无非也就那点东西喽。（被我逮到偷懒的时机了吧） 不过值得一说的是multimap没有再重载[]，因为multmap的特点重载[]会使得其行为变得不明确。 还有就是从下面的实验可以得出multimap和multiset的erase函数接口特点是一样的。

void test4()
{
	multimap<string, string> mtm;
	mtm.insert({ "front", "前" });
	mtm.insert({ "behind", "后"});
	mtm.insert({ "left", "左" });
	mtm.insert({ "front", "前" });
	mtm.insert({ "behind", "后" });
	mtm.insert({ "front", "前" });
	mtm.insert({ "right", "右" });
	mtm.insert({ "left", "左" });
	mtm.insert({ "behind", "后" });
	mtm.insert({ "front", "前" });
	mtm.insert({ "left", "左" });

	for (const auto& e : mtm)
	{
		cout << e.first << "->" << e.second << endl;
	}
	cout << endl;

	auto it = mtm.find("front");
	//传迭代器删除
	mtm.erase(it);
	for (const auto& e : mtm)
	{
		cout << e.first << "->" << e.second << endl;
	}
	cout << endl;

	//传值删除
	mtm.erase("behind");
	for (const auto& e : mtm)
	{
		cout << e.first << "->" << e.second << endl;
	}
	cout << endl;

	//传迭代器区间删除
	mtm.erase(mtm.equal_range("left").first, mtm.equal_range("left").second);
	for (const auto& e : mtm)
	{
		cout << e.first << "->" << e.second << endl;
	}
	cout << endl;
}

如果multimap中存在多个key，则传迭代器只会删除一个，传值和传迭代器区间会将multimap中所有的key删除。

本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~