csp信奥赛C++标准模板库STL（6）：map和multimap的使用详解-深圳市維司達科技有限公司

csp信奥赛C++标准模板库STL（6）：map和multimap的使用详解

1. 基本概念

map（映射）

定义：关联容器，存储键值对(key-value pairs)
特点：每个键(key)必须是唯一的
内部实现：通常使用红黑树（有序）或哈希表（无序）
时间复杂度：大多数操作O(log n)

multimap（多重映射）

定义：关联容器，存储键值对
特点：允许重复的键(key)
内部实现：通常使用红黑树
时间复杂度：大多数操作O(log n)

2. 基本用法

头文件

#include<map>// 包含map和multimap#include<iostream>#include<string>

创建和初始化

// map的创建map<int,string>studentMap;map<string,int>scoreMap={{"Alice",95},{"Bob",87}};// multimap的创建multimap<int,string>groupMap;multimap<string,int>scoreMultiMap;

3. 常用操作对比

操作	map	multimap
插入键值对	`insert()`或`operator[]`	`insert()`
查找键	`find()`返回一个迭代器	`find()`返回第一个匹配的迭代器
计数	`count()`返回0或1	`count()`返回键出现的次数
删除	`erase(key)`删除所有该键	`erase(key)`删除所有该键
访问元素	`operator[]`可直接访问	不能使用`operator[]`

4. 详细使用示例

4.1 map的基本操作

#include<iostream>#include<map>#include<string>usingnamespacestd;intmain(){// 创建mapmap<string,int>ageMap;// 插入元素 - 三种方法ageMap.insert({"Alice",20});// 方法1ageMap.insert(make_pair("Bob",22));// 方法2ageMap["Charlie"]=19;// 方法3// 访问元素cout<<"Alice's age: "<<ageMap["Alice"]<<endl;cout<<"Bob's age: "<<ageMap.at("Bob")<<endl;// 查找元素autoit=ageMap.find("Charlie");if(it!=ageMap.end()){cout<<"Found: "<<it->first<<" -> "<<it->second<<endl;}// 遍历mapcout<<"\nAll elements:"<<endl;for(constauto&pair:ageMap){cout<<pair.first<<": "<<pair.second<<endl;}// 使用迭代器遍历cout<<"\nUsing iterator:"<<endl;for(autoit=ageMap.begin();it!=ageMap.end();++it){cout<<it->first<<": "<<it->second<<endl;}// 删除元素ageMap.erase("Bob");// 检查大小cout<<"\nSize after erase: "<<ageMap.size()<<endl;return0;}

4.2 multimap的基本操作

#include<iostream>#include<map>#include<string>usingnamespacestd;intmain(){// 创建multimapmultimap<string,string>phonebook;// 插入元素 - 允许重复键phonebook.insert({"Alice","123-4567"});phonebook.insert({"Alice","987-6543"});// 同一个人的第二个电话phonebook.insert({"Bob","555-1234"});phonebook.insert({"Alice","111-2222"});// 同一个人的第三个电话// 统计键出现的次数cout<<"Alice has "<<phonebook.count("Alice")<<" phone numbers"<<endl;// 查找所有匹配的键 - 重要！cout<<"\nAll of Alice's phone numbers:"<<endl;autorange=phonebook.equal_range("Alice");for(autoit=range.first;it!=range.second;++it){cout<<it->first<<": "<<it->second<<endl;}// 遍历所有元素cout<<"\nAll entries:"<<endl;for(constauto&entry:phonebook){cout<<entry.first<<": "<<entry.second<<endl;}// 删除特定键的所有值intremoved=phonebook.erase("Alice");cout<<"\nRemoved "<<removed<<" entries for Alice"<<endl;return0;}

5. 在信奥赛(CSP)中的常见应用

5.1 统计频率

// 统计数组中每个数字出现的次数vector<int>nums={1,2,3,2,1,3,3,4,2};map<int,int>freq;for(intnum:nums){freq[num]++;// 如果键不存在会自动创建，值为0}for(constauto&p:freq){cout<<p.first<<": "<<p.second<<" times"<<endl;}

5.2 字符串到ID的映射

// 常用于图论题目中，将字符串节点名映射为数字IDmap<string,int>m;intidCounter=0;vector<string>names={"Beijing","Shanghai","Guangzhou","Shenzhen"};for(constauto&name:names){if(m.find(name)==m.end()){m[name]=idCounter++;}}// 现在可以用数字ID代替字符串进行操作

5.3 排序和去重

// map自动按键排序，可以利用这个特性map<int,string>m;m[3]="Three";m[1]="One";m[2]="Two";// 遍历时自动按key升序排列for(constauto&p:m){cout<<p.first<<": "<<p.second<<endl;}// 输出：// 1: One// 2: Two// 3: Three

5.4 使用multimap实现一对多关系

// 学生选课系统：一个老师可以教多个课程multimap<string,string>m;m.insert({"Wang","Math"});m.insert({"Wang","Physics"});m.insert({"Li","Chemistry"});m.insert({"Li","Biology"});m.insert({"Wang","Computer Science"});// 查询Wang老师的所有课程cout<<"Wang's courses:"<<endl;autorange=m.equal_range("Wang");for(autoit=range.first;it!=range.second;++it){cout<<"- "<<it->second<<endl;}

6. 高级用法和技巧

6.1 自定义比较函数

// 降序排列的mapstructCompareDesc{booloperator()(constint&a,constint&b)const{returna>b;// 降序}};map<int,string,CompareDesc>descMap;descMap[1]="One";descMap[2]="Two";descMap[3]="Three";for(constauto&p:descMap){cout<<p.first<<": "<<p.second<<endl;}// 输出：// 3: Three// 2: Two// 1: One

6.2 复杂键类型

// 使用pair作为键map<pair<int,int>,string>gridMap;gridMap[{1,2}]="Position (1,2)";gridMap[{3,4}]="Position (3,4)";// 查找autopos=make_pair(1,2);if(gridMap.find(pos)!=gridMap.end()){cout<<gridMap[pos]<<endl;}

7. 性能注意事项

时间复杂度：
- 插入：O(log n)
- 查找：O(log n)
- 删除：O(log n)
空间复杂度：O(n)
适用场景：
- 需要按键排序
- 需要快速查找（二分查找）
- 键值对数量适中（不是极大量）
不适用场景：
- 需要极快查找且不关心顺序：考虑unordered_map（哈希表）
- 只需要存储键：考虑set

总结

map：键唯一，支持operator[]，适合一对一映射
multimap：键可重复，不支持operator[]，适合一对多关系
两者都是有序容器，基于红黑树实现
在CSP竞赛中，合理使用map/multimap可以简化代码并提高效率

掌握map和multimap是C++竞赛编程的重要基础，熟练使用它们能帮助你更高效地解决各种问题。

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

一、CSP信奥赛C++通关学习视频课：
- C++语法基础
- C++语法进阶
- C++算法
- C++数据结构
- CSP信奥赛数学
- CSP信奥赛STL
二、CSP信奥赛C++竞赛拿奖视频课：
- 信奥赛csp-j初赛高频考点解析
- CSP信奥赛C++复赛集训课（12大高频考点专题集训）
三、考级、竞赛刷题题单及题解：
- GESP C++考级真题题解
- CSP信奥赛C++初赛及复赛高频考点真题解析
- CSP信奥赛C++一等奖通关刷题题单及题解

详细内容：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

3、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

2025 csp-j 复赛真题及答案解析（最新更新）
2025 csp-x(山东) 复赛真题及答案解析（最新更新）
2025 csp-x(河南) 复赛真题及答案解析（最新更新）
2025 csp-x(辽宁) 复赛真题及答案解析（最新更新）
2025 csp-x(江西) 复赛真题及答案解析（最新更新）
2025 csp-x(广西) 复赛真题及答案解析（最新更新）
2020 ~ 2024 csp 复赛真题题单及题解
2019 ~ 2022 csp-j 初赛高频考点真题分类解析
2021 ~ 2024 csp-s 初赛高频考点解析
2023 ~ 2024 csp-x (山东)初赛真题及答案解析
2024 csp-j 初赛真题及答案解析
2025 csp-j 初赛真题及答案解析（最新更新）
2025 csp-s 初赛真题及答案解析（最新更新）
2025 csp-x (山东)初赛真题及答案解析(最新更新)
2025 csp-x (江西)初赛真题及答案解析(最新更新)
2025 csp-x (辽宁)初赛真题及答案解析(最新更新)

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

129 道刷题练习和详细题解，涉及：模拟算法、数学思维、二分算法、前缀和、差分、深搜、广搜、DP专题、树和图

4、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}

csp信奥赛C++标准模板库STL（6）：map和multimap的使用详解