【C++：map和set的使用】C++ map/multimap完全指南：从红黑树原理入门到高频算法实战
🔥艾莉丝努力练剑：个人主页
❄专栏传送门：《C语言》、《数据结构与算法》、C/C++干货分享&学习过程记录、Linux操作系统编程详解、笔试/面试常见算法：从基础到进阶、测试开发要点全知道
⭐️为天地立心，为生民立命，为往圣继绝学，为万世开太平
🎬艾莉丝的简介：
🎬艾莉丝的C++专栏简介：
目录
C++的两个参考文档
老朋友（非官方文档）：cplusplus
官方文档（同步更新）：cppreference
map和multimap的参考文档：map、multimap
5 ~> 了解map容器
5.1 map与 multimap 概述
map和multimap是C++STL中常用的关联容器，底层基于红黑树实现，支持高效的查找、插入和删除操作。
5.2 map
map的参考文档：map
5.3 multimap
multimap的参考文档：multimap
5.4 map类的介绍
map的声明如下，Key就是map底层关键字的类型，T是map底层value的类型，set默认要求Key支持小于比较，如果不支持或者需要的话可以自行实现仿函数传给第二个模版参数，map底层存储数据的内存是从空间配置器申请的。一般情况下，我们都不需要传后两个模版参数。map底层是用红黑树实现，增删查改效率是O（logN），迭代器遍历是走的中序，所以是按key有序顺序遍历的。
两条直线相交，其中一条直线上有一个点A，过点A作与另一条直线的垂线，焦点是B——
A点和直线上的B也可以是成映射关系。
template < class Key, // map::key_type class T, // map::mapped_type class Compare = less<Key>, // map::key_compare class Alloc = allocator<pair<const Key, T> > // map::allocator_type > class map;5.5 pair类型介绍
map底层的红黑树节点中的数据，使用pair<Key，T>存储键值对数据。
typedef pair<const Key, T> value_type; 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 U, class V> pair(const pair<U, V>& pr) : first(pr.first), second(pr.second) {} }; template <class T1, class T2> inline pair<T1, T2> make_pair(T1 x, T2 y) { return (pair<T1, T2>(x, y)); }5.6 map和multimap的底层原理浅解
5.6.1 底层原理
map和multimap底层使用红黑树（平衡二叉搜索树）实现。
5.6.2 键不可修改（key），值可修改（value）
typedef std::pair<const Key, T> value_type;6 ~> map使用层详解
6.1 增删查
map增接口，插入的pair键值对数据，跟set所有不同，但是查和删的接口只用关键字key跟set是完全类似的，不过find返回iterator，不仅仅可以确认key在不在，还找到key映射的value，同时通过迭代还可以修改value。
6.1.1 insert
上面是C++98标准的插入操作，下面是C++11的插入操作。
6.1.2 map的构造
map对象的构造——
6.1.3 map：C++98的插入操作
插入操作的多种方式——
C++98风格的插入 —— 构造pair对象插入：
6.1.4 map：C++11的插入操作
C++11风格的插入 —— 使用初始化列表：
6.1.5 map的key唯一性
这个插入会失败，因为“left”已存在，所以不会再插入。
6.1.6 遍历方式：迭代器遍历
再举个例子——
for (auto it = dict.begin(); it != dict.end(); ++it) { std::cout << it->first << ": " << it->second << std::endl; }6.1.7 C++11：范围for
6.1.8 C++17：结构化绑定
6.1.9 查找操作：find
6.1.10 查：find
auto it = dict.find("key"); if (it != dict.end()) { // 找到 }6.1.11 at
6.1.12 count
// 查找k，返回k所在的迭代器，没有找到返回end() iterator find (const key_type& k); // 查找k，返回k的个数 size_type count (const key_type& k) const;6.1.13 删除（用范围for遍历显示结果）：erase
auto pos = dict.find("left"); if (pos != dict.end()) { dict.erase(pos); }也可直接通过键删除——
dict.erase("left");6.1.14 博主手记
6.2 以字典dict为例，展示词频统计的两种实现方式
6.2.1 查找 + 插入
// 查找 + 插入组合 map<string, int> countMap; for (auto& e : arr) { auto it = countMap.find(e); if (it != countMap.end()) { it->second++; // 存在则递增 } else { countMap.insert({ e,1 }); // 不存在则插入 } }存在时直接通过迭代器修改value（second），不存在时使用insert插入新的pair。
6.2.2 利用operator[ ]搞定dict查找
// 利用 operator[] 的特性 for (auto e : arr) { countMap[e]++; }
6.3 map和multimap的差异
multimap和map的使用基本完全类似，主要区别点在于multimap支持关键值key冗余，那么insert / find / count / erase都围绕着支持关键值key冗余有所差异，这里跟set和multiset完全一样，比如find时，有多个key，返回中序第一个。其次就是multimap不支持[]，因为支持key冗余，[ ]就只能支持插入了，不能支持修改。
6.4 map的数据修改
前面艾莉丝提到map支持修改mapped_type数据，不支持修改key数据，修改关键字数据，破坏了底层搜索树的结构。map第一个支持修改的方式时通过迭代器，迭代器遍历时或者find返回key所在的iterator修改，map还有一个非常重要的修改接口operator[]，但是operator[]不仅仅支持修改，还支持插入数据和查找数据，所以他是一个多功能复合接口需要注意从内部实现角度，map这里把我们传统说的value值，给的是T类型，typedef为mapped_type。而value_type是红黑树结点中存储的pair键值对值。日常使用中，我们还是习惯将这里的T映射值叫做value。
Member types key_type->The first template parameter(Key) mapped_type->The second template parameter(T) value_type->pair<const key_type, mapped_type> // 查找k，返回k所在的迭代器，没有找到返回end()， // 如果找到了通过iterator可以修改key对应的mapped_type值 iterator find(const key_type& k); // 文档中对insert返回值的说明 // The single element versions (1) return a pair, with its member pair::first //set to an iterator pointing to either the newly inserted element or to the //element with an equivalent key in the map.The pair::second element in the pair //is set to true if a new element was inserted or false if an equivalent key //already existed. // insert插⼊⼀个pair<key, T>对象 // 1、如果key已经在map中，插⼊失败，则返回⼀个pair<iterator,bool>对象， // 返回pair对象first是key所在结点的迭代器，second是false // 2、如果key不在在map中，插⼊成功，则返回⼀个pair<iterator,bool>对象， // 返回pair对象first是新插⼊key所在结点的迭代器，second是true // 也就是说无论插入成功还是失败，返回pair<iterator,bool>对象的first都会指向key所在的迭代器 // 那么也就意味着insert插⼊失败时充当了查找的功能，正是因为这⼀点，insert可以⽤来实现 operator[] // 需要注意的是这⾥有两个pair，不要混淆了，⼀个是map底层红⿊树节点中存的pair<key, T>， // 另⼀个是insert返回值pair<iterator, bool> pair<iterator, bool> insert(const value_type& val); mapped_type& operator[] (const key_type& k); // operator的内部实现 mapped_type& operator[] (const key_type& k) { // 1、如果k不在map中，insert会插⼊k和mapped_type默认值， // 同时[]返回结点中存储mapped_type值的引⽤，那么我们可以通过引用修改返映射值。所以[]具备了插入 + 修改功能 // 2、如果k在map中，insert会插⼊失败，但是insert返回pair对象的first是指向key结点的迭代器， // 返回值同时[]返回结点中存储mapped_type值的引用，所以[]具备了查找 + 修改的功能 pair<iterator, bool> ret = insert({ k, mapped_type() }); iterator it = ret.first; return it->second; }6.5 operator[ ]（重点）
文档链接：operator[]
6.5.1 插入默认值
// 插入 dict["sort"]; // 插入 {"sort", ""}，string 默认构造为空字符串6.5.2 插入 + 修改
// 插入 + 修改 dict["left"] = "左边"; // 插入 {"left", "左边"}6.5.3 修改已存在的值
// 查找 cout << dict["sort"] << endl; // 修改已存在的 key 的 value6.5.4 查找
// 查找 cout << dict["sort"] << endl; // 如果不存在会插入空字符串！6.6 at()
6.6.1 修改存在的 key
dict.at("left") = "xxxxxxxxxx"; // 安全修改6.6.2 访问不存在的 key（抛异常）
// dict.at("insert") = "xxxxxxxxxx"; // 抛出 std::out_of_range 异常
6.7 对比：operator[ ] VS at( )
| 特性 | operator[] | at() |
|---|---|---|
| key 不存在时 | 自动插入默认值 | 抛出 std::out_of_range 异常 |
| 返回值 | value 的引用 | value 的引用 |
| 使用场景 | 需要自动插入的场景 | 确保 key 存在的安全访问 |
| 性能 | 稍快（无异常检查） | 稍慢（有边界检查） |
7 ~> map算法题实战
7.1 随机链表的复制
力扣链接：138. 随机链表的复制
力扣题解链接：原链表基础上拷贝节点、置random指针、断开新旧链表解决随机链表的复制
题目描述：
7.1.1 图解题给示例
数据结构初阶阶段，为了控制随机指针，我们将拷贝结点链接在原节点的后面解决，后面拷贝节点还得解下来链接，非常麻烦。这里我们直接让{原结点，拷贝结点}建立映射关系放到map中，控制随机指针会非常简单方便，这里体现了map在解决一些问题时的价值，完全是降维打击。
7.1.2 算法实现
/* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val = _val; next = NULL; random = NULL; } }; */ class Solution { public: Node* copyRandomList(Node* head) { map<Node*,Node*> nodeMap; Node* copyhead =nullptr,*copytail = nullptr; Node* cur= head; while(cur) { Node* copy=new Node(cur->val); // 尾随 if(copytail == nullptr) { copyhead = copytail=copy; } else { copytail->next=copy; copytail=copy; } nodeMap.insert({cur,copy}); cur=cur->next; } cur = head; Node* copy = copyhead; while(cur) { if(cur->random == nullptr) { copy->random = nullptr; } else { copy->random = nodeMap[cur->random]; } cur = cur->next; copy = copy->next; } return copyhead; } };时间复杂度：O(n)，空间复杂度：O(n)。
7.1.3 博主手记
本题整个的思路、算法原理、解题过程博主在纸上推导了一遍，大家可以参考一下手记的推导过程！最好做题的过程中自己也推导一遍！！！自己能够推导很重要！
7.2 前K个高频单词
力扣链接：692. 前K个高频单词
力扣题解链接：三种写法解决【前K个高频单词】
题目描述：
7.2.1 题目理解
本题目我们利用map统计出次数以后，返回的答案应该按单词出现频率由高到低排序，有一个特殊要求，如果不同的单词有相同出现频率，按字典顺序排序。
7.2.2 算法实现
7.2.2.1 写法1
用排序找前k个单词，因为map中已经对key单词排序过，也就意味着遍历map时，次数相同的单词，字典序小的在前面，字典序大的在后面。那么我们将数据放到vector中用一个稳定的排序就可以实现上面特殊要求，但是sort底层是快排，是不稳定的，所以我们要用stable_sort，他是稳定的。
// 方法1 class Solution { public: struct kv_pair { bool operator()(const pair<string, int>& kv1,const pair<string, int> kv2) { return kv1.second > kv2.second; } }; vector<string> topKFrequent(vector<string>& words, int k) { map<string, int> countMap; for(auto& str : words) { countMap[str]++; } // multimap<int,string> sortMap; // 降序 vector<pair<string, int>> v(countMap.begin(), countMap.end()); // sort(v.begin(),v.end(),kv_pair()); // 稳定的排序 stable_sort(v.begin(), v.end(), kv_pair()); for (auto& [k, v] : v) { cout << k << ":" << v << endl; } cout << endl; vector<string> ret; for (size_t i = 0; i < k; ++i) { ret.push_back(v[i].first); } return ret; } };时间复杂度：O(nlogn)，空间复杂度：O(n)。
7.2.2.2 写法2
自己实现一个仿函数，控制比较逻辑。
将map统计出的次数的数据放到vector中排序，或者放到priority_queue中来选出前k个。利用仿函数强行控制次数相等的，字典序小的在前面。
次数大的在前面，次数相等的、字典序小的在前面——
// 方法2 class Solution { public: // 自己实现一个仿函数，控制比较逻辑 struct kv_pair { // 次数大的在前面，次数相等的、字典序小的在前面 bool operator()(const pair<string,int>& kv1,const pair<string,int>& kv2) { return kv1.second > kv2.second; || (kv1.second == kv2.second && kv1.first < kv2.first); } }; vector<string> topKFrequent(vector<string>& words, int k) { for(auto& str : words) { countMap[str]++; } // multimap<int,string> sortMap; // 降序 vector<pair<string,int>> v(countMap.begin(),countMap.end()); sort(v.begin(),v.end(),kv_pair); for(auto& [k,v] : v) { cout<< k << ":" << v << endl; } cout << endl; vector<string> ret; for(size_t i = 0;i < k;++i) { ret.push_back(v[i].first); } return ret; } };时间复杂度：O(nlogn)，空间复杂度：O(n)。
7.2.2.3 写法3
使用优先级队列，大堆提供的小于的比较逻辑。
次数大的在前面，次数相等的，字典序小的在前面——
// 方法3 class Solution { public: struct kv_pair{ // 次数大的在前面，次数相等的，字典序小的在前面 // 优先级队列，大堆提供的小于的比较逻辑 bool operator()(const pair<string,int>& kv1,const pair<string,int>& kv2) { return kv1.second < kv2.second || (kv1.second == kv2.second && kv1.first > kv2.first); } }; vector<string> topKFrequent(vector<string>& words, int k) { map<string,int> countMap; for(auto& str : words) { countMap[str]++; } // 大堆 priority_queue<pair<string,int>,vector<pair<string,int>>, kv_pair> pq(countMap.begin(),countMap.end()); vector<string> ret; for(size_t i = 0;i < k;++i) { ret.push_back(pq.top().first); pq.pop(); } return ret; } };时间复杂度：O(nlogn)，空间复杂度：O(n)。
8 ~> 本文博主手记
下面这里博主手记的墨水旋开了，uu们先凑合凑合看一下，内容和本文大体一致——
完整代码示例与实践演示
Test.cpp：
#define _CRT_SECURE_NO_WARNINGS 1 #include<iostream> #include<map> #include<string> using namespace std; void Test_map1() { map<string, string> dict; // C++98 pair<string, string> kv1("sort", "排序"); dict.insert(kv1); dict.insert(pair<string, string>("left", "左边")); dict.insert(make_pair("pair", "左边")); // C++11 dict.insert({ "right","右边" }); //dict.insert({ kv1,pair<string,string>("left","左边") }); dict.insert({ { "string","字符串" }, { "map","地图,映射" } }); // key相同就不会再插入，value不相同也不会插入 dict.insert({ "left","左边xxxx" }); map<string, string>::iterator it = dict.begin(); while (it != dict.end()) { //cout << (*it).first << ":" << (*it).second << endl; cout << it->first << ":" << it->second << endl; //cout << it.operator->()first << ":" << it.operator->()second << endl; ++it; } cout << endl; for (auto& e : dict) { cout << e.first << ":" << e.second << endl; } cout << endl; // 结构化绑定 C++17 auto [x, y] = kv1; // 使用结构化绑定遍历 //for (auto [k, v] : dict) //for (auto& [k, v] : dict) for (const auto& [k, v] : dict) { cout << k << ":" << v << endl; } cout << endl; // 查找和删除 auto pos = dict.find("left"); if (pos != dict.end()) { dict.erase(pos); } // 再次遍历显示结果 for (const auto& [k, v] : dict) { cout << k << ":" << v << endl; } cout << endl; } void Test_map2() { string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" }; map<string, int> countMap; for (auto& e : arr) { auto it = countMap.find(e); if (it != countMap.end()) { it->second++; } else { countMap.insert({ e,1 }); } countMap[e]++; } for (auto e : arr) { countMap[e]++; } for (auto& [k, v] : countMap) { cout << k << ":" << v << endl; } cout << endl; map<string, string> dict; // 插入 dict["sort"]; // 插入 + 修改 dict["left"] = "左边"; // 修改 dict["sort"] = "排序"; // 查找 cout << dict["sort"] << endl; // 纯粹的查找 + 修改 // at dict.at("left") = "xxxxxxxxxx"; // key不存在，会抛异常 dict.at("insert") = "xxxxxxxxxx"; //报错 // 0x00007FF9E4CE837A处(位于 map的使用.exe 中) // 有未经处理的异常: Microsoft C++ // 异常 : std::out_of_range（抛异常），位于内存位置 0x000000279D0FEBE0处。 } void Test_map3() { multimap<string, string>dict; dict.insert({ "right","右边" }); dict.insert({ "left","左边" }); dict.insert({ "right","右边xxx" }); dict.insert({ "right","右边" }); for (const auto& [k, v] : dict) { cout << k << ":" << v << endl; } cout << endl; } int main() { Test_map1(); //Test_map2(); //Test_map3(); return 0; }运行演示
Test_map1()
Test_map2()
Test_map3()
结尾
往期回顾：
【C++：map和set的使用】C++STL容器详解：set容器从使用到高频算法题实战
结语：都看到这里啦！那请大佬不要忘记给博主来个“一键四连”哦！
🗡博主在这里放了一只小狗，大家看完了摸摸小狗放松一下吧！🗡
૮₍ ˶ ˊ ᴥ ˋ˶₎ა
