C++算法
深入解剖STL map/multimap：接口使用与核心特性详解
STL map/multimap 容器基于红黑树实现，提供 key/value 搜索能力。文章详细解析了 map 的类模板声明、构造、迭代器及增删查改接口，重点阐述 operator[] 集插入查找修改于一体的特性，并对比 multimap 在 key 重复场景下的差异。结合词频统计、随机链表复制及 TopK 问题等实战案例，展示了 map 在键值映射场景中的高效应用与最佳实践。
STL map/multimap 容器基于红黑树实现，提供 key/value 搜索能力。文章详细解析了 map 的类模板声明、构造、迭代器及增删查改接口，重点阐述 operator[] 集插入查找修改于一体的特性，并对比 multimap 在 key 重复场景下的差异。结合词频统计、随机链表复制及 TopK 问题等实战案例，展示了 map 在键值映射场景中的高效应用与最佳实践。
前文我们学习了 set 和 multiset，它们是 key 搜索场景的关联式容器。本章讲解的 map 和 multimap 是 key/value 搜索场景的关联式容器，底层同样基于红黑树实现。
核心区别：
pair<key, value> 键值对，通过 key 快速映射到 valuetemplate <class Key,
class T,
class Compare = less<Key>,
class Alloc = allocator<pair<const Key, T>>>
class map;
模板参数说明：
Key：键值的类型，map 中 key 是唯一的T：映射值的类型，通过 key 映射到 valueCompare：比较仿函数，默认 less<Key>（按 key 升序）Alloc：空间配置器，一般使用默认底层特性：
map 底层红黑树节点中存储的是 pair<const Key, T> 键值对。pair 是一个模板结构体，将两个数据组合成一个单元：
typedef pair<const Key, T> value_type;
template <class T1, class T2>
struct pair {
typedef T1 first_type;
typedef T2 second_type;
T1 first; // 第一个数据（key）
T2 second; // 第二个数据（value）
// 默认构造
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) {}
};
// make_pair 函数模板：自动推导类型，简化 pair 对象创建
template <class T1, class T2>
inline pair<T1, T2> make_pair(T1 x, T2 y) {
return pair<T1, T2>(x, y);
}
接口说明：
first：访问键值 key（const 属性，不可修改）second：访问映射值 value（可修改）make_pair()：最推荐的 pair 创建方式，自动类型推导{key, value}：C++11 初始化列表语法，最简洁// 1. 无参默认构造
explicit map(const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
// 2. 迭代器区间构造
template <class InputIterator>
map(InputIterator first, InputIterator last,
const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
// 3. 拷贝构造
map(const map& x);
// 4. initializer_list 构造（最常用）
map(initializer_list<value_type> il,
const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
// 正向迭代器（双向迭代器）
iterator begin(); // 返回指向最小 key 的迭代器
iterator end(); // 返回尾后迭代器
// 反向迭代器
reverse_iterator rbegin(); // 返回指向最大 key 的迭代器
reverse_iterator rend(); // 返回反向尾后迭代器
// const 迭代器
const_iterator cbegin() const;
const_iterator cend() const;
const_reverse_iterator crbegin() const;
const_reverse_iterator crend() const;
迭代器特性：
++、-- 操作// 单个数据插入，返回 pair<迭代器，是否成功>
pair<iterator, bool> insert(const value_type& val);
// 列表插入，已存在的 key 不会插入
void insert(initializer_list<value_type> il);
// 迭代器区间插入
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
接口说明：
insert() 的参数必须是 pair<const Key, T> 类型pair<iterator, bool>：
first：指向已存在元素或新插入元素的迭代器second：true 表示插入成功，false 表示 key 已存在// 查找 key，返回迭代器，未找到返回 end()
iterator find(const key_type& k);
// 查找 key 的个数（map 中只能是 0 或 1）
size_type count(const key_type& k) const;
接口说明：
find()：O(logN) 效率，通过返回的迭代器可以修改 valuecount()：返回值 0 或 1，常用于存在性判断// 删除迭代器位置的值
iterator erase(const_iterator position);
// 删除 key，返回删除个数（0 或 1）
size_type erase(const key_type& k);
// 删除迭代器区间
iterator erase(const_iterator first, const_iterator last);
// 返回 >= k 的第一个元素的迭代器
iterator lower_bound(const key_type& k);
const_iterator lower_bound(const key_type& k) const;
// 返回 > k 的第一个元素的迭代器
iterator upper_bound(const key_type& k);
const_iterator upper_bound(const key_type& k) const;
// 返回 pair<lower_bound, upper_bound>
pair<iterator, iterator> equal_range(const key_type& k);
pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
map 支持修改 value，不支持修改 key。通过 find() 返回的迭代器或遍历时的迭代器，可以直接修改 second 成员：
auto it = dict.find("left");
if (it != dict.end()) {
it->second = "左边、剩余"; // 修改 value
// it->first = "right"; // 错误！不能修改 key
}
接口说明：
operator[] 是 map 最强大、最常用的接口，集插入、查找、修改于一身：
mapped_type& operator[](const key_type& k);
内部实现原理：
mapped_type& operator[](const key_type& k) {
// 1. 调用 insert：如果 k 不存在，插入 {k, mapped_type()}
// 如果 k 存在，插入失败，返回已存在节点的迭代器
pair<iterator, bool> ret = insert({k, mapped_type()});
// 2. 无论插入成功还是失败，ret.first 都指向 k 所在的节点
iterator it = ret.first;
// 3. 返回 value 的引用
return it->second;
}
三种场景：
| 场景 | key 状态 | operator[] 行为 | 返回值 |
|---|---|---|---|
| 插入 | 不存在 | 插入 {key, value 默认构造} | value 的引用 |
| 修改 | 已存在 | 返回已存在 value 的引用 | value 的引用 |
| 查找 | 已存在 | 返回已存在 value 的引用 | value 的引用 |
使用样例：
map<string, string> dict;
dict["insert"]; // 1. 插入：key 不存在，插入{"insert", ""}
dict["left"] = "左边"; // 2. 插入 + 修改：插入{"left", "左边"}
dict["left"] = "左边、剩余"; // 3. 修改：key 已存在，修改 value
std::cout << dict["left"]; // 4. 查找：key 已存在，返回 value
接口讲解：
本示例演示 map 的构造、遍历和插入操作。map 的遍历按 key 升序进行，插入时需构造 pair 对象，共四种构造方式，其中初始化列表最简洁。已存在的 key 插入会失败。
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
// 1. initializer_list 构造（最常用）
map<string, string> dict = {
{"left", "左边"},
{"right", "右边"},
{"insert", "插入"},
{"string", "字符串"}
};
// 2. 迭代器遍历（按 key 升序）
auto it = dict.begin();
while (it != dict.end()) {
// 方式 1：解引用后访问成员
// cout << (*it).first << ":" << (*it).second << endl;
// 方式 2：箭头运算符（最常用）
// 第一个->是迭代器重载，返回 pair*；第二个->是结构指针访问成员
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
// 3. 插入 pair 的 4 种方式（对比学习）
pair<string, string> kv1("first", "第一个"); // 方式 1：命名对象
dict.insert(kv1);
dict.insert(pair<string, string>("second", "第二个")); // 方式 2：匿名对象
dict.insert(make_pair("sort", "排序")); // 方式 3：make_pair（推荐）
dict.insert({"auto", "自动的"}); // 方式 4：初始化列表（最简洁）
// 4. key 已存在，插入失败（即使 value 不同）
dict.insert({"left", "左边，剩余"});
// 5. 范围 for 遍历
for (const auto& e : dict) {
cout << e.first << ":" << e.second << endl;
}
cout << endl;
// 6. 查找演示
string str;
while (cin >> str) {
auto ret = dict.find(str); // O(logN) 查找
if (ret != dict.end()) {
cout << "->" << ret->second << endl;
} else {
cout << "无此单词，请重新输入" << endl;
}
}
return 0;
}
输出结果（部分）：
insert:插入 left:左边 right:右边 string:字符串 auto:自动的 first:第一个 insert:插入 left:左边 right:右边 second:第二个 sort:排序 string:字符串
接口讲解：
本示例演示传统方式统计词频：使用 find() 查找元素是否存在。不存在则插入 {单词，1}，存在则通过迭代器修改 value（ret->second++）。这种方式逻辑清晰，但代码稍显冗长。
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
// 利用 find 和 iterator 修改功能，统计水果出现的次数
string arr[] = {"苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉"};
map<string, int> countMap;
for (const auto& str : arr) {
// 1. 查找水果在不在 map 中
auto ret = countMap.find(str);
if (ret == countMap.end()) {
// 2. 不存在：第一次出现，插入 {水果，1}
countMap.insert({str, 1});
} else {
// 3. 存在：通过迭代器修改 value（次数 +1）
ret->second++;
}
}
// 遍历输出（按 key 升序：苹果、西瓜、香蕉）
for (const auto& e : countMap) {
cout << e.first << ":" << e.second << endl;
}
cout << endl;
return 0;
}
输出结果：
苹果:6 西瓜:3 香蕉:2
接口讲解：
本示例演示 operator[] 的优雅用法。countMap[str]++ 一句代码完成了插入 + 查找 + 修改三个功能：
{str, 0}，返回 value 引用，++ 后变为 1这是 map 最经典的用法，代码极其简洁高效。
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
// 利用 [] 插入 + 修改功能，巧妙实现统计水果出现的次数
string arr[] = {"苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉"};
map<string, int> countMap;
for (const auto& str : arr) {
// [] 先查找水果在不在 map 中
// 1、不在：插入 {水果，0}，返回次数的引用，++ 后变成 1
// 2、在：返回水果对应次数的引用，++ 后次数 +1
countMap[str]++;
}
for (const auto& e : countMap) {
cout << e.first << ":" << e.second << endl;
}
cout << endl;
return 0;
}
输出结果：
苹果:6 西瓜:3 香蕉:2
接口讲解：
本示例集中演示 operator[] 的四种使用场景：插入空值、插入 + 修改、修改、查找。理解这个例子就掌握了 map 最核心的操作技巧。
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
map<string, string> dict;
// 1. 插入 pair 对象（传统方式）
dict.insert(make_pair("sort", "排序"));
// 2. [] 插入空值
// key 不存在 -> 插入 {"insert", string()} （value 默认构造为空字符串）
dict["insert"];
// 3. [] 插入 + 修改
// key 不存在 -> 插入 {"left", "左边"}
dict["left"] = "左边";
// 4. [] 修改
// key 已存在 -> 修改 value 为"左边、剩余"
dict["left"] = "左边、剩余";
// 5. [] 查找
// key 已存在 -> 返回 value 的引用
cout << dict["left"] << endl; // 输出：左边、剩余
// 验证 insert 结果
for (const auto& e : dict) {
cout << e.first << ":" << e.second << endl;
}
return 0;
}
输出结果：
左边、剩余 insert: left:左边、剩余 sort:排序
| 特性 | map | multimap |
|---|---|---|
| 键值冗余 | ❌ 不支持（key 唯一） | ✅ 支持（key 可重复） |
| insert | key 存在时插入失败 | 总是成功 |
| find | 返回任意位置 | 返回中序第一个 |
| count | 返回 0 或 1 | 返回实际个数 |
| erase(val) | 删除 0 或 1 个 | 删除所有匹配 key 的元素 |
| operator[] | ✅ 支持 | ❌ 不支持 |
接口说明：
multimap 与 map 的接口基本一致，主要差异点：
operator[]：因为 key 可重复，[] 无法确定返回哪个 value 的引用find() 返回中序遍历的第一个匹配元素count() 返回实际重复个数erase(key)删除所有匹配 key 的元素#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
// multimap：支持 key 重复
multimap<string, string> authors = {
{"鲁迅", "狂人日记"},
{"余华", "活着"},
{"鲁迅", "朝花夕拾"},
{"余华", "许三观卖血记"},
{"村上春树", "挪威的森林"}
};
// 遍历（按 key 有序，相同 key 连续存放）
for (const auto& e : authors) {
cout << e.first << ":" << e.second << endl;
}
cout << endl;
// find 返回中序第一个
auto pos = authors.find("鲁迅");
if (pos != authors.end()) {
cout << "鲁迅的第一部作品：" << pos->second << endl;
}
// count 返回实际个数
cout << "鲁迅作品数：" << authors.count("鲁迅") << endl;
// erase(key) 删除所有匹配项
authors.erase("余华");
for (const auto& e : authors) {
cout << e.first << ":" << e.second << endl;
}
return 0;
}
输出结果：
村上春树：挪威的森林 鲁迅：狂人日记 鲁迅：朝花夕拾 余华：活着 余华：许三观卖血记
鲁迅的第一部作品：狂人日记
鲁迅作品数：2
村上春树：挪威的森林 鲁迅：狂人日记 鲁迅：朝花夕拾
接口讲解：
本示例展示 map 在复杂链表拷贝中的妙用。传统方法需要将拷贝节点链接在原节点后，非常繁琐。使用 map 建立原节点→拷贝节点的映射关系，处理 random 指针时直接通过 nodeMap[cur->random] O(logN) 获取对应拷贝节点，降维打击。
class Solution {
public:
Node* copyRandomList(Node* head) {
// 1. 建立原节点 -> 拷贝节点的映射
map<Node*, Node*> nodeMap;
Node* copyhead = nullptr;
Node* copytail = nullptr;
Node* cur = head;
// 2. 第一次遍历：拷贝 next 指针链，同时建立映射
while (cur) {
if (copytail == nullptr) {
copyhead = copytail = new Node(cur->val);
} else {
copytail->next = new Node(cur->val);
copytail = copytail->next;
}
// 存储映射关系
nodeMap[cur] = copytail;
cur = cur->next;
}
// 3. 第二次遍历：处理 random 指针
cur = head;
Node* copy = copyhead;
while (cur) {
if (cur->random == nullptr) {
copy->random = nullptr;
} else {
// O(logN) 查找原节点 random 对应的拷贝节点
copy->random = nodeMap[cur->random];
}
cur = cur->next;
copy = copy->next;
}
return copyhead;
}
};
算法复杂度：
接口讲解：
本示例要求按频率降序返回前 K 个单词，频率相同则按字典序升序。map 已按 key（单词）字典序排序，因此相同频率的单词在遍历时已经是字典序升序。使用稳定的排序算法 stable_sort 可以保持这一相对顺序。
class Solution {
public:
struct Compare {
// 按频率降序
bool operator()(const pair<string, int>& x, const pair<string, int>& y) const {
return x.second > y.second;
}
};
vector<string> topKFrequent(vector<string>& words, int k) {
// 1. map 统计词频（自动按单词字典序排序）
map<string, int> countMap;
for (auto& e : words) {
countMap[e]++;
}
// 2. 将 map 数据拷贝到 vector 中
vector<pair<string, int>> v(countMap.begin(), countMap.end());
// 3. 稳定排序：频率降序，相同频率保持字典序（因为 map 已排序）
stable_sort(v.begin(), v.end(), Compare());
// 4. 取前 k 个
vector<string> strV;
for (int i = 0; i < k; ++i) {
strV.push_back(v[i].first);
}
return strV;
}
};
接口讲解：
本解法将频率降序和字典序升序两个规则合并到一个仿函数中，直接用 sort 排序。仿函数逻辑：频率高的排前面；频率相同时，字典序小的排前面。
class Solution {
public:
struct Compare {
bool operator()(const pair<string, int>& x, const pair<string, int>& y) const {
// 频率降序，或频率相等时字典序升序
return x.second > y.second || (x.second == y.second && x.first < y.first);
}
};
vector<string> topKFrequent(vector<string>& words, int k) {
map<string, int> countMap;
for (auto& e : words) {
countMap[e]++;
}
vector<pair<string, int>> v(countMap.begin(), countMap.end());
// 仿函数控制排序规则
sort(v.begin(), v.end(), Compare());
vector<string> strV;
for (int i = 0; i < k; ++i) {
strV.push_back(v[i].first);
}
return strV;
}
};
接口讲解：
本解法使用优先级队列（堆）来选出前 K 个高频单词。需要注意的是，priority_queue 的仿函数与 sort 相反：sort 的 Compare 返回 true 表示前者应在前；priority_queue 的 Compare 返回 true 表示前者优先级低（即大堆需要 < 比较）。
class Solution {
public:
struct Compare {
bool operator()(const pair<string, int>& x, const pair<string, int>& y) const {
// 优先级队列：大堆要实现小于比较
// 频率低优先级低，字典序大优先级低
return x.second < y.second || (x.second == y.second && x.first > y.first);
}
};
vector<string> topKFrequent(vector<string>& words, int k) {
map<string, int> countMap;
for (auto& e : words) {
countMap[e]++;
}
// 将 map 中的<单词，次数>放到 priority_queue 中
// 仿函数控制大堆：频率高的在堆顶，频率相同时字典序小的在堆顶
priority_queue<pair<string, int>, vector<pair<string, int>>, Compare> p(countMap.begin(), countMap.end());
vector<string> strV;
for (int i = 0; i < k; ++i) {
strV.push_back(p.top().first);
p.pop();
}
return strV;
}
};
| 容器 | 底层结构 | key 唯一性 | key 有序性 | 修改 value | 修改 key | operator[] |
|---|---|---|---|---|---|---|
| map | 红黑树 | ✅ 唯一 | ✅ 升序 | ✅ 支持 | ❌ 禁止 | ✅ 支持 |
| multimap | 红黑树 | ❌ 可重复 | ✅ 升序 | ✅ 支持 | ❌ 禁止 | ❌ 不支持 |
核心要点：
pair<const Key, T>find() 返回迭代器，可通过迭代器修改 valuefind() 返回中序第一个，erase(key) 删除所有匹配项
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online