小叶-duck个人主页❄️个人专栏《Data-Structure-Learning》《C入门到进阶自我学习过程记录》《算法题讲解指南》--优选算法《算法题讲解指南》--递归、搜索与回溯算法《算法题讲解指南》--动态规划算法✨未择之路不须回头已择之路纵是荆棘遍野亦作花海遨游目录前言一、map 核心原理键值对与红黑树底层1、什么是 map2、关键类型定义二、 map 基础操作构造、遍历与增删查改1、构造与初始化2、迭代器遍历3、插入操作insert4、查找与删除find/erase4.1 查找find 与 count5、核心特性operator [] 的多功能性三. map 与 multimap 的差异四、map 实战LeetCode 经典案例1、随机链表的复制题目链接C算法代码2、前k个高频单词题目链接结束语前言在 C STL 容器中map是兼具“高效查找”与“键值映射”能力的关联式容器底层基于红黑树实现支持 O(log N) 级别的增删查改操作且会按键值Key自动排序。本文将从 map 的核心概念切入结合实操代码详细讲解其构造、增删查改、迭代器遍历等基础操作对比 map 与 multimap 的差异帮你彻底掌握 map 的使用。一、map 核心原理键值对与红黑树底层1、什么是 mapmap 是一种“键值对Key-Value”容器每个元素包含一个不可修改的键Key 和一个可修改的值Value底层通过红黑树平衡二叉搜索树组织数据因此具备两个核心特性键唯一相同的 Key 无法重复插入自动排序遍历 map 时走的中序遍历元素会按 Key 的升序默认用 lessKey 比较排列。map的参考文档map - C Reference2、关键类型定义map 的模板参数与内部类型需重点理解直接影响使用方式// map 模板定义 template class Key, // 键的类型Keytypedef 为 key_type class T, // 值的类型Valuetypedef 为 mapped_type class Compare lessKey, // 键的比较方式默认升序 class Alloc allocatorpairconst Key, T // 空间配置器 class map; // 核心内部类型 typedef pairconst Key, T value_type; // 红黑树节点存储的键值对Key 不可改 typedef Key key_type; // 键的类型 typedef T mapped_type; // 值的类型value_typemap 存储的是 pairconst Key, T 类型(这个非常重要后面会反复进行讲解)其中 Key 被 const 修饰意味着不能通过迭代器修改 Key会破坏红黑树结构但可以修改 TValueCompare默认用 lessKey 实现升序若需降序可传入 greaterKey如 mapint, int, greaterintpair 类型介绍map 底层的红黑树节点中的数据使用 pairKey,T 存储键值对数据。typedef pairconst 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) { } templateclass U, class V pair(const pairU, V pr) : first(pr.first), second(pr.second) { } }; template class T1, class T2 inline pairT1, T2 make_pair(T1 x, T2 y) { return (pairT1, T2(x, y)); } //make_pair这个函数模板可以帮助我们节省代码量来构造map //简单来讲就是通过调用这个函数模板返回的类型就是map一些接口需要的pair的类型我们会发现 value_type 这个是由 pairconst Key, T typedef 而来的而 pair 里面两个模板参数分别就是 Key(键) 和 T(值Value)所以我们可以理解为是将 map 中的Key(键) 和 T(值Value) 通过类模板 pair 再进行了一次封装之所以要这样是因为后面讲解的接口中有些需要传的类型是 pair 类型所以在这里对 pair 的结构先进行讲解而且 pair 会在后面的讲解中频繁地使用。二、 map 基础操作构造、遍历与增删查改结合具体的代码示例分模块讲解 map 的常用操作注释会补充关键细节。1、构造与初始化set 的构造常见相关接口// empty (1) ⽆参默认构造 explicit map (const key_compare comp key_compare(), const allocator_type alloc allocator_type()); // range (2) 迭代器区间构造 template class InputIterator map (InputIterator first, InputIterator last, const key_compare comp key_compare(), const allocator_type allocator_type()); // copy (3) 拷⻉构造 map (const map x); // initializer list (5) initializer 列表构造 map (initializer_listvalue_type il, const key_compare comp key_compare(), const allocator_type alloc allocator_type()); // 迭代器是⼀个双向迭代器 iterator - a bidirectional iterator to const value_type // 正向迭代器 iterator begin(); iterator end(); // 反向迭代器 reverse_iterator rbegin(); reverse_iterator rend();map 支持多种构造方式包括默认构造、迭代器区间构造、初始化列表构造等实际开发中初始化列表构造最常用注意看下面代码的注释#include iostream #include string #include map using namespace std; //map构造与初始化 void test_map1() { // 1. 默认构造空 map mapstring, string dict1; // 2. 初始化列表构造C11支持比较推荐 mapstring, string dict2 { {sort, 排序}, {left, 左边}, {right, 右边} }; //最外面一层的花括号代表的是列表构造 //而里面的每个花括号其实就是类型转换中的多参数转化(C11支持)通过一个花括号的形式将多个参数放在一起 //{sort, 排序}等本质就是“多参数转化”隐式类型转换成 pairstring, string 类型 // 3. 迭代器区间构造从其他 map 或容器拷贝 mapstring, string dict3(dict2.begin(), dict2.end()); // 4. 拷贝构造 mapstring, string dict4(dict3); //构造测试打印 auto it dict2.begin(); while (it ! dict2.end()) { //cout *it endl;//error //因为迭代器it解引用获取的是里面的数据而里面包含有两个值(Key、Value) //而 pair 并没有重载流插入cin和流提取coutC又不能同时返回两个值所以会报错 cout (*it).first : (*it).second endl; //所以我们需要手动通过.来访问first和second两个成员的值 cout it-first : it-second endl; //pair不仅重载了*也重载了-所以当不对迭代器进行解引用时 //我们也可以通过调用operator-来访问first和second上面是简化版本实际展开为 //cout it.operator-()-first : it.operator-()-second endl; it; } cout endl; } int main() { test_map1(); return 0; }2、迭代器遍历map 的迭代器是双向迭代器仅支持 /-- 操作而不能使用 /-操作遍历方式包括 “迭代器循环”“范围 for”//迭代器遍历 void test_map2() { mapstring, string dict1 { {sort, 排序}, {left, 左边}, {right, 右边} }; // 方式1普通迭代器遍历支持修改 Value auto it dict1.begin(); while (it ! dict1.end()) { cout it-first : it-second endl; // 尝试修改 Key编译报错Key 是 const 修饰的不可修改 //it-first new_left; //error // 修改 Value合法 if (it-first left) { it-second 左边(修改后); } it; } cout endl; // 方式2范围 for 遍历传引用可减少拷贝次数优化效率const 保护不被修改 for (const auto e : dict1) { // e 是 pairconst string, string 类型(重点) cout e.first : e.second endl; } cout endl; }核心细节map 的 iterator 和 const_iterator 都不能修改 Key但 iterator 可以修改 Value若只需读取可优先用 const auto 传引用减少拷贝开销优化效率。3、插入操作insertmap 的 insert 接口用于插入键值对返回 pairiterator, bool其中iterator指向插入成功的新节点或已存在的相同 Key 节点booltrue 表示插入成功false 表示 Key 已存在插入失败。insert 支持多种插入形式实际开发中推荐“初始化列表”和“make_pair”以及多参数隐式类型转换//插入操作insert void test_map3() { mapstring, string dict; //方式1插入 pair 对象C98 风格较繁琐) pairstring, string kv1(sort, 排序); dict.insert(kv1); // 方式2插入匿名 pair 对象略简洁 dict.insert(pairstring, string(left, 左边)); // 方式3用 make_pair 生成 pair推荐无需显式写类型 dict.insert(make_pair(right, 右边)); // 方法4初始化列表插入(单参数隐式类型转换) dict.insert({ insert,插入 }); // 批量插入多个键值对用多参数的隐式类型转换C11支持) dict.insert({ {map, 映射}, {erase, 删除} }); // 插入重复 Key返回的pair第二个成员(bool)为false不修改原数据 auto ret dict.insert({ left, 左边重复插入 }); if (!ret.second) { cout left 已存在当前含义 ret.first-second endl; } // 输出结果 for (const auto e : dict) { cout e.first : e.second endl; } } int main() { test_map3(); return 0; }4、查找与删除find/erase4.1查找find 与 countfind(Key)查找指定 Key返回指向该 Key 的迭代器若不存在返回 end()时间复杂度O(log N) 效率count(Key)返回 Key 的出现次数map 中 Key 唯一故返回 0 或 1可间接用于查找。//查找与删除find/erase void test_map4() { mapstring, string dict { {sort, 排序}, {left, 左边}, {right, 右边} }; // 1. 查找单词并且进行删除 string x; cin x; auto pos dict.find(x); //iterator find (const key_type k); if (pos ! dict.end()) { cout 找到 Key x 值为 pos-second endl; //删除迭代器指向的节点 dict.erase(pos); //此时迭代器pos失效无法访问 cout 删除 Key left 后 endl; for (const auto e : dict) { cout e.first : e.second endl; } } else { cout 没有找到 Key x endl; } cout endl; // 2. 直接删除指定 Key返回删除的个数map 中 0 或 1 size_t del_cnt dict.erase(right); //size_type erase(const key_type k); cout 删除 Key right影响个数 del_cnt endl; cout endl; // 3. 删除迭代器区间删除所有元素 dict.erase(dict.begin(), dict.end()); //void erase (iterator first, iterator last); cout 删除所有元素后map 大小 dict.size() endl; } int main() { test_map4(); return 0; }5、核心特性operator [] 的多功能性map 的 operator[] 是最灵活的接口兼具“插入、查找、修改”三种功能其内部实现依赖前面所讲解的 insert核心逻辑如下// operator[] 内部伪代码便于理解方括号的执行逻辑 mapped_type operator[](const key_type k) { // 插入 {k, mapped_type()}默认构造的 Value如 int 为 0string 为空 pairiterator, bool ret insert({ k, mapped_type() }); // 返回 Value 的引用无论插入成功与否都指向 Key 对应的 Value return ret.first-second; }在前面讲解 insert 接口时我们就提到了这个接口当插入失败时可以充当查找功能就是为这里实现 operator 做铺垫的基于此实现operator[] 就可以灵活应对不同场景//核心特性operator [] void test_map5() { mapstring, int countMap; // 统计每种水果出现次数 string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 香蕉 }; ////方法一(不使用operator[]) ////先判断该水果是否存在于map中(find())如果存在则Value如果不存在则insert //for (auto e : arr) //{ // auto it countMap.find(e); // if (it ! countMap.end())//说明存在 // { // it-second; // } // else//说明不存在 // { // countMap.insert({e, 1}); // } //}//这样写我们就会发现代码是比较多的那能不能优化呢是可以的就是利用operator [] //方法二(使用operator[]同时进行插入、查找和修改操作) for (auto fruit : arr) { countMap[fruit]; // 若 fruit 不存在先插入 { fruit, int() }返回插入位置的Value引用( 调用的默认构造int()0 ) 后变为 1 // 若 fruit 已存在则不会执行插入操作并且查找到fruit存在位置返回存在位置 Value 引用 后次数增加 } //测试打印结果 cout 水果统计结果 endl; for (const auto e : countMap) { cout e.first : e.second endl; } cout endl; // 场景2只插入数据Key 不存在时插入默认 Value mapstring, string dict; dict[insert]; // 插入 { insert, string() }string 默认空 cout 插入 insert 后值 dict[insert] endl; // 场景3插入 修改Key 不存在时插入存在时修改 dict[left] 左边; // 插入 { left, string() }同时将返回的结果 修改为 左边 dict[left] 左边修改后; // Key已经存在查找后返回结果左边再修改为 左边修改后 cout 修改 left 后值 dict[left] endl; // 场景4纯粹查找Key 存在时返回 Value 引用 cout 查找 left值 dict[left] endl; //一定要注意的是用operator[]用于查找时要保证Key在map中一定是已经存在的否则就会出问题 //因为不管Key在不在map中operator[]后都一定会使其存在于map中就体现不出查找的功能 } int main() { test_map5(); return 0; }三. map 与 multimap 的差异multimap 是 map 的 “兄弟容器”底层同样基于红黑树但核心差异是支持 Key 冗余相同 Key 可重复插入由此导致接口和使用场景不同特性mapmultimapKey 唯一性唯一重复插入失败不唯一支持重复 Keyoperator[]支持插入 / 查找 / 修改不支持Key 冗余无法确定修改哪个find(Key)返回唯一 Key 的迭代器返回中序遍历的第一个 Key 迭代器count(Key)返回 0 或 1返回 Key 的实际出现次数erase(Key)删除唯一 Key返回 0 或 1删除所有相同 Key返回删除个数void test_multimap() { //multimap没有[] multimapstring, string dict; dict.insert({ right, 右边 }); dict.insert({ left, 左边 }); dict.insert({ right, 右边xx }); dict.insert({ right, 右边 }); for (const auto e : dict) { cout e.first : e.second endl; } cout endl; dict.erase(right); //删除所有的right返回删除个数 for (const auto e : dict) { cout e.first : e.second endl; } cout endl; } int main() { test_multimap(); return 0; }四、map 实战LeetCode 经典案例map 的核心价值在于“高效键值映射”和“自动排序”在算法题中可简化复杂逻辑以下是两个典型案例1、随机链表的复制题目链接138. 随机链表的复制 - 力扣LeetCode在数据结构初阶阶段为了控制随机指针我们将拷贝结点链接在原节点的后面解决后面拷贝节点还得解下来链接非常麻烦。这里我们直接让{原结点, 拷贝结点} 建立映射关系放到 map 中通过 operator[] 访问原结点就能返回相对于的拷贝结点控制随机指针会非常简单方便这里体现了 map 在解决⼀些问题时的价值完全是降维打击。C算法代码class Solution { public: Node* copyRandomList(Node* head) { mapNode*, Node* Node_Copy_Map; //步骤一先拷贝一个链表 Node* copyhead NULL; Node* copypail NULL; Node* cur head; while(cur) { if(copypail NULL) { copyhead copypail new Node(cur-val); } else { copypail-next new Node(cur-val); copypail copypail-next; } //步骤二在拷贝过程中将原节点和拷贝节点通过map进行联系 Node_Copy_Map[cur] copypail; cur cur-next; } //步骤三处理random //通过Node_Copy_Map[cur-random]就能获取到对应cur-random的copy结点位置 cur head; copypail copyhead; while(cur) { if(cur-random nullptr) { copypail-random nullptr; } else { copypail-random Node_Copy_Map[cur-random]; } cur cur-next; copypail copypail-next; } return copyhead; } };2、前k个高频单词题目链接692. 前K个高频单词 - 力扣LeetCode本题目我们利用 map 统计出次数以后返回的答案应该按单词出现频率由高到低排序(需要手动实现仿函数)但还有一个特殊要求如果不同的单词有相同出现频率按字典顺序排序(这是这道题比较麻烦的地方以下有两种解决思路)。C算法代码解决思路1用排序找前k个单词因为 map 中已经对 key 单词排序过(按照字母的大小顺序)也就意味着遍历 map 时次数相同的单词字典序小的在前面字典序大的在后面。那么我们将数据放到vector 中用一个稳定的排序就可以实现上面特殊要求但是sort 底层是快排 是不稳定的所以我们要用stable_sort他是稳定的。class Solution { public: struct Compare { bool operator()(const pairstring, int kv1, const pairstring, int kv2) { return kv1.second kv2.second; } }; vectorstring topKFrequent(vectorstring words, int k) { mapstring,int CountMap; for(int i 0; i words.size(); i) { CountMap[words[i]]; } vectorpairstring,int v(CountMap.begin(),CountMap.end()); //sort(v.begin(),v.end(),Compare()); // 得稳定排序 stable_sort(v.begin(),v.end(),Compare()); vectorstring ret; for(size_t i0;ik;i) { ret.push_back(v[i].first); } return ret; } };解决思路2(两种方法两种容器)将 map 统计出的次数的数据放到 vector 中排序或者放到 priority_queue 中来选出前k个。利用仿函数强行控制次数相等的字典序小的在前面。方案一vectorclass Solution { public: //手动实现排序的仿函数因为默认的排序方式不是我们想要的 struct Compare { bool operator()(const pairstring, int kv1, const pairstring, int kv2) { return kv1.second kv2.second || kv1.second kv2.second kv1.first kv2.first; } //保证次数高的单词排在前面的同时也保证了当次数相同时按照字母小的单词在前面 }; vectorstring topKFrequent(vectorstring words, int k) { vectorstring ret; mapstring, int CountMap; for(int i 0; i words.size(); i) { CountMap[words[i]]; } //此时map就将单词按照字母从小到大的顺序将出现次数统计出来了 //通过创建一个类型为pair的vector进行排序 //因为map的迭代器是双向迭代器而sort需要随机迭代器才能使用 vectorpairstring, int p(CountMap.begin(), CountMap.end()); sort(p.begin(), p.end(), Compare()); //因为sort底层是快排即使map是按照字母从小到大的顺序存放次数sort也会打乱所以实现仿函数时也要考虑 for(int i 0; i k; i) { ret.push_back(p[i].first); } return ret; } };方案二优先级队列class Solution { public: struct Compare { // 次数多的在前面次数相等的时候字典序小的在前面 bool operator()(const pairstring, int x, const pairstring, int y) { // 要注意优先级队列底层是反的大堆要实现小于比较所以这里次数相等想要字典序小的在前面要比较字典序大的为真 return x.second y.second || (x.second y.second x.first y.first); } }; vectorstring topKFrequent(vectorstring words, int k) { mapstring,int CountMap; for(auto e:words) { CountMap[e]; } priority_queuepairstring,int,vectorpairstring,int,Compare q(CountMap.begin(),CountMap.end()); vectorstring ret; for(size_t i0;ik;i) { ret.push_back(q.top().first); q.pop(); } return ret; } };结束语到此C STL 中的 map 容器我们就讲解完了。map系列容器是 C STL 中 “键值映射” 场景的核心工具map的键唯一、multimap的键冗余特性底层红黑树更是保障了 O (log N) 的高效操作。从operator[]的多功能统计到算法题中简化复杂逻辑的实战价值它既降低了开发复杂度又兼顾了性能与易用性。希望对大家学习C能有所收获C参考文档https://legacy.cplusplus.com/reference/https://zh.cppreference.com/w/cpphttps://en.cppreference.com/w/
C++ STL map 系列深度解析：从底层原理、核心接口到实战场景
小叶-duck个人主页❄️个人专栏《Data-Structure-Learning》《C入门到进阶自我学习过程记录》《算法题讲解指南》--优选算法《算法题讲解指南》--递归、搜索与回溯算法《算法题讲解指南》--动态规划算法✨未择之路不须回头已择之路纵是荆棘遍野亦作花海遨游目录前言一、map 核心原理键值对与红黑树底层1、什么是 map2、关键类型定义二、 map 基础操作构造、遍历与增删查改1、构造与初始化2、迭代器遍历3、插入操作insert4、查找与删除find/erase4.1 查找find 与 count5、核心特性operator [] 的多功能性三. map 与 multimap 的差异四、map 实战LeetCode 经典案例1、随机链表的复制题目链接C算法代码2、前k个高频单词题目链接结束语前言在 C STL 容器中map是兼具“高效查找”与“键值映射”能力的关联式容器底层基于红黑树实现支持 O(log N) 级别的增删查改操作且会按键值Key自动排序。本文将从 map 的核心概念切入结合实操代码详细讲解其构造、增删查改、迭代器遍历等基础操作对比 map 与 multimap 的差异帮你彻底掌握 map 的使用。一、map 核心原理键值对与红黑树底层1、什么是 mapmap 是一种“键值对Key-Value”容器每个元素包含一个不可修改的键Key 和一个可修改的值Value底层通过红黑树平衡二叉搜索树组织数据因此具备两个核心特性键唯一相同的 Key 无法重复插入自动排序遍历 map 时走的中序遍历元素会按 Key 的升序默认用 lessKey 比较排列。map的参考文档map - C Reference2、关键类型定义map 的模板参数与内部类型需重点理解直接影响使用方式// map 模板定义 template class Key, // 键的类型Keytypedef 为 key_type class T, // 值的类型Valuetypedef 为 mapped_type class Compare lessKey, // 键的比较方式默认升序 class Alloc allocatorpairconst Key, T // 空间配置器 class map; // 核心内部类型 typedef pairconst Key, T value_type; // 红黑树节点存储的键值对Key 不可改 typedef Key key_type; // 键的类型 typedef T mapped_type; // 值的类型value_typemap 存储的是 pairconst Key, T 类型(这个非常重要后面会反复进行讲解)其中 Key 被 const 修饰意味着不能通过迭代器修改 Key会破坏红黑树结构但可以修改 TValueCompare默认用 lessKey 实现升序若需降序可传入 greaterKey如 mapint, int, greaterintpair 类型介绍map 底层的红黑树节点中的数据使用 pairKey,T 存储键值对数据。typedef pairconst 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) { } templateclass U, class V pair(const pairU, V pr) : first(pr.first), second(pr.second) { } }; template class T1, class T2 inline pairT1, T2 make_pair(T1 x, T2 y) { return (pairT1, T2(x, y)); } //make_pair这个函数模板可以帮助我们节省代码量来构造map //简单来讲就是通过调用这个函数模板返回的类型就是map一些接口需要的pair的类型我们会发现 value_type 这个是由 pairconst Key, T typedef 而来的而 pair 里面两个模板参数分别就是 Key(键) 和 T(值Value)所以我们可以理解为是将 map 中的Key(键) 和 T(值Value) 通过类模板 pair 再进行了一次封装之所以要这样是因为后面讲解的接口中有些需要传的类型是 pair 类型所以在这里对 pair 的结构先进行讲解而且 pair 会在后面的讲解中频繁地使用。二、 map 基础操作构造、遍历与增删查改结合具体的代码示例分模块讲解 map 的常用操作注释会补充关键细节。1、构造与初始化set 的构造常见相关接口// empty (1) ⽆参默认构造 explicit map (const key_compare comp key_compare(), const allocator_type alloc allocator_type()); // range (2) 迭代器区间构造 template class InputIterator map (InputIterator first, InputIterator last, const key_compare comp key_compare(), const allocator_type allocator_type()); // copy (3) 拷⻉构造 map (const map x); // initializer list (5) initializer 列表构造 map (initializer_listvalue_type il, const key_compare comp key_compare(), const allocator_type alloc allocator_type()); // 迭代器是⼀个双向迭代器 iterator - a bidirectional iterator to const value_type // 正向迭代器 iterator begin(); iterator end(); // 反向迭代器 reverse_iterator rbegin(); reverse_iterator rend();map 支持多种构造方式包括默认构造、迭代器区间构造、初始化列表构造等实际开发中初始化列表构造最常用注意看下面代码的注释#include iostream #include string #include map using namespace std; //map构造与初始化 void test_map1() { // 1. 默认构造空 map mapstring, string dict1; // 2. 初始化列表构造C11支持比较推荐 mapstring, string dict2 { {sort, 排序}, {left, 左边}, {right, 右边} }; //最外面一层的花括号代表的是列表构造 //而里面的每个花括号其实就是类型转换中的多参数转化(C11支持)通过一个花括号的形式将多个参数放在一起 //{sort, 排序}等本质就是“多参数转化”隐式类型转换成 pairstring, string 类型 // 3. 迭代器区间构造从其他 map 或容器拷贝 mapstring, string dict3(dict2.begin(), dict2.end()); // 4. 拷贝构造 mapstring, string dict4(dict3); //构造测试打印 auto it dict2.begin(); while (it ! dict2.end()) { //cout *it endl;//error //因为迭代器it解引用获取的是里面的数据而里面包含有两个值(Key、Value) //而 pair 并没有重载流插入cin和流提取coutC又不能同时返回两个值所以会报错 cout (*it).first : (*it).second endl; //所以我们需要手动通过.来访问first和second两个成员的值 cout it-first : it-second endl; //pair不仅重载了*也重载了-所以当不对迭代器进行解引用时 //我们也可以通过调用operator-来访问first和second上面是简化版本实际展开为 //cout it.operator-()-first : it.operator-()-second endl; it; } cout endl; } int main() { test_map1(); return 0; }2、迭代器遍历map 的迭代器是双向迭代器仅支持 /-- 操作而不能使用 /-操作遍历方式包括 “迭代器循环”“范围 for”//迭代器遍历 void test_map2() { mapstring, string dict1 { {sort, 排序}, {left, 左边}, {right, 右边} }; // 方式1普通迭代器遍历支持修改 Value auto it dict1.begin(); while (it ! dict1.end()) { cout it-first : it-second endl; // 尝试修改 Key编译报错Key 是 const 修饰的不可修改 //it-first new_left; //error // 修改 Value合法 if (it-first left) { it-second 左边(修改后); } it; } cout endl; // 方式2范围 for 遍历传引用可减少拷贝次数优化效率const 保护不被修改 for (const auto e : dict1) { // e 是 pairconst string, string 类型(重点) cout e.first : e.second endl; } cout endl; }核心细节map 的 iterator 和 const_iterator 都不能修改 Key但 iterator 可以修改 Value若只需读取可优先用 const auto 传引用减少拷贝开销优化效率。3、插入操作insertmap 的 insert 接口用于插入键值对返回 pairiterator, bool其中iterator指向插入成功的新节点或已存在的相同 Key 节点booltrue 表示插入成功false 表示 Key 已存在插入失败。insert 支持多种插入形式实际开发中推荐“初始化列表”和“make_pair”以及多参数隐式类型转换//插入操作insert void test_map3() { mapstring, string dict; //方式1插入 pair 对象C98 风格较繁琐) pairstring, string kv1(sort, 排序); dict.insert(kv1); // 方式2插入匿名 pair 对象略简洁 dict.insert(pairstring, string(left, 左边)); // 方式3用 make_pair 生成 pair推荐无需显式写类型 dict.insert(make_pair(right, 右边)); // 方法4初始化列表插入(单参数隐式类型转换) dict.insert({ insert,插入 }); // 批量插入多个键值对用多参数的隐式类型转换C11支持) dict.insert({ {map, 映射}, {erase, 删除} }); // 插入重复 Key返回的pair第二个成员(bool)为false不修改原数据 auto ret dict.insert({ left, 左边重复插入 }); if (!ret.second) { cout left 已存在当前含义 ret.first-second endl; } // 输出结果 for (const auto e : dict) { cout e.first : e.second endl; } } int main() { test_map3(); return 0; }4、查找与删除find/erase4.1查找find 与 countfind(Key)查找指定 Key返回指向该 Key 的迭代器若不存在返回 end()时间复杂度O(log N) 效率count(Key)返回 Key 的出现次数map 中 Key 唯一故返回 0 或 1可间接用于查找。//查找与删除find/erase void test_map4() { mapstring, string dict { {sort, 排序}, {left, 左边}, {right, 右边} }; // 1. 查找单词并且进行删除 string x; cin x; auto pos dict.find(x); //iterator find (const key_type k); if (pos ! dict.end()) { cout 找到 Key x 值为 pos-second endl; //删除迭代器指向的节点 dict.erase(pos); //此时迭代器pos失效无法访问 cout 删除 Key left 后 endl; for (const auto e : dict) { cout e.first : e.second endl; } } else { cout 没有找到 Key x endl; } cout endl; // 2. 直接删除指定 Key返回删除的个数map 中 0 或 1 size_t del_cnt dict.erase(right); //size_type erase(const key_type k); cout 删除 Key right影响个数 del_cnt endl; cout endl; // 3. 删除迭代器区间删除所有元素 dict.erase(dict.begin(), dict.end()); //void erase (iterator first, iterator last); cout 删除所有元素后map 大小 dict.size() endl; } int main() { test_map4(); return 0; }5、核心特性operator [] 的多功能性map 的 operator[] 是最灵活的接口兼具“插入、查找、修改”三种功能其内部实现依赖前面所讲解的 insert核心逻辑如下// operator[] 内部伪代码便于理解方括号的执行逻辑 mapped_type operator[](const key_type k) { // 插入 {k, mapped_type()}默认构造的 Value如 int 为 0string 为空 pairiterator, bool ret insert({ k, mapped_type() }); // 返回 Value 的引用无论插入成功与否都指向 Key 对应的 Value return ret.first-second; }在前面讲解 insert 接口时我们就提到了这个接口当插入失败时可以充当查找功能就是为这里实现 operator 做铺垫的基于此实现operator[] 就可以灵活应对不同场景//核心特性operator [] void test_map5() { mapstring, int countMap; // 统计每种水果出现次数 string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 香蕉 }; ////方法一(不使用operator[]) ////先判断该水果是否存在于map中(find())如果存在则Value如果不存在则insert //for (auto e : arr) //{ // auto it countMap.find(e); // if (it ! countMap.end())//说明存在 // { // it-second; // } // else//说明不存在 // { // countMap.insert({e, 1}); // } //}//这样写我们就会发现代码是比较多的那能不能优化呢是可以的就是利用operator [] //方法二(使用operator[]同时进行插入、查找和修改操作) for (auto fruit : arr) { countMap[fruit]; // 若 fruit 不存在先插入 { fruit, int() }返回插入位置的Value引用( 调用的默认构造int()0 ) 后变为 1 // 若 fruit 已存在则不会执行插入操作并且查找到fruit存在位置返回存在位置 Value 引用 后次数增加 } //测试打印结果 cout 水果统计结果 endl; for (const auto e : countMap) { cout e.first : e.second endl; } cout endl; // 场景2只插入数据Key 不存在时插入默认 Value mapstring, string dict; dict[insert]; // 插入 { insert, string() }string 默认空 cout 插入 insert 后值 dict[insert] endl; // 场景3插入 修改Key 不存在时插入存在时修改 dict[left] 左边; // 插入 { left, string() }同时将返回的结果 修改为 左边 dict[left] 左边修改后; // Key已经存在查找后返回结果左边再修改为 左边修改后 cout 修改 left 后值 dict[left] endl; // 场景4纯粹查找Key 存在时返回 Value 引用 cout 查找 left值 dict[left] endl; //一定要注意的是用operator[]用于查找时要保证Key在map中一定是已经存在的否则就会出问题 //因为不管Key在不在map中operator[]后都一定会使其存在于map中就体现不出查找的功能 } int main() { test_map5(); return 0; }三. map 与 multimap 的差异multimap 是 map 的 “兄弟容器”底层同样基于红黑树但核心差异是支持 Key 冗余相同 Key 可重复插入由此导致接口和使用场景不同特性mapmultimapKey 唯一性唯一重复插入失败不唯一支持重复 Keyoperator[]支持插入 / 查找 / 修改不支持Key 冗余无法确定修改哪个find(Key)返回唯一 Key 的迭代器返回中序遍历的第一个 Key 迭代器count(Key)返回 0 或 1返回 Key 的实际出现次数erase(Key)删除唯一 Key返回 0 或 1删除所有相同 Key返回删除个数void test_multimap() { //multimap没有[] multimapstring, string dict; dict.insert({ right, 右边 }); dict.insert({ left, 左边 }); dict.insert({ right, 右边xx }); dict.insert({ right, 右边 }); for (const auto e : dict) { cout e.first : e.second endl; } cout endl; dict.erase(right); //删除所有的right返回删除个数 for (const auto e : dict) { cout e.first : e.second endl; } cout endl; } int main() { test_multimap(); return 0; }四、map 实战LeetCode 经典案例map 的核心价值在于“高效键值映射”和“自动排序”在算法题中可简化复杂逻辑以下是两个典型案例1、随机链表的复制题目链接138. 随机链表的复制 - 力扣LeetCode在数据结构初阶阶段为了控制随机指针我们将拷贝结点链接在原节点的后面解决后面拷贝节点还得解下来链接非常麻烦。这里我们直接让{原结点, 拷贝结点} 建立映射关系放到 map 中通过 operator[] 访问原结点就能返回相对于的拷贝结点控制随机指针会非常简单方便这里体现了 map 在解决⼀些问题时的价值完全是降维打击。C算法代码class Solution { public: Node* copyRandomList(Node* head) { mapNode*, Node* Node_Copy_Map; //步骤一先拷贝一个链表 Node* copyhead NULL; Node* copypail NULL; Node* cur head; while(cur) { if(copypail NULL) { copyhead copypail new Node(cur-val); } else { copypail-next new Node(cur-val); copypail copypail-next; } //步骤二在拷贝过程中将原节点和拷贝节点通过map进行联系 Node_Copy_Map[cur] copypail; cur cur-next; } //步骤三处理random //通过Node_Copy_Map[cur-random]就能获取到对应cur-random的copy结点位置 cur head; copypail copyhead; while(cur) { if(cur-random nullptr) { copypail-random nullptr; } else { copypail-random Node_Copy_Map[cur-random]; } cur cur-next; copypail copypail-next; } return copyhead; } };2、前k个高频单词题目链接692. 前K个高频单词 - 力扣LeetCode本题目我们利用 map 统计出次数以后返回的答案应该按单词出现频率由高到低排序(需要手动实现仿函数)但还有一个特殊要求如果不同的单词有相同出现频率按字典顺序排序(这是这道题比较麻烦的地方以下有两种解决思路)。C算法代码解决思路1用排序找前k个单词因为 map 中已经对 key 单词排序过(按照字母的大小顺序)也就意味着遍历 map 时次数相同的单词字典序小的在前面字典序大的在后面。那么我们将数据放到vector 中用一个稳定的排序就可以实现上面特殊要求但是sort 底层是快排 是不稳定的所以我们要用stable_sort他是稳定的。class Solution { public: struct Compare { bool operator()(const pairstring, int kv1, const pairstring, int kv2) { return kv1.second kv2.second; } }; vectorstring topKFrequent(vectorstring words, int k) { mapstring,int CountMap; for(int i 0; i words.size(); i) { CountMap[words[i]]; } vectorpairstring,int v(CountMap.begin(),CountMap.end()); //sort(v.begin(),v.end(),Compare()); // 得稳定排序 stable_sort(v.begin(),v.end(),Compare()); vectorstring ret; for(size_t i0;ik;i) { ret.push_back(v[i].first); } return ret; } };解决思路2(两种方法两种容器)将 map 统计出的次数的数据放到 vector 中排序或者放到 priority_queue 中来选出前k个。利用仿函数强行控制次数相等的字典序小的在前面。方案一vectorclass Solution { public: //手动实现排序的仿函数因为默认的排序方式不是我们想要的 struct Compare { bool operator()(const pairstring, int kv1, const pairstring, int kv2) { return kv1.second kv2.second || kv1.second kv2.second kv1.first kv2.first; } //保证次数高的单词排在前面的同时也保证了当次数相同时按照字母小的单词在前面 }; vectorstring topKFrequent(vectorstring words, int k) { vectorstring ret; mapstring, int CountMap; for(int i 0; i words.size(); i) { CountMap[words[i]]; } //此时map就将单词按照字母从小到大的顺序将出现次数统计出来了 //通过创建一个类型为pair的vector进行排序 //因为map的迭代器是双向迭代器而sort需要随机迭代器才能使用 vectorpairstring, int p(CountMap.begin(), CountMap.end()); sort(p.begin(), p.end(), Compare()); //因为sort底层是快排即使map是按照字母从小到大的顺序存放次数sort也会打乱所以实现仿函数时也要考虑 for(int i 0; i k; i) { ret.push_back(p[i].first); } return ret; } };方案二优先级队列class Solution { public: struct Compare { // 次数多的在前面次数相等的时候字典序小的在前面 bool operator()(const pairstring, int x, const pairstring, int y) { // 要注意优先级队列底层是反的大堆要实现小于比较所以这里次数相等想要字典序小的在前面要比较字典序大的为真 return x.second y.second || (x.second y.second x.first y.first); } }; vectorstring topKFrequent(vectorstring words, int k) { mapstring,int CountMap; for(auto e:words) { CountMap[e]; } priority_queuepairstring,int,vectorpairstring,int,Compare q(CountMap.begin(),CountMap.end()); vectorstring ret; for(size_t i0;ik;i) { ret.push_back(q.top().first); q.pop(); } return ret; } };结束语到此C STL 中的 map 容器我们就讲解完了。map系列容器是 C STL 中 “键值映射” 场景的核心工具map的键唯一、multimap的键冗余特性底层红黑树更是保障了 O (log N) 的高效操作。从operator[]的多功能统计到算法题中简化复杂逻辑的实战价值它既降低了开发复杂度又兼顾了性能与易用性。希望对大家学习C能有所收获C参考文档https://legacy.cplusplus.com/reference/https://zh.cppreference.com/w/cpphttps://en.cppreference.com/w/
