跳到主要内容C++ STL map 核心解析:从底层原理到 LeetCode 实战 | 极客日志C++算法
C++ STL map 核心解析:从底层原理到 LeetCode 实战
C++ STL map 是底层基于红黑树的关联式容器,支持 O(log N) 操作且按键自动排序。其键值对特性、构造遍历、增删查改及 operator[] 用法,对比 multimap 差异,并通过随机链表复制与前 K 个高频单词案例展示实战价值。掌握 map 能显著简化复杂逻辑,是 C++ 开发者必备技能。
黑客帝国1 浏览 在 C++ STL 容器中,map 是兼具高效查找与键值映射能力的关联式容器。它底层基于红黑树实现,支持 O(log N) 级别的增删查改操作,且会按键(Key)自动排序。本文将从 map 的核心概念切入,结合实操代码,详细讲解其构造、增删查改、迭代器遍历等基础操作,对比 map 与 multimap 的差异,并通过 LeetCode 案例展示实战价值。
一. map 核心概念:键值对与红黑树底层
1.1 什么是 map?
map 是一种'键值对(Key-Value)'容器,每个元素包含一个不可修改的键(Key)和一个可修改的值(Value)。底层通过红黑树(平衡二叉搜索树)组织数据,因此具备两个核心特性:
- 键唯一:相同的 Key 无法重复插入;
- 自动排序:遍历时元素会按 Key 的升序(默认用
less<Key> 比较)排列。
1.2 关键类型定义
map 的模板参数与内部类型需重点理解,直接影响使用方式:
template<class Key,
class T,
class Compare = less<Key>,
class Alloc = allocator<pair<const Key, T>>>
class map;
typedef pair<const Key, T> value_type;
typedef Key key_type;
typedef T mapped_type;
value_type:map 存储的是 pair<const Key, T> 类型,其中 Key 被 const 修饰,意味着不能通过迭代器修改 Key(会破坏红黑树结构),但可以修改 T(Value);
Compare:默认用 less<Key> 实现升序,若需降序,可传入 greater<Key>(如 map<int, int, greater<int>>)。
二. map 基础操作:构造、遍历与增删查改
2.1 构造与初始化
map 支持多种构造方式,包括默认构造、迭代器区间构造、初始化列表构造等,实际开发中初始化列表构造最常用:
#include <iostream>
#include <map>
#include <string>
using namespace std;
void test_map1() {
map<string, string> dict1;
map<string, string> dict2 = {
{"sort", "排序"},
{"left", "左边"},
{"right", "右边"}
};
map<string, string> dict3(dict2.begin(), dict2.end());
map<string, string> dict4(dict3);
cout << "dict2 初始化结果:" << endl;
for (const auto& [k, v] : dict2) {
cout << k << ":" << v << endl;
}
}
int main() {
test_map1();
return 0;
}
注意:遍历结果按 Key 升序排列(left < right < sort,按 ASCII 码比较),体现 map 自动排序特性。
2.2 迭代器遍历
map 的迭代器是双向迭代器,支持 ++/-- 操作,遍历方式包括'迭代器循环''范围 for''结构化绑定',其中结构化绑定(C++17+)最简洁:
void test_map2() {
map<string, string> dict = {
{"sort", "排序"},
{"left", "左边"},
{"right", "右边"},
{"string", "字符串"},
{"map", "地图,映射"}
};
map<string, string>::iterator it = dict.begin();
while (it != dict.end()) {
cout << it->first << ":" << it->second << endl;
if (it->first == "left") {
it->second = "左边(修改后)";
}
++it;
}
cout << endl;
for (const auto& e : dict) {
cout << e.first << ":" << e.second << endl;
}
cout << endl;
for (const auto& [k, v] : dict) {
cout << k << ":" << v << endl;
}
}
核心细节:map 的 iterator 和 const_iterator 都不能修改 Key,但 iterator 可以修改 Value;若只需读取,优先用 const auto& 传引用,避免拷贝开销。
2.3 插入操作(insert)
map 的 insert 接口用于插入键值对,返回 pair<iterator, bool>,其中:
iterator:指向插入成功的新节点,或已存在的相同 Key 节点;
bool:true 表示插入成功,false 表示 Key 已存在、插入失败。
insert 支持多种插入形式,实际开发中推荐'初始化列表'和'make_pair',以及多参数隐式类型转换:
void test_map3() {
map<string, string> dict;
pair<string, string> kv1("sort", "排序");
dict.insert(kv1);
dict.insert(pair<string, string>("left", "左边"));
dict.insert(make_pair("right", "右边"));
dict.insert({"move", "移动"});
dict.insert({{"map", "映射"},{"erase", "删除"}});
auto ret = dict.insert({"left", "左边(重复插入)"});
if (!ret.second) {
cout << "Key 'left' 已存在,当前值:" << ret.first->second << endl;
}
for (const auto& [k, v] : dict) {
cout << k << ":" << v << endl;
}
}
int main() {
test_map3();
return 0;
}
2.4 查找与删除(find/erase)
find(Key):查找指定 Key,返回指向该 Key 的迭代器;若不存在,返回 end()(O(log N) 效率);
count(Key):返回 Key 的出现次数(map 中 Key 唯一,故返回 0 或 1,可间接用于查找)。
erase 支持三种删除形式:删除指定迭代器、删除指定 Key、删除迭代器区间,其中'删除迭代器'需先通过 find 确认 Key 存在,避免删除 end() 崩溃:
void test_map4() {
map<string, string> dict = {
{"sort", "排序"},
{"left", "左边"},
{"right", "右边"}
};
auto pos = dict.find("left");
if (pos != dict.end()) {
cout << "找到 Key 'left',值:" << pos->second << endl;
dict.erase(pos);
cout << "删除 Key 'left' 后:" << endl;
for (const auto& [k, v] : dict) {
cout << k << ":" << v << endl;
}
}
size_t del_cnt = dict.erase("right");
cout << "删除 Key 'right',影响个数:" << del_cnt << endl;
dict.erase(dict.begin(), dict.end());
cout << "删除所有元素后,map 大小:" << dict.size() << endl;
}
int main() {
test_map4();
return 0;
}
2.5 核心特性:operator[] 的多功能性
map 的 operator[] 是最灵活的接口,兼具'插入、查找、修改'三种功能,其内部实现依赖 insert,逻辑如下:
mapped_type& operator[](const key_type& k) {
pair<iterator, bool> ret = insert({k, mapped_type()});
return ret.first->second;
}
基于此实现,operator[] 可灵活应对不同场景:
void test_map5() {
map<string, int> countMap;
string arr[] = {"苹果", "西瓜", "苹果", "西瓜", "苹果", "香蕉"};
for (const auto& fruit : arr) {
countMap[fruit]++;
}
cout << "水果统计结果:" << endl;
for (const auto& [fruit, cnt] : countMap) {
cout << fruit << ":" << cnt << endl;
}
cout << endl;
map<string, string> dict;
dict["insert"];
cout << "插入 'insert' 后,值:" << dict["insert"] << endl;
dict["left"] = "左边";
dict["left"] = "左边(修改后)";
cout << "修改 'left' 后,值:" << dict["left"] << endl;
cout << "查找 'left',值:" << dict["left"] << endl;
dict.at("left") = "左边(at 修改)";
}
int main() {
test_map5();
return 0;
}
关键区别:operator[] 在 Key 不存在时会插入默认值,而 at() 会抛异常;若需'严格查找'(不存在时不插入),优先用 find;若需'统计次数''快速赋值',优先用 operator[]。
三. map 与 multimap 的差异
multimap 是 map 的'兄弟容器',底层同样基于红黑树,但核心差异是支持 Key 冗余(相同 Key 可重复插入),由此导致接口和使用场景不同:
| 特性 | map | multimap |
|---|
| Key 唯一性 | 唯一(重复插入失败) | 不唯一(支持重复 Key) |
| operator[] | ✅ 支持(插入 / 查找 / 修改) | ❌不支持(Key 冗余,无法确定修改哪个) |
| find(Key) | 返回唯一 Key 的迭代器 | 返回中序遍历的第一个 Key 迭代器 |
| count(Key) | 返回 0 或 1 | 返回 Key 的实际出现次数 |
| erase(Key) | 删除唯一 Key(返回 0 或 1) | 删除所有相同 Key(返回删除个数) |
void test_multimap() {
multimap<string, string> dict;
dict.insert({"right", "右边"});
dict.insert({"left", "左边"});
dict.insert({"right", "右边 xx"});
dict.insert({"right", "右边"});
for (const auto& [k, v] : dict) {
cout << k << ":" << v << endl;
}
cout << endl;
}
int main() {
test_multimap();
return 0;
}
四. map 实战:LeetCode 经典案例
map 的核心价值在于'高效键值映射'和'自动排序',在算法题中可简化复杂逻辑,以下是两个典型案例:
4.1 随机链表的复制
数据结构初阶阶段,为了控制随机指针,我们将拷贝结点链接在原节点的后面解决,后面拷贝节点还得解下来链接,非常麻烦。这里我们直接让{原结点,拷贝结点}建立映射关系放到 map 中,控制随机指针会非常简单方便,这里体现了 map 在解决一些问题时的价值,完全是降维打击。
class Solution {
public:
Node* copyRandomList(Node* head) {
map<Node*, Node*> NodeMap;
Node* copyhead = nullptr, *copytail = nullptr;
Node* cur = head;
while (cur) {
if (copyhead == nullptr) {
copyhead = copytail = new Node(cur->val);
} else {
copytail->next = new Node(cur->val);
copytail = copytail->next;
}
NodeMap.insert({cur, copytail});
cur = cur->next;
}
cur = head;
Node* copy = copyhead;
while (cur) {
if (cur->random == nullptr)
copy->random = nullptr;
else
copy->random = NodeMap[cur->random];
cur = cur->next;
copy = copy->next;
}
return copyhead;
}
};
4.2 前 k 个高频单词
本题目我们利用 map 统计出次数以后,返回的答案应该按单词出现频率由高到低排序,有一个特殊要求,如果不同的单词有相同出现频率,按字典顺序排序。
解决思路 1:
用排序找前 k 个单词,因为 map 中已经对 key 单词排序过,也就意味着遍历 map 时,次数相同的单词,字典序小的在前面,字典序大的在后面。那么我们将数据放到 vector 中用一个稳定的排序就可以实现上面特殊要求,但是 sort 底层是快排,是不稳定的,所以我们要用 stable_sort,他是稳定的。
class Solution {
public:
struct kv_pair {
bool operator()(const pair<string, int>& x, const pair<string, int>& y) {
return x.second > y.second;
}
};
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());
stable_sort(v.begin(), v.end(), kv_pair());
vector<string> ret;
for (size_t i = 0; i < k; i++) {
ret.push_back(v[i].first);
}
return ret;
}
};
解决思路 2:(两种方法,两种容器)
将 map 统计出的次数的数据放到 vector 中排序,或者放到 priority_queue 中来选出前 k 个。利用仿函数强行控制次数相等的,字典序小的在前面。
class Solution {
public:
struct kv_pair {
bool operator()(const pair<string, int>& x, const pair<string, int>& y) {
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(), kv_pair());
vector<string> ret;
for (size_t i = 0; i < k; i++) {
ret.push_back(v[i].first);
}
return ret;
}
};
class Solution {
public:
struct kv_pair {
bool operator()(const pair<string, int>& x, const pair<string, int>& y) {
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]++;
}
priority_queue<pair<string, int>, vector<pair<string, int>>, kv_pair> q(CountMap.begin(), CountMap.end());
vector<string> ret;
for (size_t i = 0; i < k; i++) {
ret.push_back(q.top().first);
q.pop();
}
return ret;
}
};
结语
map 系列容器是 C++ STL 中'键值映射'场景的核心工具,map 的键唯一、multimap 的键冗余特性,精准适配不同业务需求,底层红黑树更是保障了 O(log N) 的高效操作。从 operator[] 的多功能统计,到结构化绑定的简洁遍历,再到算法题中简化复杂逻辑的实战价值,它既降低了开发复杂度,又兼顾了性能与易用性。掌握其使用细节与场景适配,能为日常开发和算法实现提供有力支撑,是 C++ 开发者必备的容器技能。
相关免费在线工具
- 加密/解密文本
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
- Gemini 图片去水印
基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印,支持批量处理与下载。 在线工具,Gemini 图片去水印在线工具,online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
- Markdown转HTML
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online
- HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online