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

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

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

本章节讲解的map和set底层是红⿊树，红⿊树是⼀颗平衡⼆叉搜索树。set是key搜索场景的结构，map是key/value搜索场景的结构。

2. set系列的使⽤

参考文档链接：

https://legacy.cplusplus.com/reference/set/

首先我们还是先打开文档，然后我们会看到下面这个部分

我们可以看到set由两部分set与multiset组成，set的模型就是上一节我们写的不允许重复元素的key模型，multiset就是允许数据冗余的key模型，下面我们就来分别介绍：

2.1 set的介绍

• set的声明如上，T就是set底层关键字的类型（也就是上一节学的k）
• set默认要求T⽀持⼩于⽐较，如果不⽀持或者想按⾃⼰的需求⾛可以⾃⾏实现仿函数传给第⼆个模版参数
• set底层存储数据的内存是从空间配置器申请的，如果需要可以⾃⼰实现内存池，传给第三个参数。
• ⼀般情况下，我们都不需要传后两个模版参数。
• set底层是⽤红⿊树实现，增删查效率是 O(logN) ，迭代器遍历是⾛的搜索树的中序，所以是有序的。
• 前⾯部分我们已经学习了vector/list等容器的使⽤，STL容器接⼝设计，⾼度相似，所以这⾥我们就不再⼀个接⼝⼀个接⼝的介绍，⽽是直接带着⼤家看⽂档，挑⽐较重要的接⼝进⾏介绍。

（1）set的构造和迭代器：

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

这一部分我们就看一下文档里的例子就可以了，与之前的string，vector差不多。

（2）set的增删查

下面是使用代码：

void settest1()
{//set<int> st;int arr[] = { 8,1,0,7,3,9,2 };for (auto& e : arr){st.insert(e);}set<int>::iterator it = st.begin();while (it != st.end()){cout << *it << ' ';it++;}cout << endl;//普通的插入set<int> st2;st2.insert(arr, arr + sizeof(arr) / sizeof(int));for (auto& e : st2){cout << e << ' ';}cout << endl;set<int> st3(st2);for (auto& e : st3){cout << e << ' ';}cout << endl;//拷贝构造set<int> st4 = st3;for (auto& e : st4){cout << e << ' ';}cout << endl;//赋值构造set<int> st5({ 8,1,0,7,3,9,2 });//隐式类型转换for (auto& e : st5){cout << e << ' ';}cout << endl;//删除最小值st5.erase(st5.begin());for (auto& e : st5){cout << e << ' ';}cout << endl;st5.erase(--st5.end());//删除最大值for (auto& e : st5){cout << e << ' ';}cout << endl;//指定数据的删除int x = 0;cin >> x;st4.erase(x);for (auto& e : st4){cout << e << ' ';}cout << endl;//利用指定位置的迭代器来删除set中的元素cin >> x;set<int>::iterator pos = st4.find(x);st4.erase(pos);for (auto& e : st4){cout << e << ' ';}cout << endl;查找某个数据//cin >> x;//set<int>::iterator pos1 = st3.find(x);set本身提供的//set<int>::iterator pos2 = find(st3.begin(), st3.end(), x);算法库里提供的int count = st3.count(3);//这个接口原本返回的count是指这个数在set容器里的个数，set只要存在都只会是1//因为set不支持数据冗余if (st3.count(8))//在这里格外好用{cout << "存在" << endl;}else{cout << "不存在" << endl;}
}

此外在这里我介绍一下迭代器
常见的迭代器划分：

我们怎样来容器的迭代器类型呢？

迭代器的类型取决于容器的底层结构，知道迭代器的类型才能更好地帮助我们使用算法，例如，官方sort：

sort并不是我们随便传一个迭代器就可以使用，必须是随机迭代器，set的迭代器就是双向的，这一点大家需要知道。

我们在回归set这里：

set还支持最下面这三个接口，最后一个接口我这里不讲，lower_bound的接口的意思是返回大于等于我们传入的值的迭代器的接口（这个值可以不存在），upper_bound是返回大于当前传入值的迭代器（同前），那他俩有啥用呢，简单的来说这里可以完成区间的删除
例如：

void settest2()
{//区间删除set<int> st;for (int i = 1; i <= 9; i++){st.insert(i * 10);}set<int> st1(st);for (auto e : st){cout << e << ' ';}cout << endl;//这里我们的set里存着10-90的数据，现在我们需要删除30-50auto itbegin = st.lower_bound(30);//取大于等于30的区间auto itend = st.upper_bound(60);//取大于60的区间//这里的区间是左闭右开的st.erase(itbegin, itend);for (auto e : st){cout << e << ' ';}cout << endl;//假如我们10-90这几个数，我们现在要删除25-55的数字怎么办？auto itbegin1 = st1.lower_bound(25);auto itend1 = st1.upper_bound(55);st.erase(itbegin1, itend1);for (auto e : st1){cout << e << ' ';}cout << endl;
}

2.2 multiset的介绍

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

void multisettest()//允许冗余
{multiset<int> mus({ 9,0,1,3,4,4,2,7,8,9 });for (auto e : mus){cout << e << ' ';}cout << endl;//唯一的差别是如果我们要查找的值有重复，它会返回第一个在中序中出现的那个auto pos = mus.find(4);mus.erase(pos);for (auto e : mus){cout << e << ' ';}cout << endl;//count会返回存在的个数cout << "9->";cout << mus.count(9) << endl;//删除第一个9前auto pos1 = mus.find(9);mus.erase(pos1);for (auto e : mus){cout << e << ' ';}cout << endl;cout << "9->";cout << mus.count(9) << endl;//删除第一个9后
}

以上就是set的简单使用，此外set用于做题也十分好用，例如
349. 两个数组的交集 - ⼒扣（LeetCode）
142. 环形链表 II - ⼒扣（LeetCode）
这两个题目，大家自己下来去尝试去做一下。

3 map

3.1 参考文档

https://legacy.cplusplus.com/reference/map/

3.2 map类的介绍

首先它也是分为map与multimap，同样multimap允许数据冗余

map的声明如下，Key就是map底层关键字的类型，T是map底层value的类型，set默认要求Key⽀持⼩于⽐较，如果不⽀持或者需要的话可以⾃⾏实现仿函数传给第⼆个模版参数，map底层存储数据的内存是从空间配置器申请的。⼀般情况下，我们都不需要传后两个模版参数。map底层是⽤红⿊树实现，增删查改效率是 O(logN) ，迭代器遍历是⾛的中序，所以是按key有序顺序遍历的

3.3 pair类型介绍

map底层的红⿊树节点中的数据，使⽤pair<Key, T>存储键值对数据。

typedef pair<const Key, T> value_type;
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){}template<class U, class V>pair (const pair<U,V>& pr): first(pr.first), second(pr.second){}
};
template <class T1,class T2>
inline pair<T1,T2> make_pair (T1 x, T2 y)
{return ( pair<T1,T2>(x,y) );
}

这段代码看不懂没关系，我们只需要记住，pair里的第一个元素也就是first就是我们的key，第二个元素second就是我们的value。

3.4 map的构造

map的构造我们关注以下⼏个接⼝即可。

map的⽀持正向和反向迭代遍历，遍历默认按key的升序顺序，因为底层是⼆叉搜索树，迭代器遍历⾛的中序；⽀持迭代器就意味着⽀持范围for，map⽀持修改value数据，不⽀持修改key数据，修改关键字数据，破坏了底层搜索树的结构。

void maptest1()//map是key_value模型，比较的逻辑仍然是key
{map<int, string> mp({ {1,"mid"},{0,"left"},{2,"right"} });auto it = mp.begin();while (it != mp.end()){cout << it->first << ";" << it->second << endl;it++;}cout << endl;pair<string, int> str1("香蕉", 2);pair<string, int> str2("苹果", 1);pair<string, int> str3("菠萝", 5);map<string, int> mp1;mp1.insert(str1);mp1.insert(str2);mp1.insert(str3);auto it1 = mp1.begin();while (it1 != mp1.end()){cout << it1->first << ";" << it1->second << endl;it1++;}cout << endl;map<string, int> mp2;mp2.insert(pair < string, int>("香蕉", 2));//匿名对象mp2.insert(make_pair("苹果", 1));mp2.insert({ "菠萝",5 });//隐式类型转换这种方式日常常用一点auto it2 = mp2.begin();while (it2 != mp2.end()){cout << it2->first << ";" << it2->second << endl;it2++;}cout << endl;
}

这些就是map的构造、插入删除等接口。

3.6 map的数据修改

前⾯我提到map⽀持修改mapped_type 数据，不⽀持修改key数据，修改关键字数据，破坏了底层搜索树的结构。

map第⼀个⽀持修改的⽅式时通过迭代器，迭代器遍历时或者find返回key所在的iterator修改，map还有⼀个⾮常重要的修改接⼝operator[]，但是operator[]不仅仅⽀持修改，还⽀持插⼊数据和查找数据，所以他是⼀个多功能复合接⼝需要注意从内部实现⻆度，map这⾥把我们传统说的value值，给的是T类型，typedef mapped_type。⽽value_type是红⿊树结点中存储的pair键值对值。⽇常使⽤我们还是习惯将这⾥的T映射值叫做value。

void maptest2()
{
//	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
//"苹果", "香蕉", "苹果", "香蕉" };
//
//	map<string, int> countMap;//创建map
//
//	for (const auto& str : arr)//遍历数组
//	{
//		auto ret = countMap.find(str);//如果没找到返回end迭代器，如果找到了返回当前迭代器
//		if (ret == countMap.end())//map中不存在
//		{
//			countMap.emplace(str, 1);
//		}
//		else//已经存在
//		{
//			ret->second++;
//		}
//	}
//
//	auto it = countMap.begin();
//	while (it != countMap.end())
//	{
//		cout << it->first << ";" << it->second << endl;
//		it++;
//	}
//	cout << endl;
//	//第一种方式
//
//	auto it1 = countMap.begin();
//	while (it1 != countMap.end())
//	{
//		cout << (*it1).first << ':' << (*it1).second << endl;
//		it1++;
//	}
//	cout << endl;// 利⽤[]插⼊+修改功能，巧妙实现统计⽔果出现的次数string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };map<string, int> countMap;for (const auto& str : arr){// []先查找⽔果在不在map中// 1、不在，说明⽔果第⼀次出现，则插⼊{⽔果, 0}，同时返回次数的引⽤，++⼀下就变成1次了// 2、在，则返回⽔果对应的次数++countMap[str]++;}for (const auto& e : countMap){cout << e.first << ":" << e.second << endl;}cout << endl;
}

pair<iterator,bool> insert (const value_type& val);
mapped_type& operator[] (const key_type& k);
// operator的内部实现
mapped_type& operator[] (const key_type& k)
{
// 1、如果k不在map中，insert会插⼊k和mapped_type默认值，同时[]返回结点中存储
mapped_type值的引⽤，那么我们可以通过引⽤修改返映射值。所以[]具备了插⼊+修改功能
// 2、如果k在map中，insert会插⼊失败，但是insert返回pair对象的first是指向key结点的
迭代器，返回值同时[]返回结点中存储mapped_type值的引⽤，所以[]具备了查找+修改的功能
pair<iterator, bool> ret = insert({ k, mapped_type() });
iterator it = ret.first;
return it->second;
}

3.7 multimap和map的差异

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