前言：

    我们前面一起学习了二叉搜索树，这便是为了引入本章我们所学的map和set容器。map和set的底层实现就和二叉搜索树有关...

目录

（一）键值对的引入

（1）关联式容器

（2）键值对

（二）set

（1）set的介绍

（2）set的使用

set的插入：

 set的查找：

set的删除：

 （3）multiset的介绍+使用

（三）map

（1）map的介绍

（2）map的使用

map的插入：

std::map::operator[]的使用（*重点）：

（一）键值对的引入

（1）关联式容器

关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的 键值对，在数据检索时比序列式容器效率更高。

通常我们学习的都是树状结构的关联式容器

总结：

序列式容器：

• 在前期我们所学过的STL容器中，例如：string，vector，list，queue…，这些序列式容器中我们不难发现，其存储的都是 C++ 基本数据类型（诸如 int、double、float、string等）或使用自定义类型（结构体）的元素。

树状结构的关联式容器：

• 关联式容器则和序列式容器有很大区别，关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高。除此之外，序列式容器中存储的元素默认都是未经过排序的，而使用关联式容器存储的元素，默认会根据各元素的键值的大小做升序排序。

（2）键值对

关联式容器存放的是键值对，那么键值对是什么呢？

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。

 它实际上就是一个类模板，用来表示具有一 一对应关系的一种结构。

STL源码库给出的源代码如下：

（二）set

（1）set的介绍

使用 set 容器，必须引入该头文件#include < set >

set的使用文档

 介绍：

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

• 1. 与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放 value，但在底层实际存放的是由<value, value>构成的键值对。
• 2. set中插入元素时，只需要插入value即可，不需要构造键值对。
• 3. set中的元素不可以重复(因此可以使用set进行去重)。
• 4. 使用set的迭代器遍历set中的元素，可以得到有序序列
• 5. set中的元素默认按照小于来比较
• 6. set中查找某个元素，时间复杂度为：$log_2 n$
• 7. set中的元素不允许修改

（2）set的使用

set的插入：

和很多容器一样，set设置了插入的接口，但是set的插入是有额外的功能性的！ 

我们试用下面的代码：

void test_set1()
{
	set<int> s1;
	s1.insert(2);
	s1.insert(6);
	s1.insert(2);
	s1.insert(3);
	s1.insert(3);
	s1.insert(5);
	s1.insert(8);
	s1.insert(8);
	s1.insert(6);
	s1.insert(7);

//两种迭代打印的方法：：
	set<int>::iterator it = s1.begin();
	while (it != s1.end())
	{
		// 搜索树不允许修改key，可能会破坏搜索的规则
		//*it1 += 1;
		cout << *it << " ";
		++it;
	}
	cout << endl;


	for (auto e : s1)
	{
		cout << e << " ";
	}

}

输出结果：

 set实现了去重和排序：

• 有重复的不插入
• 默认按照升序排列

同样的迭代器的使用方式也一样，只是这里的const迭代器和普通迭代器都是一样的，都不支持修改，原因是如果对二叉搜索树进行修改的话，很有可能会导致整棵树的结构被打乱，所以不支持修改。

 set的查找：

 应用代码：
 

void test_set2()
{
	// 排序 + 去重
	set<int> s1;
	s1.insert(2);
	s1.insert(6);
	s1.insert(2);
	s1.insert(3);
	s1.insert(3);
	s1.insert(5);
	s1.insert(8);
	s1.insert(8);
	s1.insert(6);
	s1.insert(7);
	int x;
	while (cin >> x)
	{
		/*auto ret = s1.find(x);
		if (ret != s1.end())
			cout << "在" << endl;
		else
			cout << "不在" << endl;*/

		if (s1.count(x))
			cout << "在" << endl;
		else
			cout << "不在" << endl;
	}
}

这里find的用法和算法库里的一样，但是为什么要再在set中创立一个呢？

set自带的查找和算法库中的查找有什么区别

• set自带的查找是利用了搜索树的特点，查找时间复杂度为〇（logN）
• 如果用算法库中的查找则是通过暴力查找的方式进行的，时间复杂度为〇（N）

set的删除：

		set<int> s;
		s.insert(4);
		s.insert(5);
		s.insert(2);
		s.insert(1);
		s.insert(1);
		s.insert(3);
		s.insert(2);
		s.insert(1);

		s.erase(3);//直接给值删除

		for (auto e : s)
		{
			cout << e << " ";
		}
		cout << endl;

		int x;
		while (cin >> x)
		{
			set<int>::iterator pos = s.find(x);
			if (pos != s.end())
			{
				s.erase(pos);//迭代器删除
				cout << "删除" << x << "成功" << endl;
			}
			else
			{
				cout << x << "不在set中" << endl;
			}

			for (auto e : s)
			{
				cout << e << " ";
			}
			cout << endl;
		}
	

删除接口也没什么可以过多介绍的了，还有size、empty、clear等接口和我们之前学的容器接口用法一样，大家可以自己实践一下！

 （3）multiset的介绍+使用

set会自动实现去重的操作，那我们只想拥有排序等相关的操作，而不想去重，这里STL也为我们提供了multiset容器。

介绍：

• 1. multiset是按照特定顺序存储元素的容器，其中元素是可以重复的。
• 2. 在multiset中，元素的value也会识别它(因为multiset中本身存储的就是<value, value>组成 的键值对，因此value本身就是key，key就是value，类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的)，但可以从容器中插入或删除。
• 3. 在内部，multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。
• 4. multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢，但当使用迭代器遍历时会得到一个有序序列。
• 5. multiset底层结构为二叉搜索树(红黑树)。

用法：

void test_set3()
{
	multiset<int> s1;
	s1.insert(1);
	s1.insert(1);
	s1.insert(2);
	s1.insert(3);
	s1.insert(3);
	s1.insert(4);
	s1.insert(4);
	s1.insert(4);
	s1.insert(5);

	multiset<int>::iterator it = s1.begin();
	while (it != s1.end())
	{
		cout << *it << " ";
		it++;
	}

	cout << endl;

	auto ret = s1.find(1);
	cout << *ret << endl;
	while (ret != s1.end() && *ret == 1)
	{
		cout << *ret << " ";
		++ret;
	}
	cout << endl;
	cout << s1.count(1) << " ";
	cout << s1.count(5) << " ";

}

输出结果：

 这里我们看到，可以打印出重复的数据了，此时count的作用可以计数了，不需要局限于和find同等的用处。

（三）map

（1）map的介绍

使用 map 容器，必须引入该头文件#include < map >

map的使用文档

• 1. map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
• 2. 在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的 内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型 value_type绑定在一起，为其取别名称为pair: typedef pair<const key, T> value_type;
• 3. 在内部，map中的元素总是按照键值key进行比较排序的。
• 4. map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序
• 对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
• 5. map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
• 6. map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。

（2）map的使用

map的插入：

其实map的操作也和其他容器的操作是一样的，但由于map中存放的是键值对，所以我们以插入为例来介绍如何使用：

void test_map1()
{
	map<string, string> dict;
	//匿名对象的好处
	dict.insert(pair<string, string>("sort", "排序"));

	//不用匿名对象
	pair<string, string> kv("insert", "插入");
	dict.insert(kv);

	//make_pair是函数模板
	dict.insert(make_pair("left", "左边"));

	//可以这么写但是别这么用（隐式类型的转换） -- C++11再讲
	dict.insert({ "right", "右边" });

	//map的遍历
	map<string, string>::iterator it = dict.begin();
	while (it != dict.end())
	{
		//cout << *it << endl;//it->operator*() -- C++不支持返回两个值
		//cout << (*it).first << ":" << (*it).second << endl;

		cout << it->first << ":" << it->second << endl;

		it++;
	}
	cout << endl;

	for (const auto& kv : dict)
	{
		cout << kv.first << ":" << kv.second << endl;
	}
}

我们这里使用匿名对象配合insert使用非常方便，库中也给了make_pair函数模板来表示键值对的创建。

 因为C++不支持返回两个值，所以我们这里用到了pair，通过pair的first和second，即可访问到两个值。

同时，map迭代器的使用方法和其他容器迭代器的使用方法一样，这是STL设计时为了方便使用，所采用的高维度泛型设计。

Key_value模型中，修改不能修改key，但是可以修改value。

std::map::operator[]的使用（*重点）：

引入：

我们利用map来统计各个水果出现的次数：

通过查找来挨个遍历查找统计个数

void test_map2()
{
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果",
					 "西瓜", "苹果", "香蕉", "苹果", "香蕉" };

	map<string, int> countMap;
	for (auto& str : arr)
	{
		map<string, int>::iterator it = countMap.find(str);
		if (it != countMap.end())
		{
			it->second++;
		}
		else
		{
			countMap.insert(make_pair(str, 1));
		}
	}
}

注意：

• 只要是一对一对的值都可以用pair
• first和second是不允许被修改的

insert的返回值是一个pair，pair的first是一个迭代器（如果插入成功了指向新插入的位置，如果插入失败了，则返回已经存在的结点的位置），pair的second的一个bool值，插入成功是返回true，失败是返回false。

所以我们还可以通过返回值来统计个数

但是map库中给出 operator[ ] ，其实他的应用会让上述郭晨改变的更简单易懂！

• 在之前学习的容器中，operator[]都有随机访问的意思，这里的方括号已经没有了随机访问的意思
• 这里operator[]的参数是key，返回值是value的引用

其中可以对文档中的最后一句对此函数的调用等效于：

我么能深入探讨一下，理解如下：

所以operator[ ]的参数是key，返回值是value的引用！！！

我们可以用operator[ ]来统计次数：

因为返回的是value的引用所以，可以修改，这样一来，operator[]兼顾了两个功能：插入 + 修改

同样当map需要插入的时候，也就有了如下的写法：

void test_map2()
{
	map<string, string> dict;
	//dict.insert(pair<string, string>("sort", "排序"));
	dict.insert(make_pair("sort", "排序"));
	dict.insert(make_pair("string", "字符串"));
	dict.insert(make_pair("count", "计数"));
	dict.insert(make_pair("count", "(计数)"));//插入失败


	dict["left"] = "左面";//插入+修改
	dict["right"];//插入
	dict["count"] = "（计数）";//修改
	cout << dict["count"] << endl; // 查找

	//map<string, string>::iterator dit = dict.begin();
	auto dit = dict.begin();
	while (dit != dict.end())
	{
		//cout << (*dit).first << ":" << (*dit).second << endl;
		cout << dit->first << ":" << dit->second << endl;

		++dit;
	}
	cout << endl;
}

operator[ ]的使用不仅可以简化计数等，还可以兼顾插入、修改、查找等作用！大家重点理解！

感谢您的阅读！