1. 先从查表这个需求说起map 到底在解决什么问题写业务代码写得久了你会发现有一类需求反复出现给一个编号要找出它对应的名字给一个用户 ID要拿到他的积分给一个字符串要统计它出现过多少次。这类需求的本质都是拿着一个键去换一个值也就是查表。数组能干这事但前提是键必须是连续的整数下标一旦键变成字符串、变成稀疏的大整数、变成自定义结构体数组就立刻哑火了你会被迫写一堆线性扫描代码臃肿不说性能还随着数据量线性劣化。C 标准库里的STL map就是为这类场景准备的。它是一个有序的键值对容器你去查一个键它能给你对应的值平均时间复杂度是对数级别数据量翻十倍查找次数只多几次这个特性在工程里非常值钱。更重要的是map 内部按照键的大小排好序了所以你不仅能查还能找比某个键大的第一个元素遍历某一段范围内的所有键值对这些能力在数组和哈希表里要么没有要么很别扭。这篇东西我打算写给两类人看。一类是刚学完 C 基础语法、听说 map 很好用但一直没搞明白它和数组到底差在哪的朋友另一类是已经会用 map、但踩过坑——比如遍历时删除元素崩了、自定义结构体做键编译不过、明明用好几个函数却能跑但说不清为什么的人。我会从它底层是个什么东西讲起把插入、查找、删除、遍历这些操作一个个拆开配上能直接复制编译的代码最后把我这些年真金白银踩出来的坑整理成速查表。不聊虚的全是能落地的内容。2. 底层结构决定了它的脾气红黑树给了我们什么2.1 为什么不是一棵普通的二叉搜索树很多人第一次听说 map 底层是平衡二叉树就跳过了觉得这是面试八股。其实这个结构直接决定了你写代码时该做什么、不该做什么值得花几分钟讲透。最朴素的二叉搜索树有个致命问题它长成什么样完全取决于你的插入顺序。你按 1、2、3、4、5 的顺序插入它就会退化成一条向右的链子查找从 O(log n) 变成 O(n)等于白搭。红黑树做的事情就是在每次插入和删除之后通过旋转和重新染色把树的高度强行压在 2 倍 log₂(n) 以内。这意味着无论你以什么顺序塞数据进去查找代价都不会失控。注意红黑树的平衡是近似平衡不是严格平衡。它只保证最长路径不超过最短路径的两倍换来的是插入删除时更少的旋转次数。这是工程上的取舍不是理论上的最优。对你写代码的实际影响有三条。第一插入顺序不影响性能你可以放心按业务数据的自然顺序往里塞。第二每个节点的结构里除了键和值还要存父指针、左右孩子指针和颜色标记一个节点轻轻松松吃掉 32 到 48 字节比它存的数据本身大得多。第三所有元素在内存里是分散的不是连续排布所以顺序遍历时的缓存命中率远不如 vector。2.2 有序性带来的真实好处map 的键始终按比较规则有序这一条衍生出一批非常好用的操作是哈希表给不了的。lower_bound(key)返回第一个键不小于 key 的位置用来做找第一个大于等于的目标。upper_bound(key)返回第一个键严格大于 key 的位置。equal_range(key)一次拿到上面两个迭代器组成一个区间。begin() 到 end() 的顺序遍历天然是按键从小到大不需要额外排序。拿一个具体场景说。你在做一个日志系统要查询2024-03-01 到 2024-03-15 之间所有记录的条数。如果用哈希表你只能把整个表遍历一遍去判断。用 map时间戳做键lower_bound 定位起点upper_bound 定位终点中间这段就是答案代价是两个对数级查找。2.3 复杂度账要算清楚操作平均复杂度说明插入 insert / emplaceO(log n)需要定位插入点再平衡查找 find / countO(log n)从根走到叶子删除 erase(key)O(log n)先查找再平衡下标访问 operator[]O(log n)内部就是一次插入尝试顺序遍历全部元素O(n)中序遍历本身很便宜内存占用每节点约 32~48 字节开销这是 map 最大的隐性成本看到这张表你要建立一个直觉n 等于十万的时候log₂(100000) 大约是 17。也就是说一次查找最多比较十几次这比很多人想象的少得多。但反过来如果你只有十几个元素map 的查找未必比 vector 从头扫一遍快因为 vector 是连续内存CPU 缓存友好而 map 每比较一次就是一次随机内存访问可能触发缓存未命中。数据量小、又不需要有序性的时候别急着上 map。3. 从声明到删除map 的基础操作全流程3.1 头文件、定义与初始化先看最基本的骨架。std::map定义在map头文件里模板参数至少两个键类型和值类型。#include map #include string #include iostream int main() { // 空 map std::mapstd::string, int score; // 初始化列表C11 起可用 std::mapstd::string, int init { {alice, 90}, {bob, 85}, {carol, 95} }; // 拷贝构造 std::mapstd::string, int copy(init); // 从其他容器的迭代器区间构造 std::mapstd::string, int range(init.begin(), init.end()); return 0; }这里有个细节值得提前说清楚map的value_type是std::pairconst Key, T注意那个const。键一旦放进去就不能改因为改键等于破坏整棵树的有序结构。所以你不能写it-first newkey编译器会直接拦下来。但it-second是可以随便改的值随便你更新。3.2 插入的四种姿势性能差别不小这是新手最容易糊弄过去、实际上最该搞明白的地方。第一种operator[]。score[dave] 77; // 键不存在先默认构造一个 int(0)再赋值为 77 int v score[eve]; // 键不存在插入 {eve, 0}并返回 0operator[]的行为是不存在就插入默认值。这带来两个后果一它要求值类型可以默认构造如果值是某个没有默认构造函数的类这行代码编译不过二你只是想查一下结果莫名其妙往表里塞了一堆键这在调试的时候非常难发现。第二种insert。auto ret score.insert({frank, 88}); if (ret.second) { std::cout 插入成功\n; } else { std::cout 键已存在值保持不变原值是 ret.first-second \n; }insert的返回值是pairiterator, boolsecond告诉你到底插没插进去。这是一个非常关键的语义差异如果键已经存在insert什么都不做不会覆盖原来的值也不会报错。很多人的 bug 就出在这——以为 insert 是写入实际上它是不存在才写入。第三种emplaceC11。score.emplace(grace, 91);emplace直接在容器内部原地构造元素省掉了先造一个临时 pair 再拷贝进去的开销。对于值类型比较重的场景比如值是长字符串或大对象emplace通常比insert更划算。但它也有坑参数是直接转发给构造函数 的如果你的参数类型对不上报错信息会长得让人怀疑人生。第四种insert_or_assignC17。score.insert_or_assign(frank, 99); // 存在就覆盖不存在就插入这个接口解决的就是我想无条件写入的需求语义比insert清楚得多。如果你的编译器支持 C17需要覆盖语义时优先用它。3.3 遍历迭代器和范围 forfor (auto it score.begin(); it ! score.end(); it) { std::cout it-first it-second \n; } // C11 范围 for for (const auto kv : score) { std::cout kv.first kv.second \n; } // C17 结构化绑定写起来最舒服 for (const auto [name, sc] : score) { std::cout name sc \n; }三点提醒。第一const auto里的引用别省auto kv会把整个 pair 拷贝一份值是字符串的时候白白多一次分配。第二想改值就写auto kv但记住kv.first依然是只读的。第三遍历顺序永远是按键从小到大不是插入顺序这一点和 Python 的 dict 不一样别搞混。3.4 查找和删除// 查找 auto it score.find(alice); if (it ! score.end()) { std::cout 找到 it-second \n; } // 只想知道在不在 if (score.count(alice)) { /* ... */ } // 删除按迭代器C11 起返回下一个有效迭代器 it score.find(bob); if (it ! score.end()) { it score.erase(it); } // 删除按 key返回删除的元素个数map 里只可能是 0 或 1 size_t n score.erase(carol); // 删除按区间 score.erase(score.begin(), score.end());注意遍历过程中删除元素必须用it m.erase(it);的写法。写成m.erase(it); it;是未定义行为因为我删完之后it已经指向一块被释放的内存再自增就是在垃圾数据上走指针。这个错误在测试环境经常看起来没事到线上数据量大一点就随机崩。4. 键类型和比较器绕开那堵编译报错的墙4.1 键为什么必须可比较map 要维护有序结构就必须能在任意两个键之间比较大小。默认情况下它用std::lessKey也就是调用operator。所以 int、double、string 这些内置支持的类型直接就能当键而你自己定义的结构体不行编译器会抛出一大串模板错误核心信息就一句no match for operator。4.2 自定义结构体做键的两种写法写法一重载operator。struct Point { int x, y; bool operator(const Point o) const { if (x ! o.x) return x o.x; return y o.y; } }; std::mapPoint, std::string labels; labels[Point{1, 2}] 起点;写法二传一个独立的比较器。struct Cmp { bool operator()(const Point a, const Point b) const { return a.x b.x || (a.x b.x a.y b.y); } }; std::mapPoint, std::string, Cmp labels;第二种写法更通用因为它不改动 Point 本身的定义一个结构体可以配不同的比较规则。C20 之后无捕获的 lambda 也能直接用作模板参数写起来更省事auto cmp [](const Point a, const Point b) { return a.x b.x || (a.x b.x a.y b.y); }; std::mapPoint, std::string, decltype(cmp) labels(cmp);注意比较器必须满足严格弱序。简单说就是小于关系要自洽不能出现 a b 和 b a 同时成立也不能出现 a b、b c 但 a 不小于 c 的情况。最常见的错误是比较函数用而不是。用了map 认为两个相等的键互相小于插入第二个相同键的时候就会破坏树结构表现是元素丢失、遍历死循环或者直接崩溃。4.3 指针和浮点数做键的陷阱拿指针当键map 默认比较的是地址的大小不是指针指向内容的大小。如果你的业务语义是按内容去重那必须自己写比较器去解引用比较否则同一个对象的两份拷贝会被当成两个不同的键去重完全失效。浮点数当键更微妙。0.1 0.2 ! 0.3这个经典问题在 map 里会直接导致查不到。因为查不到很多人第一反应是 bug 出在 map实际上是浮点精度。真要用通常得先量化成整数比如把金额按分存成long long。5. 实战场景map 在真实问题里的几种用法5.1 词频统计最经典的入门场景#include map #include string #include sstream #include iostream int main() { std::string text the quick brown fox jumps over the lazy dog the fox; std::mapstd::string, int freq; std::istringstream iss(text); std::string word; while (iss word) { freq[word]; // 不存在则插入 0 再自增存在则直接自增 } for (const auto [w, c] : freq) { std::cout w : c \n; } }freq[word]这一行浓缩了operator[]的全部特性不存在就默认构造 0 然后加一存在就直接加一。写起来确实优雅但要意识到它有个副作用——即使某个词后续处理中被跳过只要执行到这一行表里就会多一个条目。如果统计过程中有大量查询但不该插入的操作这种写法会污染数据那时候要用find配合手动插入。5.2 离散化把大范围的值压缩成小下标这是算法题里 map 出镜率最高的场景之一。给你一万个数值域是 1 到 10⁹你想拿它们做数组下标或者线段树下标显然不能开这么大的数组。做法是先把所有出现过的值收集起来排序去重然后每个值对应它在有序序列里的位置。#include map #include vector #include algorithm std::vectorint values {1000000000, 5, 999999999, 5, 42}; std::mapint, int idx; for (int v : values) idx[v] 0; // 用 map 天然去重 排序 int cur 0; for (auto [v, i] : idx) i cur; // 依次编号 // 现在 idx[5] 就是一个很小的下标用 map 做这件事代码量最少代价是常数比排序 unique lower_bound的数组方案大一些。数据量在十万以内基本感觉不到差别超过百万就建议换成数组方案。5.3 配置表、路由表和轻量缓存工程里 map 一个很实际的用途是当小规模的静态映射表。比如把状态枚举映射到字符串enum class Status { Pending, Running, Done, Failed }; const std::mapStatus, std::string kStatusName { {Status::Pending, pending}, {Status::Running, running}, {Status::Done, done}, {Status::Failed, failed} }; std::string to_string(Status s) { auto it kStatusName.find(s); return it kStatusName.end() ? unknown : it-second; }注意我把它声明成了const。const map 不能用operator[]因为operator[]有插入语义和 const 矛盾所以查表只能用find。这个限制其实是个好事逼着你写更明确的代码。5.4 和 vector 组合做区间维护有些场景需要维护一堆互不重叠的区间比如 IP 段归属、时间片占用。用mapint, int存区间起点 - 区间终点天然按起点有序插入新区间时用lower_bound找到位置检查是否和相邻区间重叠重叠就合并。这个模式在内存管理、任务调度里都很常见核心就是把 map 的有序性当成一个可以二分查找的骨架来用。6. 常见问题与排查技巧实录6.1 编译期报错速查报错关键词真实原因解决办法no match for operator键类型没有定义operator或传自定义比较器passing const std::map as this argument discards qualifiers在 const map 上用了operator[]改用findno matching function for call to pair(...)值类型不可默认构造被operator[]要求了改用insert或emplaceassignment of read-only member试图修改it-first键不可改删了重插no viable overloaded 用了自定义比较器但没在构造函数里传实例构造时传入比较器对象6.2 运行期异常几个真踩过的坑坑一遍历时删除没接返回值。前面提过再说一遍是因为它太常见。判断标准很简单只要循环体里出现了删除就必须写成it m.erase(it);然后continue或者用else分支别让循环头的it再执行一次。坑二比较器里改了外部状态。有人图省事在比较器里读一个全局变量来影响排序运行中又去改这个变量。结果整棵树的有序性被破坏之后的所有查找都可能返回错误结果而且不报错极难定位。比较器必须是纯函数只依赖参数。坑三用size()和int混着比较。for (int i 0; i m.size(); i) { /* ... */ }size()返回的是无符号类型当m为空时理论上存在有符号无符号比较的隐患很多编译器只给个警告。养成写size_t或者直接用范围 for 的习惯能省掉这类噪音。坑四以为 map 的迭代器删除后会全部失效。事实是删除一个元素只让指向它的迭代器失效其他迭代器依然有效。这和 vector 完全不同。所以你在遍历 map 时删除当前元素是安全的只要按上面说的方式接住返回值。6.3 性能上的那些反直觉第一小数据量下 map 不一定比 vector 快前面算过连续内存的缓存优势在小规模时非常明显。我做过一个粗糙的对比大概几百个元素以内vector 线性查找和 map 的差距不明显有时还更快。第二operator[]和insert在键不存在的情况下代价接近但在键已存在的情况下operator[]还是要走一次完整的查找没有便宜可占。第三map 的节点分配是逐个 new 出来的构造一个几十万元素的 map分配器会承受很大压力。如果数据是静态的、构建后不再变动可以考虑先放进 vector 再批量插入或者评估 unordered_map 是不是更合适。提示如果你需要构建后只读、查询极多的结构除了 map 和 unordered_map还可以考虑构建完成后把所有 pair 拷进一个排好序的 vector然后用 lower_bound 查询。查询同样是对数级内存连续缓存友好实际经常更快。7. 再往前一步multimap、unordered_map 和现代接口7.1 multimap键可以重复的版本std::multimap允许一个键对应多个值典型用途是一个分类下挂多条记录。它有两点必须知道。首先multimap 没有operator[]。这很合理键不唯一m[key]该返回哪一个其次查找要用equal_range而不是find因为find返回的是若干相同键中的某一个不保证是第一个。std::multimapstd::string, int mm; mm.insert({a, 1}); mm.insert({a, 2}); mm.insert({a, 3}); auto [lo, hi] mm.equal_range(a); for (auto it lo; it ! hi; it) { std::cout it-second \n; // 1 2 3插入顺序在这个实现里通常保持 }需要提醒的是标准并不保证相同键之间维持插入顺序上面这个例子的输出顺序在多数实现上是稳定的但你不能把业务逻辑建立在它之上。7.2 unordered_map什么时候它更合适如果不需要有序性只关心给我键换值unordered_map通常是更好的选择。它底层是哈希表平均查找 O(1)常数比红黑树小。代价是元素无序最坏情况大量哈希冲突会退化到 O(n)而且每次扩容都要重哈希。选择逻辑我总结成一句话要范围查询或者要求遍历有序用 map只要精确查找、数据量大、键的哈希好写用 unordered_map。还有一点差别unordered_map 要求键类型提供哈希函数和相等比较自定义结构体做键的时候比 map 多一份工作。7.3 C17 之后的几个实用接口第一组是节点操作。extract可以把一个节点从容器里摘出来而不销毁它insert可以把节点原封不动地装进另一个容器中间不发生元素的拷贝或移动。做容器之间搬数据的时候非常省。std::mapint, std::string a {{1, one}, {2, two}}; std::mapint, std::string b; auto node a.extract(2); // 拿走节点a 中不再有 2 node.key() 20; // 摘出来的节点可以改键 b.insert(std::move(node));第二组是try_emplace。它和emplace的区别在于如果键已经存在try_emplace不会去碰后面的参数不会构造那个临时对象。对于值是重量级对象的场景这个差别能实打实省下开销。第三组是 C20 的contains和erase_if。if (m.contains(key)) { /* ... */ } // 比 m.find(key) ! m.end() 更直白 std::erase_if(m, [](const auto kv) { return kv.second 60; });contains让判断在不在的意图一眼可见erase_if把按条件批量删除从一段手写循环压缩成一行。这些接口不难用上了就很难回去。最后聊聊我自己的使用习惯。写业务代码时我基本不用operator[]去查值因为它会偷偷插入而我宁愿多写两行find换来确定性只有在明确要做不存在则计数这类累加操作时才会用它。用自定义结构体做键的时候我一定把比较器单独拎出来写成结构体而不是重载operator这样同一个类型在不同业务场景下可以有不同的排序口径改动面也小。至于普通结构体直接拿比大小这种写法——结构体有补位填充memcmp的结果和成员逐个比较的结果未必一致这事我在项目里见过一次数据错乱才彻底记住。还有一个建议给正在入门的朋友不要把 map 当成更高级的数组去用。数组胜在下标连续、内存紧凑、访问飞快map 胜在键可以是任意类型、可以范围查询、迭代器稳定。选错容器带来的性能损失往往比算法写错还难查因为代码看起来完全正确。