【C++】map、set、multimap、multiset的介绍和使用

我讨厌世俗，也耐得住孤独。

---

---

一、键值对

1.
之前所学的vector，list，deque等容器都是序列式容器，因为他们的底层数据结构都是线性的，并且数据结构中存储的都是元素数据本身，也就是单一的变量。
而下面所学的set、map、multimap、multiset等容器都是关联式容器，他们内部存储的不再是单一的元素数据，存储的而是<key,value>的键值对，由于每个键值对之间都有关联，所以其结构天生就具有优势，在数据检索时效率要比序列式容器高的多。

2.
那什么是键值对呢？键值对实际也是一个类，类里面对key和value数据进行了封装，key表示关键码，value表示与之对应的值，下面是SGI对于pair键值对结构体的定义：

3.
struct pair{}有两个构造函数，一个是无参的利用T1和T2类型的默认构造函数初始化出来的键值对，一个是T1和T2作为参数的构造函数。
另外pair还重载了两个运算符，用于键值对的等于和小于比较，小于比较时，优先比较first，如果first恰好满足x<y，则返回true。如果first之间相等，则比较失败返回false。如果first是x>y，那就继续比较second。
为了方便构造键值对，pair又另写了成员函数make_pair()，这个函数其实也是调用了构造函数，但在构造键值对的时候，省下我们自己去传T1和T2的类型了就。

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 T1, class T2>
inline bool operator==(const pair<T1, T2>& x, const pair<T1, T2>& y) { return x.first == y.first && x.second == y.second; 
}template <class T1, class T2>
inline bool operator<(const pair<T1, T2>& x, const pair<T1, T2>& y) { return x.first < y.first || (!(y.first < x.first) && x.second < y.second); 
}template <class T1, class T2>
inline pair<T1, T2> make_pair(const T1& x, const T2& y) {return pair<T1, T2>(x, y);
}

二、树形结构的关联式容器

根据应用场景的不同，STL总共实现了两种不同结构的管理式容器，一种是树型结构，一种是哈希结构，树型结构的关联式容器主要分为map、set、multimap、multiset。
这四种容器的共同点是都是用平衡搜索树(红黑树)作为底层结构。

1.set

1.1 set的介绍

1.
在set中，key和value是同时被标识的，所以key就是value，正由于key就是value，所以set容器中的元素不允许被修改，每个元素都被const修饰，只能增insert删erase查find。

2.
set在比较时默认使用缺省的仿函数less< T >，所以一旦比较成功时，较小元素就被插入到左边，较大元素就被插入到右边，那么在中序遍历时，结果自然就是升序结果。如果改为greater< T >，则逻辑就会反过来，中序遍历结果就是降序。

3.
set与map不同的是，map存放的是真正的键值对<key,value>，而set中只放value，但在底层实际存放的是<key,key>的键值对。

4.
set不允许元素被修改，因为这会破坏搜索树的结构。

5.
set中不允许元素有重复，所以set和二叉搜索树比较像，一旦元素重复再进行插入时，情况就较为复杂，需要用到树的旋转等知识，不过multiset可以支持插入的元素重复。
在使用set迭代器进行遍历时，set的迭代器走的是中序遍历的顺序，每一个迭代器都指向对应位置的键值对，当然set容器的元素我们也可以叫做键值对，只不过key和value相等罢了。

6.
由于set中不允许有元素重复，所以将一段数据插入到set时，set所展现的功能是排序+去重。

1.2 set的使用

1.
set的insert有三个重载形式，较为常用的就是直接插入一个值和利用其他容器的迭代器区间构建出set容器。

2.
erase用于删除set中的某个元素，如果删除成功，则返回1，否则返回0，size_type是unsigned int typedef出来的。

3.
find用于查找set中某个元素val，找到就返回键值对对应的迭代器，否则就返回end迭代器。
算法库中也有find，但哪个find的效率明显要低于set类的find，因为一个是类似于二分查找，一个是暴力通过迭代器进行查找，一个是logN，一个是N

void test_set1()
{set<int,greater<int>> s;s.insert(3);s.insert(1);s.insert(4);s.insert(7);s.insert(2);s.insert(1);//set底层是二叉搜索树，当插入相同的值时会返回false，所以set是排序+去重set<int,greater<int>>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;for (auto e : s){cout << e << " ";}cout << endl;//auto pos = s.find(3);auto pos = find(s.begin(), s.end(), 3);//算法库的find其实就是利用迭代器进行查找，找不到就返回end()迭代器//上面这两行代码的查找结果相同，但34行的效率肯定更高一些，因为35行是暴力查找，34行借助搜索树的特性查找高度次//如果是平衡的搜索树，则效率是O(logN)。暴力查找的效率是O(N)，即一个一个迭代器的遍历进行查找。if (pos != s.end()){s.erase(pos);}for (auto e : s){cout << e << " ";}cout << endl;cout << s.erase(10) << endl;//返回0表示没有删除cout << s.erase(1) << endl;//返回1表示删除//上面代码等价于find+erase，删除元素也是要先找再删，找到就删，没找到就直接返回。
}

1.3 multiset的使用

1.
multiset与set的唯一区别就是允许元素重复，其余并没有什么区别，所以用multiset进行排序时，仅仅只能排序，没有去重的效果。
在set中count可能没有什么用，因为每个键值对都只能出现一次，不允许元素重复，但count在multiset中就有用了，可以统计某个key在set中共出现了几次。

#include <set>
void TestSet()
{int array[] = { 2, 1, 3, 9, 6, 0, 5, 8, 4, 7 };// 注意：multiset在底层实际存储的是<int, int>的键值对multiset<int> s(array, array + sizeof(array)/sizeof(array[0]));for (auto& e : s)cout << e << " ";cout << endl;return 0;
}

2.
在set和multiset中都有lower_bound和upper_bound接口，bound是约束束缚的意思，可以用于set中某一上限和下限区间元素的删除，有一说一，这俩接口确实不常用。

2.map

2.1 map的介绍

1.
map存储的是key和value组成的键值对元素结构体，在比较时按照key来进行比较，下面源码我们可以看到key依旧是不允许被修改的，但其对应的value是可以被修改的。

2.
map中比较时比较的是key类型，但我们可以通过key找到value，这里多说一句，无论是map还是set，他们的迭代器走的都是中序的顺序。

2.2 map的使用

1.
map和set都有三个构造函数，其中无参构造函数最为常用，平常在使用map或set时，直接定义其对象即可，无须传参，大多数情况下都是这样。

2.
map和set在插入后都会返回一个键值对：
键值对的first是迭代器，其指向的是新插入键值对，若新插入键值对的key已经存在，则返回已经存在的key对应的键值对的迭代器，这是first的变化规则。
键值对的second是bool值，如果插入的key已经存在，则bool为false，否则bool为true。

3.
map的迭代器访问这里有讲究，由于其迭代器指向的是由key和value组成的键值对，那* it该获得哪个key和value的哪个值呢？set的迭代器指向的就只有key，所以* it直接返回key值即可。
对于map来说，*it拿到的是pair的对象，所以我们还需要再加一个.操作符才能访问pair对象里面的first和second值，但这样写起来有点麻烦，所以map的迭代器也重载了→操作符，→重载的函数会返回迭代器指向对象的地址，所以还应该再加个→访问first或second才对，但是编译器在这里做了优化，省略了一个箭头。（这部分其实在list迭代器那里就说过了，这里正好做一下复习）

4.
在map这里，如果我们用语法糖遍历map时，最好采用const引用，因为map中存的是键值对pair，不用引用就会发生赋值，会调用pair的赋值重载函数，代价比较大，为了提升效率建议采用const引用。（语法糖遍历拿到的值其实就是*it，在map这里就是pair对象，键值对）

int main()
{map<string, string> dict;dict.insert(pair<string, string>("苹果", "apple"));dict.insert(pair<string, string>("鸭梨", "pear"));dict.insert(pair<string, string>("西瓜", "watermelon"));dict.insert(make_pair("草莓", "strawberry"));//make_pair是一个函数模板，内部调用pair的构造函数，但隐式实例化可以减少代码dict["迭代器"] = "iterator";// 插入+修改dict["insert"];// key不在就是插入，value用string的默认构造dict.insert(pair<string, string>("鸭梨", "xxxx"));//这个插入不进去，搜索树的鸭梨已经存在了dict["insert"] = "插入";// insert已经存在，这里表示修改insert的value值cout << dict["insert"] << endl;//key已经存在，这里相当于查找，[]会返回关键码对应的value值，查找时必须确定key已经存在于mapmap<string, string>::iterator it = dict.begin();while (it != dict.end()){//如果结点定义成key和value两个变量，*it都不知道返回谁的值。所以返回pair对象，这样就可以访问两个值了//cout << (*it).first << ":" << (*it).second << endl;cout << it->first << ":" << it->second << endl;//底层是pair封装了value和key，并实现运算符重载it++;}for (const auto& kv : dict)//kv就相当于*it，取到的是map中存储的结构体对象pair//现在的kv已经不像以前一样，仅仅是个内置类型，而是一个结构体对象，结构体的对象进行赋值调用函数代价太大，所以我们用引用{cout << kv.first << ":" << kv.second << endl;}
}

5.
如果用map来统计水果出现的次数，我们采用的思路可以是，如果key不在，那就将键值对插入map，键值对的int初始值设置为1。如果key在，那就把key对应的value值+1，最后语法糖遍历一下map，就可以拿到中序遍历的结果，也就是统计出了水果出现的次数。

6.
另外还有一种非常骚的操作就是利用map的[ ]来统计次数，在前面了解了insert的返回值之后，再来理解map的[ ]调用成本就会低很多了，实际上[ ]带来的作用包括插入，查找，修改的功能，直接一个[ ]运算符重载包揽map的三个重要功能。

7.
拥有这么多功能其实还是因为调用了insert，insert在插入时的键值对的key由我们来传参，而value用其对应类型的匿名构造来代替，所以如果key不存在，那insert就表示插入，如果key已经存在，则[ ]既可以修改，又可以查找。

8.
所以用[ ]可以直接统计出次数，将对应的arr每个元素插入到map里面，如果key存在，则[ ]内部的insert会返回已经存在的key对应的迭代器，通过此迭代器可以拿到value的引用，又因为int类型匿名构造是0，则value初始化是0，++就是1，所以countMap.[e]++就可以直接统计出水果出现的次数。

int main()
{//定义一个map统计水果出现的次数string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" ,"草莓","草莓", "香蕉", "西瓜", };map<string, int> countMap;//for (auto& e : arr)//{//	//map<string, int>::iterator it = countMap.find(e);//	auto it = countMap.find(e);//	if (it == countMap.end())//		countMap.insert(make_pair(e, 1));//	else//		it->second++;//}for (auto& e : arr){countMap[e]++;//  (   *(   (this->insert(make_pair(k, mapped_type()))).first  )   ).second //迭代器指向的是pair类实例化的对象，我们称这个对象为键值对}for (const auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}return 0;
}

9.
注意：在元素访问时，有一个与operator[]类似的操作at()(该函数不常用)函数，都是通过
key找到与key对应的value然后返回其引用，不同的是：当key不存在时，operator[]用默认
value与key构造键值对然后插入，返回该默认value，at()函数直接抛异常。

2.3 multimap的使用

1.
multimap是没有[ ]的，因为multimap支持key值进行重复，那[ ]返回哪个key的引用呢？太乱了吧，所以multimap没有重载[ ]运算符。其余接口的使用和map一样，这里不作介绍。

三、两道OJ题

1.前K个高频单词（less小于号是小的在左面升序，greater大于号是大的在左面降序）

前K个高频单词

1.
我们可以用排序的思路来解决这道题，定义string和int的键值对，然后将所有单词存到map里面，这样map里面就有单词和单词出现的次数的键值对了，并且string还是按照字典顺序排好了。然后我们将键值对利用sort来进行排序，但由于map的迭代器是双向迭代器，而sort要求支持随机访问，因为他底层是快排，那就需要随机迭代器，所以我们将map中的键值对语法糖式的尾插到vector里面，vector的迭代器是随机迭代器，可以适用于快排。

2.
比较vector中的键值对时，快排是不稳定的，当两个单词的出现次数一样时，那在快排比较的时候是有可能打乱两个单词在vector里面出现的顺序的，所以我们可以采取stable_sort进行排序，代码里面写出了错误示范，其实问题不仅仅出现在sort上面，而是出现在pair的比较规则上面去了，所以要想解决问题，还是得从排序的比较规则上面入手，我们重写仿函数，自己定义比较的规则就好了，让这个比较规则契合题目逻辑。

快排的确是不稳定的，这确实没毛病。

3.
sort排序想要正确，他的仿函数逻辑要分两种情况，一种是只有左边键值对的次数大于右边时才可以交换，另一种是关键，因为快排不是不稳定么，那我们就调整逻辑让他稳定，当次数相等时，必须保证second的相对顺序不变，不能随意交换。那就增加条件为：左边的string小于右边的string才返回true。
（这个地方你可以这么理解，因为算法库中默认的less排升序，less里面是小于号，那就是小的在左面，greater排降序，greater里面是大于号，大的在左面，这样理解的话，当次数相同时我们想让字符串小的在左面，那就应该用小于号进行比较，所以仿函数里面second比较那里用小于号）

4.
这里并没有改变sort的稳定性，只是调整了比较的逻辑，如果不控制first相等时的string顺序，那快排就会随意打乱次数相等的单词，但这并不是我们想看到的，所以我们现在强行控制逻辑，不让快排打乱单词的顺序，必须按照字典顺序保证string小的单词在左面。

class Solution {
public:struct compare{bool operator()(const pair<int, string>& left, const pair<int, string>& right){return left.first > right.first || (left.first==right.first && left.second < right.second);//second用小于号比较}};vector<string> topKFrequent(vector<string>& words, int k) {vector<string> ret;map<string, int> mp;for(const auto& str : words){mp[str]++;}vector<pair<int, string>> v;//用vector来排序，map是双向迭代器，不支持随机访问for(const auto& kv : mp){v.push_back(make_pair(kv.second, kv.first));}//第一个是错误写法示例，greater排降序，但pair默认的比较规则不符合题目要求stable_sort(v.begin(), v.end(), greater<pair<int ,string>>);sort(v.begin(), v.end(), compare());for(int i=0; i<k; i++){ret.push_back(v[i].second);}return ret;}
};

5.
下面采用稳定排序的方式进行排序，稳定排序不用考虑first相等时单词有可能被打乱顺序的情况，因为稳定排序不会打乱相等值的相对顺序。

6.
所以仿函数逻辑就是，只有左边的键值对的first大于右边的first（vector中键值对的first是单词出现次数）时，我们才会返回true，进行交换，其他相等或小于的情况都不允许交换，这样就可以保证大的在左面，就能完成降序的工作了。

class Solution {
public:struct compare{bool operator()(pair<int, string> left, pair<int, string> right){return left.first > right.first;}};vector<string> topKFrequent(vector<string>& words, int k) {vector<string> ret;map<string, int> mp;for(const auto& str : words){mp[str]++;}vector<pair<int, string>> v;//用vector来排序，map是双向迭代器，不支持随机访问for(const auto& kv : mp){v.push_back(make_pair(kv.second, kv.first));}stable_sort(v.begin(), v.end(), compare());for(int i=0; i<k; i++){ret.push_back(v[i].second);}return ret;}
};

2.两个数组的交集（排序+去重，简单的比对算法）

两个数组的交集

1.
这道题目就比较简单了，我们可以利用set先进行排序+去重，然后比较两个set里面的值，如果两个值相等时，说明这个值是两个数组的交集，两个迭代器同时往后走，去后面继续比较，如果不相等，那就让较小元素对应的迭代器往后++，因为在小元素的后面才会有可能和另一个set当前的值相等。

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {vector<int> ret;set<int> s1(nums1.begin(), nums1.end());set<int> s2(nums2.begin(), nums2.end());auto it1 = s1.begin();auto it2 = s2.begin();while(it1 != s1.end() && it2 != s2.end()){if(*it1 < *it2){it1++;}else if(*it1 > *it2){it2++;}else{ret.push_back(*it1);it1++;it2++;}}return ret;}
};