【C++】7000字介绍map容器和set容器的功能和使用

（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;
//范围for
for (auto& e : s)
{
cout << e << " ";
}
cout << endl;

return 0;
}

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

（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);

五、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容器（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;

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码值进行排序。

七、multimap容器

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

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

八、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完成上述功能：

//使用insert
for (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++;
}
}

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函数，所以[ ]还能完成下述功能：