一、序列式容器和关联式容器
1、STL中的部分容器如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间一般没有紧密的关联关系，比如交换一下，它依旧是序列式容器，不会破坏逻辑结构。
2、关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是非线性结构，两个位置有紧密的关联关系，交换一下，它的存储结构就被破坏了。关联式容器中的元素是按关键字(key)来保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。
3、map和set底层是红黑树，红黑树是一颗平衡⼆叉搜索树(时间复杂度为
)。set是key搜索场景的结构，map是key/value搜索场景的结构。大家在学习set和map的时候，要结合我们上篇二叉搜索树中的两个场景的实现过程进行理解。
二、
1、set容器
set是key搜索场景的结构，这里的第一个模板参数T其实就是K(key)，第二个参数是仿函数，提供仿函数的目的是：保证set容器中的数据是按升序排列的还是降序排列的，第三个参数是空间配置器，set底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第三个参数，基本上每个容器都有这个东西，我们暂且用它的缺省值即可。
一般情况下，我们都不需要传后两个模版参数。
set底层是用红黑树实现，增删查效率是
，它的迭代器遍历是走的搜索树的中序，由于二叉搜索树的性质，左子树小于根，根小于右子树，所以中序遍历的结果是有序的。
我们在此之前已经学习了vector/list等容器的使用，STL容器接口的设计高度相似，所以这里我们
就不再一个接口一个接口的介绍，只挑选比较重要的接口进行介绍。
(1)构造函数和迭代器
set的支持正向和反向迭代遍历，它的迭代器是双向迭代器，双向迭代器支持++/–，但是不支持+/-，遍历默认按升序顺序，因为底层是⼆叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围for，set的iterator和const_iterator都不支持迭代器修改数据(修改key的值)，如果修改就破坏了底层搜索树的结构。
//empty (1) 无参默认构造，第一个参数是仿函数对象
explicit set(const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
//range (2) 迭代器区间构造
template
set(InputIterator first, InputIterator last,
const key_compare& comp = key_compare(),
const allocator_type& = allocator_type());
//copy (3) 拷⻉构造
set(const set& x);
//initializer list (4) C++11支持: initializer 列表构造
set(initializer_list il,
const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
//迭代器是一个双向迭代器
iterator -> a bidirectional iterator to const value_type
//正向迭代器
iterator begin();
iterator end();
//反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();
对应代码说明：
int main()
{
set s1; //无参构造
set::iterator it1 = s1.begin();
while (it1 != s1.end())
cout v1({ 5,7,2,8,1,9,6,3,4 }); //vector支持用初始化列表构造
set s2(v1.begin(), v1.end()); //迭代器区间构造
set::iterator it2 = s2.begin();
while (it2 != s2.end())
cout s3(s2); //拷贝构造
set::iterator it3 = s3.begin();
while (it3 != s3.end())
cout s4({6,5,4,3,2,1}); //初始化列表构造
cout ::iterator it4 = s4.begin();
while (it4 != s4.end())
cout ::reverse_iterator rit4 = s4.rbegin();
while (rit4 != s4.rend())
cout 运行结果：
不难发现，无论是以什么样形式初始化，它们的正向迭代器打印结果都是从小到大， 这是因为它的底层就是key搜索场景，迭代器在走的时候会进行中序遍历，在二叉搜索树中，中序遍历的结果就是顺序的，这里的第一个模板参数的仿函数默认是less，就是用less来控制插入时比较的方式，从而达到升序的效果，如果我们想让它是降序输出，那么只需显示传第一个模板参数的仿函数为greater，如果仿函数是greater那么底层二叉搜索树就是左孩子比父亲大，右孩子比父亲小，中序遍历时就是降序。如果T是自定义类型，若库中的仿函数不支持比较T的大小或者支持比较T的大小但比较的规则不是我们想要的那样，那我们就可以单独写一个仿函数，在默认构造时传我们单独写的仿函数对象给第一个默认构造参数。需要注意的是，第一个模板参数如果是排降序类型，如果要传第一个默认构造函数的参数，那也必须是这个排降序类型的对象；第一个模板参数如果是排升序类型，如果要传第一个默认构造函数的参数，那也必须是这个排升序类型的对象。
(2)增删查
set支持增删查，但不支持修改，因为修改可能会破坏内部性质。
相关接口如下：
//注：
//key_type -> The first template parameter (T) 即第一个模板参数T
//value_type -> The first template parameter (T) 即第一个模板参数T
//在set中key_type和value_type是一样的，都是第一个模板参数T(key)
//因为map底层是key/value场景，所以set中的key_type和value_type是为了与map保持一致
//1.单个数据插入，如果已经存在则插入失败
pair insert(const value_type& val);
//2.列表插入，已经在容器中存在的值不会插入
void insert(initializer_list il);
//3.迭代器区间插入，已经在容器中存在的值不会插入
template
void insert(InputIterator first, InputIterator last);
//1.删除一个迭代器位置的值，erase就是"有"就删，"没有"就不删，"没有"不会报错
iterator erase(const_iterator position);
//2.删除val，val不存在返回0，存在返回1
//这么做也是因为要兼容multiset，因为在multiset中val的值可能有多个
size_type erase(const value_type& val);
//3.删除一段迭代器区间的值
iterator erase(const_iterator first, const_iterator last);
//查找val，返回val所在的迭代器，没有找到返回end()，它的查找逻辑就是按平衡二叉搜索树进行的，时间复杂度是O(logN)
iterator find(const value_type& val);
代码说明：
int main()
{
//set容器在插入数据时：排序+去重
//set s1; //默认排升序
set> s1; //排降序
s1.insert(5);
s1.insert(2);
s1.insert(7);
s1.insert(5); //插入相同的值会失败
s1.insert({ 2,8,3,9,2 }); //支持插入初始化列表，重复的值不会插入多次
set::iterator it = s1.begin();
while (it != s1.end())
{
//*it = 1; //迭代器指向的内容不允许修改(set容器中的值不允许修改)
cout strset = { "sort","insert","add" };
//set容器中存放的是string类型的元素
//string类型支持比较大小，它是按ASCII码进行比较的
for (auto e : strset)
cout s2 = { 4,2,7,2,8,5,9 };
for (auto e : s2)
cout > x1;
int num = s2.erase(x1);
if (num == 0)
cout > x2;
auto pos = s2.find(x2);
if (pos != s2.end())
{
s2.erase(pos); //删除后，pos位置的迭代器就失效了
//pos位置分为两种情况，第一:pos位置的结点只有左孩子或右孩子或是叶子节点，那么根据二叉搜索树的删除逻辑，删除后pos就是野指针了
//第二:如果pos位置结点左右都有孩子，就用替换法删除，删除后，pos虽然不是野指针，但它指向的意义已经发生变化
//这两种情况都可以称为迭代器失效，所以库中的erase返回值是一个迭代器，它返回删除位置的下一位置的迭代器
//cout > x3;
set s3 = { 4,2,7,2,8,5,9 };
//算法库中的查找
auto pos1 = find(s3.begin(), s3.end(), x3);
//set容器自身实现的查找
auto pos2 = s3.find(x3);
//算法库中的find是针对任何容器设计的，它的查找逻辑是在整个迭代区间遍历查找(暴力查找)，所以它的时间复杂度是O(N)
//set容器中的find是根据平衡二叉搜索树的查找逻辑进行查找的，所以它的时间复杂度是O(logN)
//所以，在set容器中，尽量用它自身的find，不要用算法库中的find
return 0;
}运行结果：
(3)swap()
它的作用就是交换两个容器的根节点。
代码说明：
int main()
{
set s1({5,4,3,2,1});
set s2({ 10,9,8,7,6 });
for (auto e : s1)
cout 运行结果：
(4)clear()
它的功能就是删除容器中所有数据。
代码说明：
int main()
{
set s1({ 5,4,3,2,1 });
for (auto e : s1)
cout 运行结果：
(5)count()
size_type是一个无符号整型，count的功能是查找val，返回val的个数，这里只有0和1两种情况，因为set容器中不允许有重复val，可以理解为：返回0代表该值在容器中不存在，如果为1则存在，这么做的原因还有一个就是要兼容multiset，因为在multiset中val的值可能有多个。
代码说明：
int main()
{
set s1({ 5,4,3,2,1 });
for (auto e : s1)
cout > x)
{
if (s1.count(x))
cout 运行结果：
(6)lower_bound与upper_bound
lower_bound的功能是返回第一个大于等于val位置的迭代器(按照搜索树的规则找)
upper_bound的功能是返回第一个大于val位置的迭代器(按照搜索树的规则找)
一个是大于等于，一个是大于，注意不要混淆。
这样设计方便我们去找一段区间，找到一段区间就可以针对这段区间进行相关操作。
代码说明：
int main()
{
set s1;
for (int i = 1; i =30 和 >50
auto itlow1 = s1.lower_bound(30); //返回第一个大于等于30位置的迭代器
auto itup1 = s1.upper_bound(50); //返回第一个大于50位置的迭代器
//这样就把set中在[30,50]这个区间的所有元素找出来了，删除即可
s1.erase(itlow1, itup1); //删除的区间为"左闭右开"
for (auto e : s1)
cout s2;
for (int i = 1; i =25 和 >55
auto itlow2 = s2.lower_bound(25); //返回第一个大于等于30位置的迭代器
auto itup2 = s2.upper_bound(55); //返回第一个大于50位置的迭代器
//这样就把set中在[25,55]这个区间的所有元素找出来了，删除即可
s2.erase(itlow2, itup2); //删除的区间为"左闭右开"
for (auto e : s2)
cout 运行结果：
2、multiset容器
multiset和set的使用基本完全类似，主要区别点在于multiset支持值冗余，相同的值，插入到该结点的左边还是右边都可以，没有什么区别，但是要统一，不能一会插入到左边一会插入到右边，允许数据冗余那么insert/find/count/erase这几个函数就会与set有所差异。
代码说明：
int main()
{
//multiset容器在插入数据时：排序+不去重
multiset s = { 4,2,7,2,4,8,4,5,4,9 };
auto it = s.begin();
while (it != s.end())
{
cout > x;
//输出所有的x
auto pos = s.find(x);
while (pos != s.end() && *pos == x)
{
cout 运行结果：
三、
1、map容器
map是key/value搜索场景的结构，这里的前两个模板参数分别是key和value，第三个模板参数是仿函数，提供仿函数的目的是：保证map容器中的数据是按升序排列的还是降序排列的(这里的排升序是根据key的值排的)，第四个参数是空间配置器。一般情况下，我们都不需要传后两个模版参数。
map底层是用红黑树实现，增删查改效率是 ，迭代器遍历是走的中序，所以是按Key有序顺序遍历的。
(1)pair类型
map底层的红黑树结点中的数据，使用pair存储键值对数据。
下面是库中pair的一部分源码：
typedef pair value_type;
template
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
pair(const pair& pr) //有参构造
:first(pr.first)
,second(pr.second)
{}
};
template
inline pair make_pair(T1 x, T2 y) //创建pair对象
{
return (pair(x, y));
}
pair的第一个模板参数就是key，第二个模板参数就是value，对应的就是first就是key，second就是value。相当于将key和value捆绑起来放在名为pair的结构体中，这个结构体有两个成员first和second，first就是key，second就是value。因为key不能被改变所以加了const，value可以被允许改变所以没有加const。将它们两个捆绑起来目的是在后面它们迭代器解引用时方便打印数据。
value_type就是pair类型。
(2)构造函数和迭代器
map容器支持正向和反向迭代遍历，遍历默认按key的升序顺序，因为底层是二叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围for，map支持修改value数据，但是不支持修改key数据，修改关键字数据，会破坏底层搜索树的结构。
map的构造我们关注以下几个接口即可：
//empty (1) 无参默认构造
explicit map(const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
//range (2) 迭代器区间构造
template
map(InputIterator first, InputIterator last,
const key_compare& comp = key_compare(),
const allocator_type & = allocator_type());
//copy (3) 拷贝构造
map(const map& x);
//initializer list (4) initializer 列表构造
map(initializer_list il,
const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
//迭代器是一个双向迭代器
iterator->a bidirectional iterator to const value_type
//正向迭代器
iterator begin();
iterator end();
//反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();
它跟set容器用法几乎一样，这里只讲一个初始化列表构造：
#include 调试结果：
(3)增删查
map插入的是pair键值对数据，跟set所有不同，但是查和删的接口只用关键字key跟set是完全类似的，不过find返回iterator，不仅仅可以确认key在不在，还找到key映射的value，同时通过迭代还可以修改value。
map的增删查关注以下几个接口即可：
//key_type -> The first template parameter (Key) 即第一个模板参数Key
//mapped_type -> The second template parameter (T) 即第二个模板参数T(value)
//value_type -> pair 即pair (pair)
//单个数据插入，如果已经存在key则插入失败，若存在key相等但value不相等也会插入失败
pair insert(const value_type& val);
//列表插入，已经在容器中存在的值不会插入
void insert(initializer_list il);
//迭代器区间插入，已经在容器中存在的值不会插入
template
void insert(InputIterator first, InputIterator last);
//查找k，返回k所在的迭代器，没有找到返回end()
iterator find(const key_type& k);
//删除一个迭代器位置的值
iterator erase(const_iterator position);
//删除k，k存在返回0，存在返回1
size_type erase(const key_type& k);
//删除一段迭代器区间的值
iterator erase(const_iterator first, const_iterator last);
代码说明：
int main()
{
map dict1;
pair kv1("first","第一个");
dict1.insert(kv1); //直接传一个有名对象
dict1.insert(pair("second", "第二个")); //传匿名对象
dict1.insert(make_pair("third","第三个"));//make_paia是一个模板，它接收两个模板参数，并返回一个pair对象，它可以减少代码长度
dict1.insert({ "sort","排序" });//C++11，隐式类型转换，{"sort","排序"}可以转换成一个pair的对象(前提是pair支持两个参数的构造函数)
//插入失败
dict1.insert({ "sort","排序xxx" }); //在map中，如果插入和key的值相等但与value的值不相等，它是不会更新value的，因为插入的时候只看key，key如果相等，就不插入
//遍历dict
//map::iterator it1 = dict.begin();
auto it1 = dict1.begin();
while (it1 != dict1.end())
{
//cout first += 'x'; //key不支持修改
it1->second += 'x'; //value支持修改
//也可以这样写:
cout first second ()->first ()->second dict2;
dict2.insert({ {"left","左边"},{"right","右边"},{"up","向上"}});//隐式类型转换
auto it2 = dict2.begin();
while (it2 != dict2.end())
{
cout first second 因为map的删除和查找只和key有关，所以它的删除和查找几乎和set一样，大家可以直接参考set容器的删除和查找。
(4)其它
map的swap、clear、count、 lower_bound与upper_bound几乎和set一模一样，直接参考set容器的这一部分即可。
(5)equal_range
它的功能是返回k的左闭右开区间，如果k为20，就返回[20,第一个大于b的值)，这一迭代区间，这一函数在multimap中效果很好，因为它可以找到所有的k。
(6)operator[]
在map容器中，它重载了[]，这点是与set容器是不同的。
它虽然重载了[]，但此时的意义已经和数组中那个下标引用操作符不同了，这里是传一个key，返回对应的value的引用。
这里的[]具有三重功能：插入、查找、修改。这里的插入指的是如果传入的key，在map中找不到，那就将key插入到map容器中，它的底层会调用insert。查找是指要先查找key是否存在这个过程。修改是指我们可以对返回值value进行修改。
insert函数也就是下面这个：
pair insert(const value_type& val);
我们在上面讲了它的用法，但没讲它的返回值，接下来我们就研究一下它的返回值：
它的返回值是pair类型，但是它与上面pair是不同的，模板参数就不一样，⼀个是map底层红⿊树节点中存的pair，另⼀个是insert返回值pair。
这里的pair中第一个模板参数是一个迭代器，如果插入成功，返回新插入的元素位置的迭代器；如果插入失败，返回key位置的迭代器。也就是说无论插入成功还是失败，返回pair对象的first都会指向key所在的迭代器。
这里的pair中第二个模板参数bool类型就是当key存在，那就插入失败，返回false；当key不存在，那就插入，返回true。
插入成功：pair
插入失败：pair
insert插入失败时充当了查找的功能，正是因为这⼀点，insert可以用来实现operator[]。
operator的内部实现就像下面这样：
mapped_type& operator[] (const key_type& k)
{
//1.如果key不在map中，insert会插入key和mapped_type(value)的默认值
//同时[]返回结点中存储的mapped_type(value)值的引用，那么我们可以通过引用修改value值。所以[]具备了插入+修改功能
//2.如果k在map中，insert会插入失败，但是insert返回pair对象的first是指向与key值相同的结点的
//迭代器，同时[]返回结点中存储mapped_type(value)值的引用，所以[]具备了查找+修改的功能
pair ret = insert({ k, mapped_type() });
iterator it = ret.first;
return it->second;
}
我们来举个例子，可能会帮助大家更好的理解：
int main()
{
//利用find和iterator修改功能，统计水果出现的次数
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
map countMap;
for (const auto& str : arr)
{
//先查找水果在不在map中
//1、不在，说明水果第一次出现，则插入{水果, 1}
//2、在，则查找到的节点中水果对应的次数++
auto ret = countMap.find(str);
if (ret == countMap.end())
countMap.insert({ str, 1 });
else
ret->second++;
}
for (const auto& e : countMap)
cout 这段代码是统计各个水果出现的次数的，我们在上一篇二叉搜索树中讲到过，只不过这里换成了map容器进行操作，底层还是一样的。
运行结果：
我们上面学习了解了[]，现可以对这段代码进行优化：
int main()
{
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
map countMap;
for (const auto& str : arr)
{
countMap[str]++; //一句代码搞定问题
//如果map中没有str，那么就插入str，并初始化value为0，返回value的引用，接着++，相当于首次插入str，并将对应的value置为1
//如果map中有str，那么就返回当前str位置上的value的引用，接着++，相当于，只对value进行了加1操作，value就是水果的个数，逻辑上没有任何问题
}
for (const auto& e : countMap)
cout 运行结果：
结果没有问题，大大简化了代码的复杂度。
我们再来看一个例子：
int main()
{
map dict;
dict.insert(make_pair("sort", "排序"));
//insert不存在：插入
dict["insert"]; //insert({"insert", string()})
//left不存在：插入+修改
dict["left"] = "左边"; //将""修改为"左边"
//left存在：修改
dict["left"] = "左边、剩余"; //将"左边"修改为"左边、剩余"
//left存在：查找（确认left在才能这么用，否则就是插入了）
cout 2、multimap容器
multimap和map的使用基本完全类似，主要区别点在于multimap支持关键值key冗余，那么multimap在插入数据时一定会成功，除非空间不够，否则就不会插入失败，insert/find/count/erase都围绕着支持关键值key冗余有所差异，这里跟set和multiset完全一样，比如find时，有多个key，返回中序第一个；erase时，它的内部先利用find找到第一个key，然后开始依次删除，直到key删除完全，其次就是multimap不支持[]，因为multimap支持key冗余，调用[]会返回对应的value，如果支持key冗余，那调用后返回哪一个value呢？所以multimap不支持[]。
代码说明：
int main()
{
multimap dict;
//插入一定成功
dict.insert({ "sort", "排序1" });
dict.insert({ "sort", "排序1" });
dict.insert({ "sort", "排序2" });
dict.insert({ "sort", "排序3" });
dict.insert({ "sort", "排序3" });
dict.insert({ "string", "字符串" });
//将sort全部删除
dict.erase("sort");
return 0;
}erase执行前调试结果：
erase执行后调试结果：
四、结语
本篇内容到这里就结束了，主要讲了set和multiset容器以及map和multimap容器的基本使用，希望对大家有帮助，祝生活愉快，我们下一篇再见！
