（1）、set是按照一定次序存储元素的容器

（2）、在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。

（3）、在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。

（4）、 set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。

（5）、set在底层是用二叉搜索树(红黑树)实现的。

3、注意事项：

（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中的元素不允许修改，因为底层是二叉搜索树，如果对元素进行修改，就可能不满足二叉搜索树的结构。

（8）、set中的底层使用二叉搜索树(红黑树)来实现 

（9）、头文件：<set>.

4、基本使用，更多接口可查看官网：

（1）、插入一组数字并用迭代器遍历。

#include<iostream>
using namespace std;
#include<set>int main()
{set<int> s;//插入s.insert(5);s.insert(2);s.insert(10);s.insert(7);s.insert(6);s.insert(1);s.insert(4);s.insert(3);s.insert(8);s.insert(9);//迭代器set<int>::iterator it = s.begin();while (it!= s.end()){cout << *it << " ";it++;}cout << endl;//范围forfor (auto& e : s){cout << e << " ";}cout << endl;return 0;
}

我们需要先查看文档学习相关接口和函数的介绍。迭代器对于各大容器都是一回事，所以使用方法是相同的。

set%E8%BF%9B%E8%A1%8C%E6%8E%92%E5%BA%8F%E5%92%8C%E5%8E%BB%E9%87%8D%E6%93%8D%E4%BD%9C%EF%BC%9A">（2）、习惯用set进行排序和去重操作：

根据上面的描述可知，set是根据搜索二叉树的中序遍历进行插入的，所以可以对一组数进行排序，并且不会插入相同的数，所以可以达到去重的功能。

（3）、三种erase（删除）的区别：

set提供了三种删除

第一种是删除某个迭代器位置：如果存在就删除，如果不存则报错：

这里涉及一个find函数：find函数为查找某个数，并返回该位置，若没找到则返回end();

	set<int> s;//插入s.insert(5);s.insert(2);s.insert(10);s.insert(7);s.insert(6);s.insert(1);s.insert(4);s.insert(3);s.insert(8);s.insert(9);//迭代器set<int>::iterator it = s.begin();it = s.find(1);//find函数为查找某个数，并返回该位置，若没找到则返回end();if (it != s.end()){s.erase(it);}

因为找不到会报错，所以需要用一个if语句进行判断，否则会如下：

第二种是删除某个val值，并返回删除的个数；

//第一二种删除，如果存在就删除，如果不存在就不做处理
s.erase(10);
s.erase(9);
s.erase(1000);

第三种是删除一个迭代器区间，左闭右开；

这里涉及两个操作：

lower_bound：返回大于等于k的位置

upper_bound：返回大于k的位置

利用上述两个函数得到一个左闭右开区间在进行删除。

假设我们删除区间[3，6]，因为erase的参数为左闭右开区间，所以我们需要得到区间

[3，7)，所以lower_bound可以得到左闭，upper_bound可以得到右开：

//第三种删除
//删除区间[3,6]，则需要得到区间[3,7）
auto start = s.lower_bound(3);
cout << "start指向的位置的值：" << *start << endl;
auto finish = s.upper_bound(6);
cout << "finish指向的位置的值：" << *finish << endl;
s.erase(start, finish);

set%E5%AE%B9%E5%99%A8%EF%BC%88%E5%85%81%E8%AE%B8%E6%8F%92%E5%85%A5%E9%87%8D%E5%A4%8D%E5%80%BC%EF%BC%89">五、multiset容器（允许插入重复值）

1、文档官网：

multiset - C++ Reference

2、介绍：

（1）、multiset是按照特定顺序存储元素的容器，其中元素是可以重复的。

（2）、 在multiset中，元素的value也会识别它(因为multiset中本身存储的就是<value, value>组成的键值对，因此value本身就是key，key就是value，类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的)，但可以从容器中插入或删除。

（3）、在内部，multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。

（4）、multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢，但当使用迭代器遍历时会得到一个有序序列。

（5）、 multiset底层结构为二叉搜索树(红黑树)。

3、基本使用：

multiset容器和set容器是类似的，最大的区别就是set不能存储重复的数据，而multiset容器可以存储重复的数据

int main()
{multiset<int> mus;//插入mus.insert(5);mus.insert(2);mus.insert(10);mus.insert(7);mus.insert(6);mus.insert(1);mus.insert(4);mus.insert(3);mus.insert(8);mus.insert(9);mus.insert(9);mus.insert(9);multiset<int>::iterator it = mus.begin();while (it != mus.end()){cout << *it << " ";it++;}cout << endl;return 0;
}

3、因为可以插入重复值，所以有些接口也有所区别：

（1）、第二种删除方式的返回值：

上面我们知道第二种删除时有返回值的，返回的就是删除元素的个数，在set容器中，返回值无非就是0和1，实际使用在这里才能体现出来：

（2）、count函数：

该函数的作用为：返回val值在容器中的个数，在set中返回值也无非就是0和1，在multiset容器中才能更好使用。

（3）、find函数

set中的find函数作用为：查找val值，存在则返回该位置，不存在则返回end()；

而mulitset容器可能存在多个重复值，所以功能会有所不同：

mulitset容器中find函数为： 找中序遍历中出现的第一个val值，并返回位置。

map%E5%AE%B9%E5%99%A8%EF%BC%88kvalue%E6%A8%A1%E5%9E%8B%EF%BC%9A%3Ckey%EF%BC%8Cvalue%3E%EF%BC%89">六、map容器（kvalue模型：<key，value>）

1、文档官网

map - C++ Reference

2、介绍：

（1）、 map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。

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

typedef pair<const key, T> value_type;

（3）、在内部，map中的元素总是按照键值key进行比较排序的。

（4）、map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。

（5）、map支持下标访问符，即在[ ]中放入key，就可以找到与key对应的value。

（6）、map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。

（7）、头文件：<map>

3、pair模板类：

因为map的成员是pair模版类对象，所以先学习pair模板类；

（1）、文档官网：

pair - C++ Reference

（2）、定义：

pair是一个模板类，定义在<utility>头文件中。它用于将两个不同类型的值组合成一个单一的对象（键值对）。这两个值可以是相同类型，也可以是不同类型。

该函数的作用就是构建一个pair对象：

	pair<int, int> pa1(1,1);cout << pa1.first << " " << pa1.second << endl;pair<int, int> pa2 = make_pair(2, 2);cout << pa2.first << " " << pa2.second << endl;

map%E7%9A%84%E5%9F%BA%E6%9C%AC%E4%BD%BF%E7%94%A8%EF%BC%8C%E6%9B%B4%E5%A4%9A%E6%8E%A5%E5%8F%A3%E5%8F%AF%E4%BB%A5%E6%9F%A5%E7%9C%8B%E5%AE%98%E7%BD%91%E8%BF%9B%E8%A1%8C%E5%AD%A6%E4%B9%A0%EF%BC%9A">4、map的基本使用，更多接口可以查看官网进行学习：

（1）、map模版参数的说明：

（1）、key: 键值对中key的类型

（2）、T： 键值对中value的类型

（3）、Compare: （仿函数）比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)

（4）、Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器

（5）、注意：在使用map时，需要包含头文件<map>

我们常用第一种方式，即参数是一个value_type类型的引用，而value_type是pair<T1,T2>的别名，所以实际参数是一个pair对象。返回值下面再介绍。

int main()
{map<string, string> ma;//一、使用匿名pair对象ma.insert(pair<string, string>("good", "好的"));//二、有名pair对象pair<string, string> pa("apple", "苹果");ma.insert(pa);//三、C++11中多参数隐式类型转换(构造函数)ma.insert({ "sort","排序" });//四、C++98常用make_pair函数链式调用：ma.insert(make_pair("age", "年龄"));map<string, string>::iterator it = ma.begin();while (it != ma.end()){cout << it->first << " " << it->second << endl;it++;}cout << endl;return 0;
}

打印时的注意事项：

这里不能直接解引用访问，因为map的成员变量为pair对象，是自定义类型，没有重载"<<"运算符，所以只能用结构体的两种访问方式：点（.）和' -> '。 

介意范围for加上引用，因为拷贝的代价有点大：

与set类似，map也有排序和去重的功能，并且是根据键值k进行操作的：

如果是字符串，排序则依次根据首字母的ascll码值进行排序。

map%E5%AE%B9%E5%99%A8">七、multimap容器

与set和mulitset类似，map也有一个与之对应的容器mulitmap容器

其他接口与上述类似，区别就是mulitmap容器可以插入重复值。插入是根据键值k来判断的，所以重复值即重复的键值k。

map%E5%AE%B9%E5%99%A8%E7%9A%84%5B%20%5D%EF%BC%88%E9%87%8D%E8%A6%81%EF%BC%89">八、map容器的[ ]（重要）

为了方便理解，我们以一个场景下进行讲解：

计算水果出现的次数：

string arr[] = { "苹果","菠萝","草莓","苹果","菠萝","草莓" ,"苹果","菠萝","草莓" "苹果","菠萝","草莓" };

1、使用迭代器和find函数：

for (auto& e : arr)
{map<string, int>::iterator flag = mapCount.find(e);if ( flag == mapCount.end())//说明没找到，则插入,并计数为1{mapCount.insert(make_pair(e, 1));}else//找到了，计数++{flag->second++;}
}

2、使用insert函数的返回值

查看官网我们发现，使用map的[  ]时，会转化为如下：

我们可以看到是复用了insert函数，并运用了insert函数的返回值。所以首先我们需要理解insert的返回值是什么？

查看官网可以发现insert的返回值是一个pair<iterator，bool>的类模板类型：

因为不想新构造类模板，所以这里复用了pair类模板，pair类模板是一个单独的类模版，不是map独有的，所以每个地方都可以使用。

返回值模版参数的介绍：

（1）、bool：插入成功则为true，插入失败则为false（有重复键值K,则插入失败）；

（2）、iterator：插入成功，则指向新插入元素所在的结点；插入失败，则指向map中与之键值k重复的那个结点。

知道了返回值的含义，我们就可以使用insert完成上述功能：

	//使用insertfor (auto& e : arr){//构建insert返回值的pair对象pair<map<string, int>::iterator, bool> ret;ret = mapCount.insert(make_pair(e, 1));if (ret.second == false){//插入失败，说明已经存在，则计数++ret.first->second++;}}

map%E7%9A%84%5B%20%5D">3、使用map的[ ]

上述说明使用map的[ ]时，会转化为如下：

这样不方便观察，所以简化如下：

也就是说其实是复用了insert的返回值，来找到对应map结点位置的second。

其中，V()是默认构造的缺省值，（如int()），V为int，则默认值为0，V为指针，则默认值为nullptr。

所以可以使用[ ]完成水果计数：

//使用map的[ ]
for (auto& e : arr)
{mapCount[e]++;
}

参数e用键值key的引用进行接收，然后调用insert函数，若插入成功，则返回值pair对象的模版参数iterator就指向新插入这个结点，若插入失败，则指向map中重复键值K那个结点，最后返回该结点的second，所以我们在外面对mapCount[e]进行++，其实就是对键值K为e的那个结点的second进行++，以此达到计数的功能。

因为[ ]复用了insert函数，所以[ ]还能完成下述功能：