目录1. 关联式容器与键值对简介2. map 容器详解2.1 map 核心特性2.2 map 的常用接口与代码实战2.3 遍历 map 的四种方式2.4 数据查找2.5 核心利器operator[]3. multimap 容器详解3.1 multimap 核心特性3.2 multimap 使用演示4. 题库实战实战一实战二5. map 进阶深度剖析仿函数与空间配置器5.1 深度剖析自定义比较器仿函数的多维排序5.2 深度剖析空间配置器Allocator与内存碎片优化附录基于红黑树的 map 封装实现map官方使用文档multimap官方使用文档在 C STL 中map和multimap是最常用的树形关联式容器。它们底层均由红黑树平衡二叉搜索树实现能够提供高效的O ( l o g 2 N ) O(log_2 N)O(log2N)检索效率。本文将全面深入剖析这两种容器的特性、接口用法、高频算法实战并在第 5 部分深度探讨仿函数与空间配置器最后在附录中展示其底层的红黑树封装实现。1. 关联式容器与键值对简介与vector、list等序列式容器不同关联式容器里面存储的是key, value结构的键值对在数据检索时效率更高。在 C 中键值对通常通过std::pair结构体来表示。它包含两个成员变量first代表键值keysecond代表与 key 对应的信息value。2. map 容器详解2.1 map 核心特性键值对存储map存储的元素是由键值key和映射值value组合而成的键值对。Key 的唯一性与不可变性map中的key是唯一的并且不能修改。自动排序默认按照小于的方式对key进行比较。有序序列map中的元素如果用迭代器去遍历可以得到一个有序的序列。底层结构map的底层为平衡搜索树红黑树查找效率比较高时间复杂度为O ( l o g 2 N ) O(log_2 N)O(log2N)。2.2 map 的常用接口与代码实战map提供了丰富的接口用于状态管理、数据增删及区间查找。以下为核心接口的高频使用场景代码示例#includeiostream#includemap#includestringusingnamespacestd;intmain(){mapint,stringm;// --- 1. 5种 map 定义的方式 ---//定义有名对象pairstring,stringp(char,字符);mapstring,stringm;m.insert(p);//匿名对象m.insert(pairstring,string(int,整型);//make_pair-自动识别插入的类型m.insert(make_pair(folat,浮点型));//InputIteratormapstring,stringm1{{folat,浮点型},{int,整型},{char,字符}};//插入修改先插入一个left,,然后查找key再修改成left,左边dict[left]左边;// --- 2. 容量与状态 ---cout当前元素个数: m.size()endl;cout是否为空: (m.empty()?Yes:No)endl;// --- 3. 统计与查找 ---// count 返回 key 出现的次数在 map 中只有 0 或 1常用于判断 key 是否存在if(m.count(2)){coutKey 2 存在endl;}// --- 4. 边界迭代器查找---// lower_bound: 返回第一个 2 的元素的迭代器autoit_lowm.lower_bound(2);// upper_bound: 返回第一个 2 的元素的迭代器autoit_upm.upper_bound(2);coutlower_bound(2): it_low-secondendl;// --- 5. 数据删除 ---m.erase(1);// 按 key 直接删除m.erase(m.begin());// 传入迭代器删除// m.erase(it_low, it_up); // 传入迭代器区间进行范围删除 [first, last)// --- 6. 清空 ---m.clear();cout清空后元素个数: m.size()endl;return0;}2.3 遍历 map 的四种方式mapstring,string::iterator itm1.begin();while(it!m1.end()){// 1. 解引用cout(*it).first:(*it).secondendl;// 2. 使用重载 operator-coutit-first:it-secondendl;it;}coutendl;// 3. 范围for (最推荐的现代 C 写法)for(constautoe:m1){coute.first:e.secondendl;}coutendl;// 4. C17 以后支持的结构化绑定写法for(auto[x,y]:m1){coutx:yendl;}coutendl;2.4 数据查找使用find接口可以高效查找元素找不到则返回end()。string str;while(cinstr){autoretm.find(str);if(ret!m.end()){coutret-first:ret-secondendl;}else{cout没有这个单词endl;}}2.5 核心利器operator[]operator[]是map中极为强大且常用的操作符其实际进行的是插入查找。intmain(){mapstring,stringdict;//插入修改先插入一个left,,然后查找key再修改成left,左边dict[left]左边;//修改dict[left]左边剩余;//key存在- 查找coutdict[left]endl;//key不存在- 插入insert ,coutdict[insert]endl;return0;}可用于极其精简地计数intmain(){string arr[]{苹果,香蕉,梨子,香蕉,梨子,香蕉,梨子,香蕉,梨子};mapstring,intcountMap;for(constautoe:arr){// 利用 operator[] 进行极简计数countMap[e];}for(constautoe:countMap){coute.first:e.secondendl;}return0;}3. multimap 容器详解multimap允许数据冗余没有operator[]。3.1 multimap 核心特性允许键值重复与map的区别是multimap中的元素key可以重复。底层结构与效率multimap底层结构也是二叉搜索树红黑树找某个元素的时间复杂度为O ( l o g 2 N ) O(log_2 N)O(log2N)。接口差异由于存在重复键值multimap中没有重载operator[]操作需要使用insert进行插入。3.2 multimap 使用演示intmain(){multimapstring,stringdict;dict.insert(make_pair(left,左));dict.insert(make_pair(left,左边));dict.insert(make_pair(left,左侧));autoitdict.begin();while(it!dict.end()){coutit-firstit-secondendl;it;}return0;}4. 题库实战在算法竞赛中map和set是处理离散化、频次统计的核心工具。实战一前 K 个高频单词利用map统计每个单词出现的次数将相同次数的单词放在multiset中排序后提取。classSolution{public:classCompare{public:// 在set中进行排序时的比较规则booloperator()(constpairstring,intleft,constpairstring,intright){returnleft.secondright.second;}};vectorstringtopKFrequent(vectorstringwords,intk){mapstring,intm;for(size_t i0;iwords.size();i){(m[words[i]]);}multisetpairstring,int,Comparems(m.begin(),m.end());setstrings;size_t count0;size_t leftCountk;vectorstringret;for(autoe:ms){if(!s.empty()){if(count!e.second){if(s.size()leftCount){ret.insert(ret.end(),s.begin(),s.end());leftCount-s.size();s.clear();}else{break;}}}counte.second;s.insert(e.first);}for(autoe:s){if(0leftCount)break;ret.push_back(e);leftCount--;}returnret;}};实战二随机链表的复制/* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val _val; next NULL; random NULL; } }; */classSolution{public:Node*copyRandomList(Node*head){if(headnullptr)returnnullptr;// 使用 map 构建 原节点, 新节点 的映射关系mapNode*,Node*nodeMap;// 第一次遍历创建出所有新节点并记录在 map 中Node*curhead;while(cur!nullptr){nodeMap[cur]newNode(cur-val);curcur-next;}// 第二次遍历根据 map 中的映射关系精准还原 next 和 random 指针curhead;while(cur!nullptr){nodeMap[cur]-nextnodeMap[cur-next];nodeMap[cur]-randomnodeMap[cur-random];curcur-next;}// 返回新链表的头节点returnnodeMap[head];}};(其他相关经典题目推荐两个数组的交集、给一个链表判断是否有环。)5. map 进阶深度剖析仿函数与空间配置器在应对高强度的 C/C 算法竞赛或从事底层数据结构开发时仅仅停留在接口层面的增删改查是远远不够的。想要进一步压榨性能必须深入理解map的后两个隐藏模板参数。5.1 深度剖析自定义比较器仿函数的多维排序map完整的模板声明其实是std::mapKey, Allocator Compare, T,。这里的Compare默认是std::lessKey。深度分析默认的std::less只能处理内置类型或重载了运算符的结构体。但在实际复杂业务或竞赛如扫描线算法、事件驱动引擎中我们往往需要实现多级权重的自动排序。深挖手写仿函数让map支持自定义结构体作为 Key是高级开发必备技能。仿函数Functor本质上是一个重载了operator()的类或结构体。相比于传递普通的函数指针仿函数的最大优势在于它可以在编译期被内联展开 (inline)从而省去函数调用的栈帧开销在百万级数据插入排序时能显著降低常数时间。代码演示多维权重排序structTaskKey{intpriority;intcreateTime;};// 自定义仿函数structTaskCompare{booloperator()(constTaskKeya,constTaskKeyb)const{// 多维排序逻辑优先级大的在前面如果优先级相同创建时间早的在前面if(a.priority!b.priority){returna.priorityb.priority;}returna.createTimeb.createTime;}};intmain(){// 将自定义的 TaskCompare 作为第三个模板参数传入mapTaskKey,string,TaskComparetaskMap;taskMap[{1,100}]Task A;taskMap[{2,50}]Task B;return0;}5.2 深度剖析空间配置器Allocator与内存碎片优化map的第四个模板参数是Allocator空间配置器它决定了红黑树节点是如何申请和释放内存的。深度分析红黑树是一种基于节点的动态数据结构。频繁向map中insert和erase会产生大量的小块内存碎片。每次new节点都会触发操作系统的系统调用不仅会导致内存空间利用率下降还会由于物理内存不连续引发严重的 CPU Cache Miss极大地拖慢运行速度。深挖Allocator了解 STL 的空间配置器机制比如 SGI STL 的二级内存池是向资深 C 开发者迈进的关键标志。SGI STL 的二级配置器在申请小于 128 Bytes 的内存时会直接从内部维护的 16 条自由链表Free List中获取避免了直接调用malloc带来的额外开销。学会在特殊场景下挂载自定义的内存池Memory Pool / Arena Allocator给map供电可以将离散的小内存分配转化为大块内存的整取零存。比如在算法竞赛中为了防止动态分配内存导致 TLETime Limit Exceeded可以自己写一个静态数组模拟的内存池作为Allocator喂给map达到极致的运行速度。附录基于红黑树的 map 封装实现map的底层就是红黑树因此在map中直接封装一棵红黑树然后将其接口包装下即可。通过底层的Insert返回值pairIterator, bool巧妙地实现了operator[]的逻辑。namespacebite{templateclassK,classVclassmap{typedefpairK,VValueType;// 作用将value中的key提取出来structKeyOfValue{constKoperator()(constValueTypev){returnv.first;}};typedefRBTreeK,ValueType,KeyOfValueRBTree;public:typedeftypenameRBTree::Iterator iterator;public:map(){}// Iteratoriteratorbegin(){return_t.Begin();}iteratorend(){return_t.End();}// Capacitysize_tsize()const{return_t.Size();}boolempty()const{return_t.Empty();}// Acess (巧妙复用底层的 Insert)Voperator[](constKkey){return(*(_t.Insert(ValueType(key,V()))).first).second;}// Modifypairiterator,boolinsert(constValueTypedata){return_t.Insert(data);}voidclear(){_t.Clear();}iteratorfind(constKkey){return_t.Find(key);}private:RBTree _t;};}
