?作者：一只大喵咪1201
?专栏：《C++学习》
?格言：你只管努力，剩下的交给时间！

map和set的使用

?关联式容器⚡键对值 ?set⚡构造函数⚡增删查改 ?multiset?map⚡构造函数⚡增删查改⚡operator[] ?multimap?map和set在题目中的应用⚡统计前K个高频单词⚡求两个数组的交集 ?总结

map和set的底层都是二叉搜索树，只是做了更进一步的限制，使其不会出现单只的情况，搜索的时间复杂度保证在O(log2N)，具体的底层结构后面本喵再详细介绍，现在先来认识以下set和map

?关联式容器

首先要知道的是序列式容器，这种容器我们之前接触过，比如vector，list，deque等等。

序列式容器：

底层为线性的数据结果(物理上或者逻辑上)，容器中的元素储存的是元素本身。而且我们之前在使用序列式容器的时候，插入数据和删除数据只管操作就行，不用考虑其他因素。

关联式容器：

存储的是<key，value>结构的键对值，在数据检索时比序列式容器效率更高。插入和删除数据时，要考虑该数据和它前后数据之间的关联性。

总的来说，关联式容器存放的数据不同，而且数据前后有一点的关联性。

⚡键对值

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

比如：现在要建立一个英汉互译的字典，那字典中就得右英文单词和与之对应的中文含义，而且它们的关系是一一对应的，此时用就可以使用键对值来存放，如<单词，汉语>。

在STL中，定义了一个键对值的类：

这个类的名字叫做pair，是一个模板类，可以存放任意类型的键对值，而且能够自定推演。它的成员变量右两个，分别是first和second，结构如：<first,second>。它也右自己的默认成员函数，和普通成员函数。

伪代码形式：

template <class T1, class T2>struct pair{typedef T1 first_type;typedef T2 seco_type;T1 first;T2 second;pair():first(T1()),second(T2()){}pair(const T1& a, const T2& b):first(a),second(b){}};

键对值注定是要在类外进行访问的，所以使用struct而不用class。

make_pair():

该函数是用来制作一个pair类型的匿名对象的:

pair<string, string>("string", "字符串");make_pair("string", "字符串");

上面俩句代码是等价的，都是在创建一个pair类型的匿名对象，让你选择你会选择哪种方式呢？

make_pair()是为了让我们更加方便的使用键值对。

?set

set和之前学习的容器一样，也是一个模板类，但是它的底层是关联式容器，也就是二叉搜索树，并且有很多的成员函数，这些接口相信大家大部分都不陌生。

set存放的数据只有一个，就是它本身。

⚡构造函数

构造函数有三个，分别是默认构造函数、使用迭代器区间的构造函数、拷贝构造函数。

因为底层是二叉搜索树，所有就会涉及到比较，构造函数参数就是比较方式，是一个仿函数，但是默认情况下是有缺省值的。

使用默认构造函数构造出来的s1是空的，里面什么都没有。使用迭代器区间构造出来的s2，里面是这段区间中的数据。拷贝构造函数构造出来的s3，内容和s2的完全一样。

set的去重功能：

上面使用迭代器区间构造s2的时候，原本的数组中有很多个1，但是构造出来的set中，只有一1。

set具有降重的功能，当插入的数据已经存在时就不会再插入，这一点在二叉搜索树中就讲解过。

可以看到，数组中有多个重复数字，用这些数字构造出来的set，里面每个数字只存在一个，重复的都被去除了。

迭代器的中序移动：

在打印set中的数据时，我们发现打印出来的结果是升序的，在学习二叉搜索树的时候我们知道，采用中序遍历的方式打印出来的结果就是升序的。

迭代器++时，移动的顺序就是中序遍历的顺序，所以使用迭代器遍历时得到的结果和中序遍历是一样的。

⚡增删查改

insert():

插入函数insert有3个重载函数，其中第一个是插入一个数据，并且返回一个键对值，第二个是指定位置插入，返回插入的位置，第三个是插入一段迭代器区间。

在set中插入原本没有的数据50，插入成功，返回键对值中，迭代器指向新插入的位置，布尔值是1。在set中插入原本就存在的数据5，插入石板，返回键对值中，迭代器指向set中5的位置，布尔值是0。

强烈不建议使用指定位置插入。

指定位置向set中插入数据，有可能会破环二叉搜索的结构，除非在插入之前能够确定不会破坏结构。一般情况下我们都不会指定位置插入。

迭代器区间中的数据全部插入到了set中。 set中原本就存在5，所以迭代器区间中的5不会再插入。

find():

根据指定的值在set中插入，如果存在则返回该值所在位置的迭代器，如果不存在，则返回set的结束位置的迭代器end()。

5存在于set中，返回该位置的迭代器。 50不存在于set中，返回set的end迭代器。

还有一个接口函数可以代替find，该结构名为count()：

返回指定数据的个数，如果不存在则返回0。

由于set具有降重功能，里面不会存在重复的数据，所以它在这里的功能是和find一样的，只是不过返回的是数字，而不是迭代器。

存在时返回值是1，不存在时返回值是0。

erase():

有三个重载函数，第一个删除指定迭代器位置的值，第二个返回删除指定值的个数，第三个删除迭代器区间中所有数据。

第二个重载函数，由于set中没有重复值，所以返回的值就是1。

使用指定迭代器位置的erase时，需要先使用find找到。使用指定数据的erase时，删除成功返回1，如果不存在则返回0。使用迭代器区间的erase时，将区间内的数据全部删除。迭代器区间用的是set的迭代器区间。

修改：

在二叉搜索树的时候本喵就说过，不支持修改，因为很有可能会破环树的结构，同样的set也不支持修改。

获取上下边界:

下边界给的数据是2时，返回的就是2的迭代器。上边界给的数据是7时，返回的是8的迭代器，也就是返回7的下一个数据所在位置的迭代器，因为C++中的迭代器都是左闭右开区间的。上边界给的数据是5时，返回的是6的迭代器，因为5不存在，所以返回它下一个数据的迭代器。 lower_boubder(val):返回的iterator >= val所在的位置的迭代器。upper_bounder(val):返回的iterator > val所在的位置迭代器。

但是这两个接口用的非常少，仅了解就可以。

其他成员函数的使用，包括迭代器，我们在学习vector，list等容器时已经用的炉火纯青了，本喵就不再介绍了，还有一些很不常用的接口，再以后用到的时候再详细介绍。

?multiset

multiset和set在同一个头文件中，而且几乎是一模一样的。

区别在于multiset支持数据重复，而set不可以。

重复数据仍然可以插入到multiset中。 set：排序 + 降重multiset：排序(不降重)

count()：

在set中count成员函数和find功能类似，但是在multiset中它就有了它的作用。

mutiset中有3个5，返回就是3。 multiset中没有50，返回就是0。

erase():

erase中的第二个重载函数也是给multiset使用的。

mutiset中有2个3，全部被删除，所以返回值就是2。 mutiset中没有30，所以返回值就是0。

find():

使用find查找multiset中的重复元素时，返回的是哪个呢？

find找到的是中序遍历的第一个3。

multiset其他方面和set一模一样，本喵就不再介绍了。

?map

map和set一样，也是一个关联式容器，底层是二叉搜索树。

map中存放的是键对值，如上图所示，有两个模板参数，这两个参数组成一对键对值。

⚡构造函数

没有使用一个键对值进行构造的构造函数，只有一个键对值时，只能先创建在使用insert插入。

使用默认构造函数创建的map是空的。插入键对值时，使用make_pair创建匿名对象更加方便。

使用迭代器区间进行初始化。拷贝构造初始化。

特性：

map具有降重功能，和set一样。不能插入相同的键值对，和set一样，map不支持重复数据。不能插入key值相同，val值不同的键值对。 map中虽然存放的是键值对，但是它的判断逻辑都只看key值，也就是first所表示的变量。

map也具有排序 + 降重的功能，依据只看key值而不管value值。

⚡增删查改

insert():

用法和set中的一样，只是map插入的是键值对。

插入一个键值对时，返回的也是一个键值对，返回的键值对中，first是插入键值对所在位置的迭代器，second是bool值，成功就返回1，失败就返回0。迭代器区间插入时，map已经有的元素就不再插入了。

同样强烈不建议使用指定位置插入。

find():

查找时，只需要指定要查找键值对中的键值key就可以，find是根据key去搜索的。查找到以后返回键值对所在位置，没有找到返回end迭代器。

键值4存在，它的value值是李四，所以通过返回的迭代器可以找到。键值5不存在，所以返回map的end迭代器。

erase():

和set中的使用情况一样，除了指定迭代器位置和迭代器区间外，只需要指定键值key就可以删除对应的键值对。

map和set一样，不支持修改，因为可能会破坏二叉搜索树的结构。

除了插入这样的增加操作时，需要一个键值对，其他操作都是根据键值对中的键值key来处理的。

⚡operator[]

现在使用map来统计KV模型例子中水果的个数：

void TestMap6(){string arr[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };map<string, int> countMap;for (auto& e : arr){map<string, int>::iterator it = countMap.find(e);//map没有该水果，插入，数量为1if (it == countMap.end()){countMap.insert(make_pair(e,1));}//map中有该水果，数量加1else{it->second++;}}//查看mapfor (auto& e : countMap){cout << e.first << ":" << e.second << endl;}cout << endl;}

成功统计出了水果的个数，此时水果名是key值，数量是value值。

还有一种非常不可思议的方式：

原本那么一大堆的判断逻辑，此时一句代码就搞定了。

要想知道原因，就必须了解operator[]成员函数。

键对值中的key值充当下标。

文档中解释，调用operator[]相当于在调用上面那一句代码。可以看到这句代码非常长，得需要好好分析。

这句代码可以这样解释，但是还是有些复杂。

Value& operator[](const K& key){//1.插入2.查找pair<map<K, Value>::iterator, bool> ret = insert(make_pair(key, Value()));//3.修改return ret.first->second;}

插入：使用insert进行了插入。查找：插入后返回的键对值中有布尔类型，插入就返回true，否则返回false。修改：最终的返回值是插入键对值中的value。

一个operator[]可以实现3个功能，所以可以代替最开始那一堆逻辑。

countMap[e]++;

这句代码是如何实现插入，查找，修改三个功能呢？

首先：insert(e)，map中如果不存在e，则插入，返回e的second的引用，也就是计数值。如果存在e，则不插入，直接返回e的second的引用。如果是新插入的e，此时e的second的引用是0，加加后变成了1。如果不是新插入的，对e的second的引用进行加加，数量也就被加加了。这里只是用到了operator[]的插入和修改功能，没有使用到查找。