C++_STL_map与set

1. 关联式容器

在初阶阶段，我们已经接触过STL中的部分容器，比如：vector、list、deque、 forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面 存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别？

关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是结构的 键值对，在数据检索时比序列式容器效率更高。

2. 键值对

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代 表键值，value表示与key对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中必然 有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应 该单词，在词典中就可以找到与其对应的中文含义。

3. 树形结构的关联式容器

根据应用场景的不桶，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。树型结 构的关联式容器主要有四种：map、set、multimap、multiset。

这四种容器的共同点是：使 用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。下面一依次介绍每一 个容器。

3.1  set

set - C++ Reference

翻译：

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

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

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

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

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

注意：

1. 与map/multimap不同，map/multimap中存储的是真正的键值对，set中只放 value，但在底层实际存放的是由构成的键值对。

2. set中插入元素时，只需要插入value即可，不需要构造键值对。

3. set中的元素不可以重复(因此可以使用set进行去重)。

4. 使用set的迭代器遍历set中的元素，可以得到有序序列

5. set中的元素默认按照小于来比较

6. set中查找某个元素，时间复杂度为：log_2 n

 7. set中的元素不允许修改(为什么?)

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

关于set的使用就不多说了关键看一些我们之前没见到的接口

set的拷贝代价很大但是搜索的代价很小

同时要注意这个lower_bound 和upper_bound   这两个接口

这里是找这两个区间的值

lower_bound(20)->就是找大于等于key = 25的节点

upper_bound(50)->就是找key>50的这个节点

这样形成一个左闭右开的结构，才可以将我们给的区间里面的东西删除完（迭代器里面的所有操作几乎都是左闭右开的）

而这个count 和equal_range对于met是没有什么意义的，应为set不允许重复，但是对于下面的multiset就很有意义了

3.2multiset

multiple:多样的，其实这个multiset就是可以存储重复的数据

multiset介绍multiset - C++ Reference

具体使用：

void Test_mutiset()
{int arr[] = { 2,4,5,6,7,843,2,4,5,7,9 ,11,45 };multiset<int> s1(arr, arr + (sizeof(arr) / sizeof(int)));for (const auto& e : s1){cout << e << " ";}cout << endl;//find查找（重复数据）返回中序的第一个multiset<int>::iterator it = s1.find(4);while (it != s1.end()){cout << *it << " ";++it;}cout << endl;cout << s1.count(2) << endl;pair<multiset<int>::iterator, multiset<int>::iterator> eq = s1.equal_range(2);while (eq.first != eq.second){cout << *(eq.first) << " ";++eq.first;}cout << endl;}

这里的equal_range返回的是一个pair，我们一般用auto来接收，要不然要写一大堆 

3.3map

讲之前先学习一下pair

pair - C++ Reference

这个pair其实就是一个类（我们也喜欢叫键值对），里面有first和second两个位置可以存储数据，这就方便了，在key_value

（map）里面我们就把这两个放到pair里面，这样对于一个函数返回的时候返回一个pair也方便

map - C++ Reference

翻译：

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

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

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

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

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

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

map的插入就比较繁琐，（单参数才能接受隐式类型转化）

void Test_map()
{map<string,string> dict;//插入的方法pair<string, string> p1("insert", "插入");dict.insert(p1);dict.insert(pair<string,string>("right", "右边"));dict.insert(make_pair("sort", "排序"));dict.insert({ "queue","队列" });auto it = dict.begin();while (it != dict.end()){//pair没有重载*所以打印的时候就访问first,second//cout << (*it).first << ":" <<(*it).second << endl;cout << it->first  << ":" << it->second << endl;++it;}cout << endl;
}

第三种也是比较常用的这个就是一个库里面的一个函数，方便构造

最后一种插入方法其实就是隐式类型转换

这里是c++11支持的，而c++98不支持

要注意：map和set里面的key都不能修改，因为改了话就改变了搜索树的结构

set:直接将迭代器全搞为const迭代器，但是map不敢这样搞，因为map要允许修改value

map:用pair来存（类模板）数据。

map的这个重载括号非常有用

【总结】

1. map中的的元素是键值对

2. map中的key是唯一的，并且不能修改

3. 默认按照小于的方式对key进行比较

4. map中的元素如果用迭代器去遍历，可以得到一个有序的序列

5. map的底层为平衡搜索树(红黑树)，查找效率比较高O(log N)

6. 支持[]操作符，operator[]中实际进行插入查找。

3.4multimap

multimap - C++ Reference

而这个multimap的插入就不会返回pair，显然也没有重载[]，因为key可以重复，你如果还能返回

引用，返回的是谁的引用呢？（有很多数据冗余的）

3.5改进之前做的题

20. 有效的括号 - 力扣（LeetCode）

class Solution {
public:bool isValid(string s) {stack<char> st;map<char,char> matchMap;matchMap['('] = ')';matchMap['{'] = '}';matchMap['['] = ']';for(auto ch:s){if(matchMap.count(ch)){st.push(ch);}else{if(st.empty()){return false;}if(matchMap[st.top()]==ch){st.pop();           }elsereturn false;}}if(st.empty()){return true;}elsereturn false;}
};

这样就可以很方便控制比较逻辑 

138. 随机链表的复制 - 力扣（LeetCode）

之前我们用c语言写过

c语言的思路：

1拷贝节点链接到原链表的后面

2拷贝节点的random是源节点random指向的节点

3拷贝节点解下来 链接成一个新的链表 原链表恢复

之前就是先处理random指针，通过将拷贝节点放到原节点后面，就可以知道原节点random指针指向的节点的下一个就是拷贝节点random指向的那一个

有了map我们可以将Node*用map存起来

就是用一个map存节点（k）和拷贝节点(v)

那么k->random ==v->random，就可以链接上了

这一步很妙（k->random在map里面肯定可以找到拷贝节点的random）

class Solution {
public:Node* copyRandomList(Node* head) {//拷贝节点map<Node*,Node*> matchMap;Node* copyhead=nullptr;Node* copytail=nullptr;Node* cur = head;while(cur){if(copyhead==nullptr){copyhead = copytail = new Node(cur->val);}else{copytail->next = new Node(cur->val);copytail = copytail->next;}matchMap[cur]=copytail;cur = cur->next;}//处理randomcur = head;Node* copy = copyhead;while(cur){if(cur->random ==nullptr){copy->random = nullptr;}else{copy->random = matchMap[cur->random];}cur = cur->next;copy = copy->next;}return copyhead;}};

代码量大大减少！

349. 两个数组的交集 - 力扣（LeetCode）

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {set<int> s1(nums1.begin(),nums1.end());set<int> s2(nums2.begin(),nums2.end());vector<int> v1,v2;vector<int> ret;for(const auto& e:s1){v1.push_back(e);}for(const auto& e:s2){v2.push_back(e);}size_t c1 = 0;size_t c2 = 0;while(c1!=v1.size() && c2!=v2.size()){if(v1[c1]<v2[c2]){c1++;}else if(v1[c1]>v2[c2]){c2++;}else{ret.push_back(v1[c1]);c1++;c2++;}}return ret;}
};

同时还可以求两个数组的交  差  并  原理都是一样的 

692. 前K个高频单词 - 力扣（LeetCode）

这题一看就是两个排序，一个是频率一个是字典序

1 用优先级队列

2我们用map，k为字典，v为次数，全部入map后，k为唯一的

（1）我们将数据导出来

sort 不能对map排序，因为map不是随机迭代器（快排里面有三数取中）

（2）数据导出来之后，string是按照字典序排序的 （map中序导出来（注意导出来的是pair））这时候就用sort去按照频率排序,当然pair里面重载了比较但是他是先比较first的大小再比较second的大小，且升降序是一样的，这样就与我们的要求不同了，我们希望频率是降序，string是升序，而且先比较频率（second）那么我们可以用仿函数自己控制比较逻辑

还有一点，这里涉及排序的稳定性的问题，就是排序后改不改变其他元素的相对顺序，从之前快排的实现我们可以知道，快排是不稳定的，那么排序后就会改变string的相对顺序，这里库里面提供了一个稳定的stable_sort，这个是稳定的可以用

或者我们可以想一个其他的方法

class Solution {
public:struct Greater{//这里我们控制sort的比较逻辑bool operator()(const pair<string,int>& p1,const pair<string,int>& p2){return p1.second>p2.second ||(p1.second==p2.second && p1.first<p2.first);}};vector<string> topKFrequent(vector<string>& words, int k) {map<string,int> countMap;for(const auto& e:words){countMap[e]++;} vector<pair<string,int>> v1;for(const auto &e: countMap){v1.push_back(e);}stable_sort(v1.begin(),v1.end(),Greater());这里注意，我们已经控制比较逻辑，可以用不稳定的sortvector<string> v2;for(size_t i = 0;i<k;i++){v2.push_back(v1[i].first);}return v2;}
};