【C++】map 与 multimap

map官方使用文档

multimap官方使用文档

在 C++ STL 中，map和multimap是最常用的树形关联式容器。它们底层均由红黑树（平衡二叉搜索树）实现，能够提供高效的O ( l o g 2 N ) O(log_2 N)O(log2​N)检索效率。本文将全面深入剖析这两种容器的特性、接口用法、高频算法实战，并在第 5 部分深度探讨仿函数与空间配置器，最后在附录中展示其底层的红黑树封装实现。

1. 关联式容器与键值对简介

与vector、list等序列式容器不同，关联式容器里面存储的是<key, value>结构的键值对，在数据检索时效率更高。

在 C++ 中，键值对通常通过std::pair结构体来表示。它包含两个成员变量：first代表键值（key），second代表与 key 对应的信息（value）。

2. map 容器详解

2.1 map 核心特性

1. 键值对存储：map存储的元素是由键值key和映射值value组合而成的键值对。
2. Key 的唯一性与不可变性：map中的key是唯一的，并且不能修改。
3. 自动排序：默认按照小于的方式对key进行比较。
4. 有序序列：map中的元素如果用迭代器去遍历，可以得到一个有序的序列。
5. 底层结构：map的底层为平衡搜索树（红黑树），查找效率比较高，时间复杂度为O ( l o g 2 N ) O(log_2 N)O(log2​N)。

2.2 map 的常用接口与代码实战

map提供了丰富的接口用于状态管理、数据增删及区间查找。以下为核心接口的高频使用场景代码示例：

#include<iostream>#include<map>#include<string>usingnamespacestd;intmain(){map<int,string>m;// --- 1. 5种 map 定义的方式 ---//定义有名对象pair<string,string>p("char","字符");map<string,string>m;m.insert(p);//匿名对象m.insert(pair<string,string>("int","整型");//make_pair-自动识别插入的类型m.insert(make_pair("folat","浮点型"));//InputIteratormap<string,string>m1={{"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)){cout<<"Key 2 存在"<<endl;}// --- 4. 边界迭代器查找---// lower_bound: 返回第一个 >= 2 的元素的迭代器autoit_low=m.lower_bound(2);// upper_bound: 返回第一个 > 2 的元素的迭代器autoit_up=m.upper_bound(2);cout<<"lower_bound(2): "<<it_low->second<<endl;// --- 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 的四种方式

map<string,string>::iterator it=m1.begin();while(it!=m1.end()){// 1. 解引用cout<<(*it).first<<":"<<(*it).second<<endl;// 2. 使用重载 operator->cout<<it->first<<":"<<it->second<<endl;++it;}cout<<endl;// 3. 范围for (最推荐的现代 C++ 写法)for(constauto&e:m1){cout<<e.first<<":"<<e.second<<endl;}cout<<endl;// 4. C++17 以后支持的结构化绑定写法for(auto&[x,y]:m1){cout<<x<<":"<<y<<endl;}cout<<endl;

2.4 数据查找

使用find接口可以高效查找元素，找不到则返回end()。

string str;while(cin>>str){autoret=m.find(str);if(ret!=m.end()){cout<<ret->first<<":"<<ret->second<<endl;}else{cout<<"没有这个单词！"<<endl;}}

2.5 核心利器：operator[]

operator[]是map中极为强大且常用的操作符，其实际进行的是插入+查找。

intmain(){map<string,string>dict;//插入+修改：先插入一个<"left","">,然后查找key，再修改成<"left","左边">dict["left"]="左边";//修改dict["left"]="左边，剩余";//key存在-> 查找cout<<dict["left"]<<endl;//key不存在-> 插入<"insert" ,"">cout<<dict["insert"]<<endl;return0;}

可用于极其精简地计数：

intmain(){string arr[]={"苹果","香蕉","梨子","香蕉","梨子","香蕉","梨子","香蕉","梨子"};map<string,int>countMap;for(constauto&e:arr){// 利用 operator[] 进行极简计数countMap[e]++;}for(constauto&e:countMap){cout<<e.first<<":"<<e.second<<endl;}return0;}

3. multimap 容器详解

multimap允许数据冗余，没有operator[]。

3.1 multimap 核心特性

1. 允许键值重复：与map的区别是，multimap中的元素key可以重复。
2. 底层结构与效率：multimap底层结构也是二叉搜索树（红黑树），找某个元素的时间复杂度为O ( l o g 2 N ) O(log_2 N)O(log2​N)。
3. 接口差异：由于存在重复键值，multimap中没有重载operator[]操作，需要使用insert进行插入。

3.2 multimap 使用演示

intmain(){multimap<string,string>dict;dict.insert(make_pair("left","左"));dict.insert(make_pair("left","左边"));dict.insert(make_pair("left","左侧"));autoit=dict.begin();while(it!=dict.end()){cout<<it->first<<"："<<it->second<<endl;it++;}return0;}

4. 题库实战

在算法竞赛中，map和set是处理离散化、频次统计的核心工具。

实战一：

前 K 个高频单词

利用map统计每个单词出现的次数，将相同次数的单词放在multiset中排序后提取。

classSolution{public:classCompare{public:// 在set中进行排序时的比较规则booloperator()(constpair<string,int>&left,constpair<string,int>&right){returnleft.second>right.second;}};vector<string>topKFrequent(vector<string>&words,intk){map<string,int>m;for(size_t i=0;i<words.size();++i){++(m[words[i]]);}multiset<pair<string,int>,Compare>ms(m.begin(),m.end());set<string>s;size_t count=0;size_t leftCount=k;vector<string>ret;for(auto&e: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;}}}count=e.second;s.insert(e.first);}for(auto&e:s){if(0==leftCount)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(head==nullptr)returnnullptr;// 使用 map 构建 <原节点, 新节点> 的映射关系map<Node*,Node*>nodeMap;// 第一次遍历：创建出所有新节点，并记录在 map 中Node*cur=head;while(cur!=nullptr){nodeMap[cur]=newNode(cur->val);cur=cur->next;}// 第二次遍历：根据 map 中的映射关系，精准还原 next 和 random 指针cur=head;while(cur!=nullptr){nodeMap[cur]->next=nodeMap[cur->next];nodeMap[cur]->random=nodeMap[cur->random];cur=cur->next;}// 返回新链表的头节点returnnodeMap[head];}};

(其他相关经典题目推荐：两个数组的交集、给一个链表判断是否有环。)

5. map 进阶深度剖析：仿函数与空间配置器

在应对高强度的 C/C++ 算法竞赛或从事底层数据结构开发时，仅仅停留在接口层面的增删改查是远远不够的。想要进一步压榨性能，必须深入理解map的后两个隐藏模板参数。

5.1 深度剖析：自定义比较器（仿函数）的多维排序

map完整的模板声明其实是std::map<Key, Allocator Compare, T,>。这里的Compare默认是std::less<Key>。

深度分析：

默认的std::less只能处理内置类型或重载了<运算符的结构体。但在实际复杂业务或竞赛（如扫描线算法、事件驱动引擎）中，我们往往需要实现多级权重的自动排序。深挖手写仿函数，让map支持自定义结构体作为 Key，是高级开发必备技能。

仿函数（Functor）本质上是一个重载了operator()的类或结构体。相比于传递普通的函数指针，仿函数的最大优势在于它可以在编译期被内联展开 (inline)，从而省去函数调用的栈帧开销，在百万级数据插入排序时，能显著降低常数时间。

代码演示（多维权重排序）：

structTaskKey{intpriority;intcreateTime;};// 自定义仿函数structTaskCompare{booloperator()(constTaskKey&a,constTaskKey&b)const{// 多维排序逻辑：优先级大的在前面，如果优先级相同，创建时间早的在前面if(a.priority!=b.priority){returna.priority>b.priority;}returna.createTime<b.createTime;}};intmain(){// 将自定义的 TaskCompare 作为第三个模板参数传入map<TaskKey,string,TaskCompare>taskMap;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供电，可以将离散的小内存分配转化为大块内存的整取零存。比如在算法竞赛中，为了防止动态分配内存导致 TLE（Time Limit Exceeded），可以自己写一个静态数组模拟的内存池作为Allocator喂给map，达到极致的运行速度。

附录：基于红黑树的 map 封装实现

map的底层就是红黑树，因此在map中直接封装一棵红黑树，然后将其接口包装下即可。通过底层的Insert返回值（pair<Iterator, bool>），巧妙地实现了operator[]的逻辑。

namespacebite{template<classK,classV>classmap{typedefpair<K,V>ValueType;// 作用：将value中的key提取出来structKeyOfValue{constK&operator()(constValueType&v){returnv.first;}};typedefRBTree<K,ValueType,KeyOfValue>RBTree;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)V&operator[](constK&key){return(*(_t.Insert(ValueType(key,V()))).first).second;}// Modifypair<iterator,bool>insert(constValueType&data){return_t.Insert(data);}voidclear(){_t.Clear();}iteratorfind(constK&key){return_t.Find(key);}private:RBTree _t;};}