C++——map和set

作者：几冬雪来

时间：2023年11月17日

内容：C++板块map和set知识讲解

目录

前言： 

map与set与关联式容器：

set底层：

set的书写：

insert：

erase：

lower_bound与upper_bound:

equal_ range:

multiset（Multiple-key set）：

equal_ range:

count：

find：

map底层：

map的书写：

value_type：

insert： 

pair与流插入问题：

operator[]: 

代码：

结尾： 

---

前言： 

在上一篇博客中我们学习了C++中的搜索二叉树，在那个时候我们就有说过搜索二叉树是C++学习的一个重要知识点，后面的C,V问题都有应用。而且今天我们将来讲解C++另一个重要的知识map与set。 

map与set与关联式容器：

在今天我们要学习的map与set，在C++中被称为关联式容器。

而在STL初期学习的vector，list等被称为序列式容器（线性表），它们的底层为线性序列的数据结构。

对比序列式容器，关联式容器同样的也是用来存储数据的，但是与序列式容器不同的是，关联式容器中存储的是结果的键值对，在数据检索时候比序列式容器效率更高。

在序列式容器中，vector与list如果想要插入数据的话，这里我们可以在任何地方插入。但是关联式容器不一样，在关联式容器中里面的数据有关联性和规则，我们不能随便插入。

但是因为有规则和关系，所以查找等功能对比序列性容器要更好。

set底层：

接下来我们就先来讲解C++中的set关联容器。

在这里我们看set的使用可以看见，在参数部分中多了一个Compare。

这个地方的底层为红黑树，也就是搜索树。因此这个地方的Compare是一个仿函数，用来支持key进行比较大小。

set的书写：

在稍微了解了set与map和关联式容器之后，接下来我们就先来看看set的代码书写是怎么样的？

首先正式写set的代码之前，编译器需要我们引入一个头文件。

如上图就是书写set前引入的头文件，与此同时我们也可以看出来如果要书写map关联式容器的话也要引入它的头文件。

同时要注意一个点，那就是set对比起vector和list等，set仅仅只有插入操作，而不是再分为头插，尾插和中间插入等。

insert：

首先在这里进行insert操作。

从上图可以看出来，insert将数据插入后，在用迭代器将其输出。输出的结果是一个有序的结果，从输出的值顺序来看，我们可以断定iterator中set的insert默认为中序遍历。

而且set的insert还有其他的隐藏操作。

这里set的insert的另一个操作就是去重，例如图中我们insert了几个值为3，但是这个地方输出的结果依旧不变，这就是它的另一个作用——去重。

但是它的核心内容还是去重。

erase：

接下来就是它的erase操作了。

这里我们也是借由上面的代码来辅助实现。

从上图可以看出，在进行输入操作之后我们依旧是借由迭代器，在这里建立一个pos用来存储find的值。

接下来就将pos给erase掉，这样就能做到删除set里面的值了。同样的如果erase里面传的是一个固定的值我们也可以将其删除。

lower_bound与upper_bound:

接下来讲解的是C++中的一个新的操作lower_bound与upper_bound，这两个操作可以分开使用也可以将其合并使用。

而且它们的共同作用就是确定范围。

就如上图一样，在第一个for循环语句当中，我们输入了10~90的数据。

而后用itlow和itup定位到了30和60的位置，接下来再用一个循环打印数据的话。这里可以看见30~60之间的数据全都被我们删除掉了。

同样的如果lower_bound里面的值是25的话，这里的结果并不会改变，我们可以理解为它找的值为>=25的值。 

equal_ range:

再在接下来我们来讲解一下equal_ range，其实这个接口在set处就已经存在了，但是这个接口并不能在set里面发挥自己真正的作用。

前面我们讲解了lower_bound与upper_bound，它们都是截取一段区间，而这里的equal_ range表示的意思的——等于一段区间。

在这里我们equal_ range里面的值为30。

那么在返回的时候数据就会返回一个作闭右开的区间，也就是30~40左闭右开。

multiset（Multiple-key set）：

在接下来我们来讲解一下multiset（Multiple-key set），这里的意思表明它是一个可以建值冗余的set。

这里multiset（Multiple-key set）的原型和set是一样的，它们的接口也是一样的，因此使用multiset不用再包含新的头文件。

但是接口一样并不等于其接口的作用也是一样的。

从结果上来看，我们就可以看出二者同样的接口不同的效果了。

在上面的set上说过，set的insert不仅会做到排序的效果，而且还有去重的效果。而insert在multiset中仅仅只有排序的效果，并没有去重的效果。

equal_ range:

接下来我们就来说一下multiset与equal_ range的配合。

在上边的set之中equal_ range并没有上面实质性的作用，但是在multiset中这个接口会发挥很大的作用。

类似上边，我们插入了许多的数据，在这些数据中不乏有重复的值。而现在我们利用equal_range去查找想要删除的值。

因为数据已经被排序完毕了，equal_range查找的值就是这组数据中所有的值。

又因为其左闭右开的缘故，这里查找的就是全部为6的值的区间，然后对其进行删除操作，输出的结果就会将所有6删除，而在下一个大于6值处停下。

count：

然后接下来也是一个在set中没有上面作用而且在multiset有重要作用的一个接口。

它的使用也是非常的简单。

在这里count的作用就是计算出它后面参数中数据存在的个数，例如我们要计算3的个数，区间里面有两个3因此怎么输出值就为2。

find：

再然后就是find操作，这里multiset和set并没有什么操作上的区别。

这里是要了解一个知识点。

那就是multiset支持建值冗余，find查找的值为其中序查找排列后第一个出现的值。

map底层：

在讲解完了set与multiset以及它们的大部分接口之后，接下来就要来了解一下map的底层实现是什么样的。 

map底层和set不一样的地方是，set在这个地方只传了一个class T，而且map这里传有两个值，一个是class T，另一个是class Key。

而这两个值也就代表着C++中的key和value。

下面的compare则是仿函数的比较器，它比较的是key。 

map的书写：

上边就是set的一些操作和代码的书写，在关联式容器中set占据一席之地。

但是接下来要讲解的——map，才是重中之重。

value_type：

在正式讲解map的操作之前，这个地方我们要了解到一个操作那就是value_type。 

从图中来看，value_type的底层实现就是让这里的key不允许被修改。

那么这里就回到set，set是不能被修改的但是map的value是允许被修改的，set是怎么做到不允许被修改的呢？

set这里实现是将iterator迭代器和const iterator迭代器都定性为const iterator迭代器。 

而map对比set是允许被修改的，但是它的修改又有限度。 

这里的pair就是类模板，在它的里面有两个核心成员——first和second。也就是说在map里面一般的存储数据都是用pair来进行存储的。

而pair里面两个核心成员first和second一般代表的就是key和value。

insert： 

然后再下来就需要我们配合pair去书写map的insert接口。

这里我们就直接看代码。

在这里map对比set要传两个值，接下来就是调用pair去构造一个对象。这个地方不需要我们将pair的key转换为const类型，这里编译器会转换。

这里的insert并不是插入k和value两个值，这个地方插入的是一个结构对象。

同样的这里的insert有第二种写法，我们可以将pair和insert写成一段代码。

但是这样书写的话可读性对比前一段代码的可读性要降低一点。

当然在此处还有第三种写法，这里要运用到新的知识。

第三种写法则是借助make_pair完成了实现，而make_pair是一个函数模板，也就是我们传两个值给make_pair，在make_pair里面自动构造一个pair进行返回。

  

这里书写的方法也是十分的简单，make_pair里面写入要插入的结构对象即可，连类型都不用去书写。

同时这里set的插入还有一种十分特殊的写法。

这里这样子也可以实现我们上边的一系列的操作，这是因为在C++98中编译器规定只有单参数的构造函数才能支持隐式类型的转换。

但是在C++11中支持多参数的构造函数的隐式类型转换。

这种写法等价于上边第二种写法。但是这种写法会被C++的版本所限制，前三种写法C++11和C++98都能使用，而这种写法在C++98中并不能实现。

pair与流插入问题：

接下来我们想要输出数据的时候就会有问题出现。

从图中可以看出来，这里我们定义一个it来存储dict开始的地址，接下来就是判断输出数据。

但是，如果在这里依旧是以以前*it的方式来输出的话，这个地方程序就会报错，这就说明pair这个类库里面是并没有实现流插入的。

这是因为在这里需要重载一个operator*，而迭代器里面包含一个节点的指针。如果是迭代器里面的值是一个key和一个value的话，这样子就不能做到很好的返回。并且C++中不支持返回两个或者多个值，因此我们要将这两个值放在一个结果里面，所以这个地方需要我们返回一个结构。

综上所述，这个地方直接返回*it的行为是不对的，因为这个地方返回的是结构，operator*的返回值是pair的引用，如果是指针的话这里的operator*就是返回pair的指针。

那么这段代码的正确的写法如下：

这个地方不仅仅可以使用while语句去完成，这个地方还能去使用for语句进行完成。

并且在上边有说过，在pair中我们的key被规定为const类型，是不能被修改的，那么这个地方就借用一下代码看看它的写的。

从图中我们就可以看出来，因为pair中的first对应着key与value中的key，而key的类型为const不能被修改。

但是这个地方的second对应的是value，而value并不是const类型，因此second就可以被我们进行修改。

而且在插入中还有一个需要我们知道的知识点，在pair中如果key和value都相同的话，这里是不会进行插入的。但是如果key相同而value不同的话，这个地方依旧是不插入，不覆盖，因为在插入的过程中编译器只比较key，如果已经存在key并且两个key都相同那就不插入了。

operator[]: 

在map里面有许多的接口和set是一样的，类似lower_bound与upper_bound是查找区间，count是统计次数等等。

但是在map中也有许多不同的接口，接下来讲解的operator[]就是map中一个重要的接口。而这个地方讲解operator[]的话就需要借助统计次数的问题。

这里我们就使用map来书写统计水果出现次数的代码，这个地方用map来写这个问题就不需要再像搜索二叉树一样先建一棵树出来了。

map里面的key给类型string用来判断水果类型，value用来计算出现的次数。

然后通过if语句判断该水果是否是第一次出现，如果是的话就输入这个水果的名称，并且value改写为1。

如果有新水果出现，那就再走if语句，如果没有那么做说明该水果不是第一次出现，这里就只需要将second（value）进行++即可。 

同样的这个地方查找水果出现次数的代码也可以改为这种形式。

其道理也是一样的。 

这里就是operator[]的底层，在看operator之前先来看一下右边的这张表。在pair中我们的第一个first传的是key_type，而在second处传的是mapped_type。

再结合左边的代码，平时在设计[]的操作或者代码中是直接返回下标第X个位置的数据的引用，但是在map中这个操作有些不同，这个地方给的值不是下标而是key。 

借助key返回对应value的引用，具有查找和修改的功能。

 

这里就要联系到我们统计水果出现次数的第二种写法。 

通过代码这个地方我们可以推测出这个for循环语句的作用是计算水果出现的次数，如果出现两次这里的结果就为2。

但是这段代码就会延伸出一个问题，这个水果第一次出现的情况是怎么解决的。

这里就要讲到它的底层实现，就如上图一样，这一大串的代码就是operator[]的实现。

这里可以确定的一个点，那就是operator[]是透过insert实现的，并且这个地方借助了insert的返回值。 

因此这个地方就需要重点关注insert的返回值，从图中来看，insert的返回值是pair，pair中的first是一个迭代器，它的second中是一个bool值，如果插入成功那就返回true，反之返回false。

那么下来我们就来看看[]里面具体的代码是怎么样的。

在这里我们可以看见insert在map的operator[]中不仅发挥着插入的作用，它还兼并着查找的作用。 

在operator[]里面需要insert一个pair，它的first为key，那么这里的second需要value的匿名对象去给值，也就是去调用它的默认构造，构造一个匿名对象去插入。

最后返回的是ret的first指向的second。

那么回到原始问题，这里第一次出现的水果该怎么处理。这里第一次处理，先走方括号里面的插入，key是水果value是次数，它value的类型为int，它匿名对象的缺省值就是0。

插入成功后返回迭代器，通过迭代器取得次数的别名的引用，最后完成++操作让其变成1。

如果不是第一次出现的话，这里的插入树中已经有key，在map中只看key并不看value，因此value为0并没有影响，我们依旧返回原来的迭代器，而后再进行++操作。

这里就是operator[]的一些经常出现的问题和其结果。

代码：

这里就是map和set基础知识的代码。 

#include
#include
#include
 
using namespace std;
 
//void test_set1()
//{
//	set s;
//	s.insert(1);
//	s.insert(5);
//	s.insert(2);
//	s.insert(4);
//	s.insert(3);
//	s.insert(3);
//
//	set::iterator it = s.begin();
//	while (it != s.end())
//	{
//		cout << *it << " ";
//		it++;
//	}
//	cout << endl;
//	auto pos = s.find(3);
//	s.erase(pos);
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//}
 
 
//void test_set1()
//{
//	set myset;
//	set::iterator itlow, itup;
//	for (int i = 1; i < 10; i++)
//	{
//		myset.insert(i * 10);
//	}
//	itlow = myset.lower_bound(30);
//	itup = myset.upper_bound(60);
//	myset.erase(itlow, itup);
//	for (set::iterator it = myset.begin(); it != myset.end(); ++it)
//	{
//		cout << *it << " ";
//	}
//	cout << endl;
//}
 
//void test_set1()
//{
//	multiset s;
//	s.insert(3);
//	s.insert(6);
//	s.insert(8);
//	s.insert(5);
//	s.insert(3);
//	s.insert(6);
//
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//	auto ret = s.equal_range(6);
//	auto itlow = ret.first;
//	auto itup = ret.second;
//
//	s.erase(itlow, itup);
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	cout << s.count(3) << " ";
//
//	cout << endl;
//}
 
//void test_map1()
//{
//	map dict;
//	pair kv1("insert", "插入");
//	dict.insert(kv1);
//
//	dict.insert(pair("sort", "排序"));
//
//	dict.insert({ "string","字符串" });
//}
 
//void test_map1()
//{
//	map dict;
//	dict.insert(pair("sort", "排序"));
//	map::iterator it = dict.begin();
//	while (it != dict.end())
//	{
//	/*	it->first = "xxx";*/
//		it->second = "xxx";
//
//		cout << (*it).first << ":" << (*it).second << " ";
//		cout << it->first << ":" << it->second << " ";
//	}
//	cout << endl;
//
//	for (const auto& kv : dict)
//	{
//		cout << kv.first << ":" << kv.second << endl;
//	}
//}
 
 
void test_map3()
{
	string arr[] = { "西瓜","苹果","凤梨","西瓜","西瓜","凤梨","西瓜","凤梨" };
	mapint> dict;
	/*for (auto e : arr)
	{
		auto it = dict.find(e);
		if (it == dict.end())
		{
			dict.insert(make_pair(e, 1));
		}
		else
		{
			it->second++;
		}
	}*/
	for (auto e : arr)
	{
		dict[e]++;
	}
	for (const auto& kv : dict)
	{
		cout << kv.first << ":" << kv.second << endl;
	}
}
 
int main() 
{
	test_map3();
	return 0;
}

结尾： 

到这里我们的set与map的一些基础知识就讲解完了， 但是这并不代表着map和set的知识就到此为止了，到后面我们会讲解map和set异常，AVL树等等都需要用到set和map，最后希望这篇博客能带来些许帮助。