拓冰网站定制 
std::map是 C 里最常被用、也最容易被用错的容器。它的核心事实只有一句话它是一棵自平衡的红黑树red-black tree所以 key 永远有序、查找永远是 O(log n)。有序带来范围查询、中序遍历即排序、find优于std::find这些能力但也带来一个著名陷阱operator[]在找不到 key 时会默默插入一个默认值。这篇按「结构 → 只读查表 → 查找写法 → 插入写法 → 范围查询 → 完整示例」的顺序把 map / set 全家讲清楚。1. 引子查一个不存在的 key容器却变大了先看一段真实代码的实测结果size before 1 inventory[banana] 0 but size becomes 2只是「读一下」banana的数量容器的 size 就从 1 变成了 2。std::map::operator[]的语义不是「查」而是「取引用不存在就插入一个值初始化的元素」。一个常见的 bug 是拿它当判断if (m[key] 0) { ... }每次判断都在往 map 里塞垃圾。要理解为什么会这样得先知道 map 底下是什么。2. 红黑树有序和 O(log n) 是同一个来源std::mapKey, T不是哈希表也不是普通二叉树而是红黑树一种每个节点多带一位颜色的自平衡二叉搜索树binary search tree。红黑树red-black tree一棵自平衡的二叉搜索树每个节点多一位颜色 ┌───────────────┐ │ 黑 50 │ 根永远是黑 └──┬─────────┬──┘ ┌──────┘ └──────┐ ┌──────┴──────┐ ┌──────┴──────┐ │ 红 30 │ │ 黑 70 │ └──┬───────┬──┘ └──┬───────┬──┘ ┌────┘ └────┐ ┌─────┘ └─────┐ ┌────┴───┐ ┌─────┴──┐ │ ... │ ... │ 黑 20 │ │ 黑 40 │ └────────┘ └────────┘ 五条约束教科书版本 ① 节点非红即黑 ② 根是黑 ③ 叶子NIL 空节点都是黑 ④ 红节点的孩子必须是黑不能连续两个红 ⑤ 从任一节点到它所有后代 NIL 的路径上黑节点个数相同黑高相等 由 ④⑤ 推出最长路径 2 x 最短路径 树高 O(log n)。 所以查找、插入、删除都是 O(log n)而且是「保证的」上界 不是平均情况 —— 这一点和下面要讲的 unordered_map 正好相反。 插入/删除破坏了 ①②④⑤ 时用「旋转rotation 重新着色recolor」 修回来每次只需常数次调整代价已经算在 O(log n) 里。 中序遍历这棵树取出的是20 30 40 50 70 ... —— 天然有序。这就是 map/set 能提供 lower_bound/upper_bound 的原因。注意最后一行「有序」不是 map 额外维护的一个属性而是树结构的副产品。你插入 30、50、20、70、40中序遍历永远是 20 30 40 50 70和插入顺序无关。红黑树的具体实现和旋转细节不必背记住两条就够用key 有序、树高被保证在 O(log n)。map 家族有四个成员区别只在「允不允许重复」容器重复元素有序性查找典型用途std::mapK, V不允许重复 key按 key 升序可用比较器改O(log n)键值映射、需要有序遍历或范围查询std::setK不允许重复升序O(log n)去重 有序遍历std::multimapK, V允许重复 key有序O(log n)一对多分数→姓名、索引倒排std::multisetK允许重复有序O(log n)有序袋、滑动窗口中位数// map_basic.cpp — 编译: g -stdc17 -Wall -O2 map_basic.cpp -o map_basic #include iostream #include map #include set #include string int main() { std::mapstd::string, int ages; ages[alice] 30; ages[bob] 25; ages[carol] 35; std::cout map iteration (sorted by key):; for (const auto [name, age] : ages) std::cout name age; std::cout \n; // insert 返回 pairiterator, boolbool 说明到底插进去了没有 const auto [it1, inserted1] ages.insert({dave, 40}); const auto [it2, inserted2] ages.insert({bob, 99}); std::cout insert dave: inserted inserted1 value it1-second \n; std::cout insert bob : inserted inserted2 value it2-second \n; std::setint uniq{3, 1, 4, 1, 5, 9, 2, 6}; std::cout set (dedup sorted):; for (int v : uniq) std::cout v; std::cout \nset size uniq.size() \n; std::cout count(4) uniq.count(4) count(7) uniq.count(7) \n; return 0; }map iteration (sorted by key): alice30 bob25 carol35 insert dave: inserted1 value40 insert bob : inserted0 value25 set (dedup sorted): 1 2 3 4 5 6 9 set size 7 count(4) 1 count(7) 0三处细节都值得记住遍历输出是alice bob carol而不是插入顺序红黑树的中序即字典序insert(bob, 99)返回inserted0, value25没有覆盖原来的 25 还在这是insert与operator[]最本质的区别set把重复出现的 1 去掉了并排好序count就是「在不在」的判据。官方文档std::map — cppreference 官方文档std::set — cppreference 官方文档std::multimap — cppreference3. 陷阱一operator[] 找不到就插入operator[]的完整语义是「返回 key 对应 value 的引用key 不存在就先用默认构造塞一个进去再返回它的引用」。所以它有三个后果容器会被改size 变大value 类型必须可默认构造否则编译不过const map上根本不能用它。operator[]在写入场景很好用histogram[word]是标准写法但只读场景必须换 API// map_subscript.cpp — 编译: g -stdc17 -Wall -O2 map_subscript.cpp -o map_subscript #include iostream #include map #include stdexcept #include string int main() { std::mapstd::string, int inventory{{apple, 3}}; std::cout size before inventory.size() \n; const int missing inventory[banana]; // 反例不要这么写读一下就插进去了 std::cout inventory[\banana\] missing but size becomes inventory.size() \n; const auto found inventory.find(cherry); // 只读查询找不到不会改容器 std::cout find(\cherry\) end() ? (found inventory.end()) size inventory.size() \n; try { std::cout inventory.at(cherry) \n; } catch (const std::out_of_range e) { // 异常按引用捕按值抛 std::cout at(\cherry\) threw std::out_of_range: e.what() \n; } const std::mapstd::string, int frozen inventory; std::cout size still frozen.size() \n; return 0; }size before 1 inventory[banana] 0 but size becomes 2 find(cherry) end() ? 1 size 2 at(cherry) threw std::out_of_range: map::at size still 2三种只读写法各有取舍写法找不到时能用在const map上复杂度什么时候用m[key]插入默认值size 1不能O(log n)只在「写」的语义下用如m[k]m.at(key)抛std::out_of_range能O(log n)逻辑上必须存在不存在就是 bugm.find(key)返回end()能O(log n)常规只读查询还要拿 valuem.count(key)返回 0能O(log n)只判断存在性m.contains(key)返回false能O(log n)C20 起可用语义最直白at抛出的异常信息里那句map::at是 libstdc 的实现细节标准只要求抛std::out_of_range没规定what()内容换编译器可能不同不要拿去匹配字符串。官方文档std::map::operator[] — cppreference官方第一句话就写着「若 key 不存在则插入 value_type(key, T())」。 官方文档std::map::at — cppreference 官方文档std::map::containsC20— cppreferenceC20 才有contains在 C17 里用count代替// verify: stdc20 #include map bool has_key(const std::mapint, int table, int key) { return table.contains(key); // 需要 C20C17 写 table.count(key) ! 0 }4. 陷阱二拿 std::find 去查 map「map 的查找快」不是修辞。std::map::find走的是红黑树的搜索路径一次比较就把候选范围砍一半而std::find/std::find_if是从begin()开始逐个线性扫描完全无视树结构。给 map 的 key 装一个计数比较器、再给find_if的谓词装一个计数器就能量出差距// map_find_vs_std_find.cpp — 编译: g -stdc17 -Wall -O2 map_find_vs_std_find.cpp -o map_find_vs_std_find #include algorithm #include cstddef #include iostream #include map struct Stats { inline static std::size_t comparisons 0; // map 内部比较次数 inline static std::size_t predicate_calls 0; // find_if 谓词调用次数 }; struct Key { int id 0; }; struct CountingLess { bool operator()(const Key a, const Key b) const { Stats::comparisons; return a.id b.id; } }; constexpr int N 1000; int main() { std::mapKey, int, CountingLess table; for (int i 0; i N; i) table.emplace(Key{i}, i * 10); const Key target{500}; // 正好在中间 Stats::comparisons 0; const auto by_tree table.find(target); const std::size_t tree_cmp Stats::comparisons; Stats::predicate_calls 0; const auto by_scan std::find_if(table.begin(), table.end(), [target](const auto kv) { Stats::predicate_calls; return kv.first.id target.id; }); std::cout keys N \n; std::cout map::find comparisons tree_cmp found (by_tree ! table.end()) \n; std::cout std::find_if calls Stats::predicate_calls found (by_scan ! table.end()) \n; return 0; }keys 1000 map::find comparisons 11 found1 std::find_if calls 501 found1同样是「查一个存在的 key」写法依据复杂度1000 个 key 的实测table.find(k)红黑树搜索路径每次比较砍一半O(log n)11 次比较std::find_if(m.begin(), m.end(), ...)从头部线性扫描O(n)501 次谓词调用11 次比较正好是 log₂(1000) ≈ 10 的量级红黑树最长路径不超过 2log₂(n1)501 次是「目标在中间」的必然结果。规模再大十倍前者只多 34 次后者多十倍。用了 map 却拿std::find去查等于把 O(log n) 亲手降级成 O(n)。官方文档std::map::find — cppreference标注的复杂度就是「与容器大小的对数成正比」。 官方文档std::find_if — cppreference线性扫描的泛型版本。5. 插入 API 选型五种写法构造次数差一倍map 一次性提供了五种「插入或更新」的写法它们的区别全在构造/拷贝/移动的次数以及key 已存在时的行为。用一个自带计数器的 value 类型实测一遍// map_emplace.cpp — 编译: g -stdc17 -Wall -O2 map_emplace.cpp -o map_emplace #include cstddef #include iostream #include map #include string struct WidgetStats { inline static std::size_t default_ctors 0; inline static std::size_t value_ctors 0; inline static std::size_t copies 0; inline static std::size_t moves 0; static void reset() { default_ctors 0; value_ctors 0; copies 0; moves 0; } static std::size_t ctors() { return default_ctors value_ctors; } }; struct Widget { int id 0; Widget() { WidgetStats::default_ctors; } explicit Widget(int v) : id(v) { WidgetStats::value_ctors; } Widget(const Widget other) : id(other.id) { WidgetStats::copies; } Widget(Widget other) noexcept : id(other.id) { WidgetStats::moves; } Widget operator(const Widget other) { id other.id; WidgetStats::copies; return *this; } Widget operator(Widget other) noexcept { id other.id; WidgetStats::moves; return *this; } }; void report(const char* label) { std::cout label ctors WidgetStats::ctors() copies WidgetStats::copies moves WidgetStats::moves \n; } int main() { { std::mapstd::string, Widget m; WidgetStats::reset(); m[a] Widget{1}; // 默认构造一个 移动赋值 report(operator[] ); } { std::mapstd::string, Widget m; WidgetStats::reset(); m.insert({b, Widget{2}}); // 构造临时 pair 再移动进节点 report(insert ); } { std::mapstd::string, Widget m; WidgetStats::reset(); m.emplace(c, 3); // 就地在节点里构造零临时对象 report(emplace ); } { std::mapstd::string, Widget m; WidgetStats::reset(); m.try_emplace(d, 4); // key 不存在才构造C17 report(try_emplace ); } { std::mapstd::string, Widget m; m.emplace(e, 5); WidgetStats::reset(); m.emplace(e, 9); // key 已存在白构造一个再丢掉 report(emplace dup ); std::cout kept m.at(e).id \n; } { std::mapstd::string, Widget m; m.emplace(f, 5); WidgetStats::reset(); m.try_emplace(f, 9); // key 已存在一个对象都不构造 report(try_emplace dup ); std::cout kept m.at(f).id \n; } { std::mapstd::string, Widget m; m.emplace(g, 5); WidgetStats::reset(); m.insert_or_assign(g, Widget{9}); // C17明确要覆盖 report(insert_or_assign); std::cout kept m.at(g).id \n; } return 0; }operator[] ctors2 copies0 moves1 insert ctors1 copies0 moves2 emplace ctors1 copies0 moves0 try_emplace ctors1 copies0 moves0 emplace dup ctors1 copies0 moves0 kept 5 try_emplace dup ctors0 copies0 moves0 kept 5 insert_or_assign ctors1 copies0 moves1 kept 9把这些数字翻译成人话写法key 已存在时构造次数拷贝/移动实测ctors/copies/moves什么时候用m[k] v覆盖2默认构造 赋值1 次移动赋值2 / 0 / 1value 可默认构造且你就是要覆盖m.insert({k, v})忽略boolfalse12 次移动1 / 0 / 2需要「到底插进去了没有」的返回值m.emplace(k, args...)忽略但白构造一个1命中时也构造01 / 0 / 0dup 也是 1新 key 就地构造别对已存在的 key 用m.try_emplace(k, args...)忽略且不构造1命中时 001 / 0 / 0dup 是 0C17 起的新代码首选m.insert_or_assign(k, v)覆盖11 次移动赋值1 / 0 / 1C17语义上明确要覆盖三条结论要「插入已存在就别动」→ 用try_emplace。它是唯一在 key 已存在时连一个对象都不构造的写法实测ctors0而emplace在同样情况下白构造一个Widget再销毁实测ctors1。value 很大或是持有资源文件句柄、unique_ptr时这个差别就是实打实的开销。operator[]的代价是「默认构造 赋值」两次操作实测ctors2 moves1而且要求 value 可默认构造。它在明确的写入场景m[k] v、m[k]够用但不要用它做「不存在才插入」的逻辑。要「覆盖」→ 用insert_or_assign它的意图写在函数名里比m[k] v更明确不过它要求 value可赋值——注意上面代码里写的是Widget{9}直接写9会编译失败因为Widget的单参构造函数是explicit不存在从int到Widget的隐式赋值转换。insert的返回值std::pairiterator, bool值得单独记一笔bool告诉你「到底有没有真的插入」iterator指向「现在那个 key 所在的位置」不管是新插的还是本来就有的。上面第 3 节的insert(bob, 99)输出inserted0就是这个 boole 在起作用。官方文档std::map::emplace — cppreference 官方文档std::map::try_emplace — cppreference 官方文档std::map::insert_or_assign — cppreference还有一条必须记住的map 的 key 是const。value_type是std::pairconst Key, T所以it-second可以改it-first改不了#include map #include string void keys_are_const(std::mapint, std::string m) { auto it m.begin(); it-second value is mutable; // 可以value 非 const // 反例不要这么写编译失败 —— key_type 是 const int // it-first 5; // error: assignment of read-only member }想改 key只能erase再insert这正好也说明为什么 key 不能随便改改了树的有序性就崩了。上面的片段故意不写main()因为它是用来展示编译错误的。6. 范围查询与自定义比较器有序容器真正让人舍不得放弃的能力是范围查询lower_bound第一个 ≥ key、upper_bound第一个 key、equal_range一次拿到两者也就是[lower_bound, upper_bound)。// map_range.cpp — 编译: g -stdc17 -Wall -O2 map_range.cpp -o map_range #include functional #include iostream #include iterator #include map #include string // 踩坑用的比较器只按字符串长度比较 struct ByLength { bool operator()(const std::string a, const std::string b) const { return a.size() b.size(); } }; int main() { std::mapint, std::string m{{10, ten}, {20, twenty}, {30, thirty}, {40, forty}}; const auto lo m.lower_bound(20); // 第一个 20 const auto hi m.upper_bound(30); // 第一个 30 std::cout range [20, 30] :; for (auto it lo; it ! hi; it) std::cout it-first it-second; std::cout \n; const auto [first, last] m.equal_range(30); // 一次拿到上下界 std::cout equal_range(30) count std::distance(first, last) \n; std::mapint, std::string, std::greaterint desc{{10, ten}, {40, forty}, {20, twenty}}; std::cout descending keys:; for (const auto [key, value] : desc) std::cout key; std::cout \n; std::multimapstd::string, int scores{{alice, 80}, {bob, 90}, {alice, 95}}; const auto [af, al] scores.equal_range(alice); std::cout alice scores:; for (auto it af; it ! al; it) std::cout it-second; std::cout \n; std::mapstd::string, int, ByLength by_len; by_len[ab] 1; by_len[cd] 2; // 与 ab 等价长度相同→ 不新增条目 std::cout by_len size by_len.size() key by_len.begin()-first value by_len.begin()-second \n; return 0; }range [20, 30] : 20twenty 30thirty equal_range(30) count 1 descending keys: 40 20 10 alice scores: 80 95 by_len size 1 key ab value 2逐个看[lower_bound(20), upper_bound(30))恰好是[20, 30]下半界是闭、上半界是开所以想要「含 30」就必须用upper_bound(30)而不是lower_bound(30)。这个半开区间约定和 STL 其他算法一致。equal_range一次返回上下界用std::distance数一下就是「这个 key 有几个元素」。map里最多 1 个multimap里可以多个——所以equal_range配multimap最合适示例里 alice 的 80 和 95 都拿到了。换比较器就换了遍历顺序std::greaterint让 key 降序这是「有序」的另一个用法。最后一段是踩坑示范ByLength只比字符串长度于是ab和cd在它眼里等价谁都不小于谁map 认为它们是同一个 key——by_len[cd] 2根本没新增条目只是把ab那格的值改成了 2。输出by_len size 1 key ab value 2证实了这一点。规则自定义比较器必须是一个严格弱序strict weak ordering其中最容易被忽略的一条是「等价必须可传递」——comp(a,b)false comp(b,a)false的两个 key 会被当作同一个 key。只比一部分字段长度、大小写忽略后的样子、float的近似相等是很危险的比较器。默认的std::lessKey即operator在绝大多数场景都是对的。官方文档std::map::lower_bound — cppreference 官方文档std::lower_bound泛型算法— cppreference 官方文档std::less — cppreferencestd::map的默认比较器语义就是operator。7. 完整示例一份有序的成绩单下面这个例子把前面所有要点串起来insert的bool判重、multimap按分数排序取 Top-N、lower_bound/upper_bound做分数区间查询。Key姓名用map保证不重复且有序分数是「一对多」的所以排序输出用multimap。// score_board.cpp — 编译: g -stdc17 -Wall -O2 score_board.cpp -o score_board #include cstddef #include functional #include iostream #include map #include string #include vector class ScoreBoard { public: void add(const std::string name, int score) { const auto [it, inserted] scores_.insert({name, score}); if (!inserted) { it-second score; // 已存在就更新分数key 不可改value 可改 } } std::vectorstd::string top(std::size_t count) const { std::multimapint, std::string, std::greaterint ranked; // 分数从高到低 for (const auto [name, score] : scores_) ranked.insert({score, name}); std::vectorstd::string result; for (const auto [score, name] : ranked) { if (result.size() count) break; result.push_back(name); } return result; } std::vectorstd::string between(int low, int high) const { std::multimapint, std::string sorted; // 默认 less升序才能做区间查询 for (const auto [name, score] : scores_) sorted.insert({score, name}); std::vectorstd::string result; const auto last sorted.upper_bound(high); // 上半界开才包含 high for (auto it sorted.lower_bound(low); it ! last; it) { result.push_back(it-second); } return result; } std::size_t size() const { return scores_.size(); } private: std::mapstd::string, int scores_; // 按人名有序便于查找 }; int main() { ScoreBoard board; board.add(alice, 80); board.add(bob, 95); board.add(carol, 70); board.add(dave, 88); board.add(alice, 92); // 重名 - 更新分数不新增条目 std::cout players board.size() \n; std::cout top 3:; for (const std::string name : board.top(3)) std::cout name; std::cout \n; std::cout score in [80, 95]:; for (const std::string name : board.between(80, 95)) std::cout name; std::cout \n; return 0; }players 4 top 3: bob alice dave score in [80, 95]: dave alice bobplayers 4而不是 5说明重名的 alice 走了「更新」分支top 3按分数降序给出 bob(95)、alice(92)、dave(88)区间查询按分数升序给出 dave(88)、alice(92)、bob(95)。四个容器map/multimap× 两种比较器各司其职。8. 选型速查需求选谁理由键值映射 需要有序遍历std::map红黑树O(log n) 且 key 有序去重 有序std::set同上只存 key一对多且要有序std::multimap/std::multiset允许等价 keyequal_range拿到全部只判断存在性find/countC20 用contains别用operator[]它会插入「不存在才插入」try_emplaceC17命中时不构造任何对象「存在就覆盖」insert_or_assignC17语义明确且返回是否为新插入只需要 O(1) 平均查找、不在乎顺序std::unordered_map哈希表见《unordered_map / unordered_set 完全指南》元素很少十几个std::vector 排序小 N 时线性查找的常数因子比树更低9. 延伸阅读std::map — cppreference接口全貌注意value_type是pairconst Key, T这就是 key 不可改的来源。std::map::operator[] — cppreference官方明确写了「key 不存在时插入 value-initialized 的 value」是第 3 节的依据。std::map::try_emplace — cppreference注意「若 key 已存在则不做任何事」这句是它比emplace省的根源。std::map::lower_bound — cppreference 与 std::map::upper_bound半开区间的官方定义配合equal_range一起看。std::multimap — cppreference等价 key 的相邻性保证同一个 key 的元素在遍历中连续出现。C Core Guidelines — isocpp.github.io容器选型与「别用operator[]做查询」这类接口设计思路的来源。本知识库内的相关篇目《unordered_map / unordered_set 完全指南哈希表、rehash 与自定义哈希》 —— 讲透 std::unordered_map 的哈希表结构——桶数组加链表具体实现由标准库定义《C map 与 unordered_map 怎么选底层结构、复杂度与决策流程》 —— std::map 和 std::unordered_map 接口几乎一样底层却完全不同。《list 与 forward_list链表真的比 vector 快吗》 —— 用计数分配器和实测耗时把 std::list / std::forward_list 的真实开销算清楚10. 一句话总结std::map/std::set是一棵红黑树有序和 O(log n) 是同一套结构的两个结果中序遍历即有序所以有lower_bound/upper_bound/equal_range树高被保证在 O(log n)所以map::find查 1000 个 key 只要 11 次比较而std::find_if要扫 501 次。用之前记住三条operator[]找不到会插入默认值只读查询用find要抛异常用atC20 可contains插入用try_emplace它是唯一在 key 已存在时不构造任何对象的写法emplace会白构造一个key 是const且自定义比较器必须满足严格弱序否则「等价」的 key 会被悄悄吞掉。 map / set 完全指南：红黑树与有序容器
std::map是 C 里最常被用、也最容易被用错的容器。它的核心事实只有一句话它是一棵自平衡的红黑树red-black tree所以 key 永远有序、查找永远是 O(log n)。有序带来范围查询、中序遍历即排序、find优于std::find这些能力但也带来一个著名陷阱operator[]在找不到 key 时会默默插入一个默认值。这篇按「结构 → 只读查表 → 查找写法 → 插入写法 → 范围查询 → 完整示例」的顺序把 map / set 全家讲清楚。1. 引子查一个不存在的 key容器却变大了先看一段真实代码的实测结果size before 1 inventory[banana] 0 but size becomes 2只是「读一下」banana的数量容器的 size 就从 1 变成了 2。std::map::operator[]的语义不是「查」而是「取引用不存在就插入一个值初始化的元素」。一个常见的 bug 是拿它当判断if (m[key] 0) { ... }每次判断都在往 map 里塞垃圾。要理解为什么会这样得先知道 map 底下是什么。2. 红黑树有序和 O(log n) 是同一个来源std::mapKey, T不是哈希表也不是普通二叉树而是红黑树一种每个节点多带一位颜色的自平衡二叉搜索树binary search tree。红黑树red-black tree一棵自平衡的二叉搜索树每个节点多一位颜色 ┌───────────────┐ │ 黑 50 │ 根永远是黑 └──┬─────────┬──┘ ┌──────┘ └──────┐ ┌──────┴──────┐ ┌──────┴──────┐ │ 红 30 │ │ 黑 70 │ └──┬───────┬──┘ └──┬───────┬──┘ ┌────┘ └────┐ ┌─────┘ └─────┐ ┌────┴───┐ ┌─────┴──┐ │ ... │ ... │ 黑 20 │ │ 黑 40 │ └────────┘ └────────┘ 五条约束教科书版本 ① 节点非红即黑 ② 根是黑 ③ 叶子NIL 空节点都是黑 ④ 红节点的孩子必须是黑不能连续两个红 ⑤ 从任一节点到它所有后代 NIL 的路径上黑节点个数相同黑高相等 由 ④⑤ 推出最长路径 2 x 最短路径 树高 O(log n)。 所以查找、插入、删除都是 O(log n)而且是「保证的」上界 不是平均情况 —— 这一点和下面要讲的 unordered_map 正好相反。 插入/删除破坏了 ①②④⑤ 时用「旋转rotation 重新着色recolor」 修回来每次只需常数次调整代价已经算在 O(log n) 里。 中序遍历这棵树取出的是20 30 40 50 70 ... —— 天然有序。这就是 map/set 能提供 lower_bound/upper_bound 的原因。注意最后一行「有序」不是 map 额外维护的一个属性而是树结构的副产品。你插入 30、50、20、70、40中序遍历永远是 20 30 40 50 70和插入顺序无关。红黑树的具体实现和旋转细节不必背记住两条就够用key 有序、树高被保证在 O(log n)。map 家族有四个成员区别只在「允不允许重复」容器重复元素有序性查找典型用途std::mapK, V不允许重复 key按 key 升序可用比较器改O(log n)键值映射、需要有序遍历或范围查询std::setK不允许重复升序O(log n)去重 有序遍历std::multimapK, V允许重复 key有序O(log n)一对多分数→姓名、索引倒排std::multisetK允许重复有序O(log n)有序袋、滑动窗口中位数// map_basic.cpp — 编译: g -stdc17 -Wall -O2 map_basic.cpp -o map_basic #include iostream #include map #include set #include string int main() { std::mapstd::string, int ages; ages[alice] 30; ages[bob] 25; ages[carol] 35; std::cout map iteration (sorted by key):; for (const auto [name, age] : ages) std::cout name age; std::cout \n; // insert 返回 pairiterator, boolbool 说明到底插进去了没有 const auto [it1, inserted1] ages.insert({dave, 40}); const auto [it2, inserted2] ages.insert({bob, 99}); std::cout insert dave: inserted inserted1 value it1-second \n; std::cout insert bob : inserted inserted2 value it2-second \n; std::setint uniq{3, 1, 4, 1, 5, 9, 2, 6}; std::cout set (dedup sorted):; for (int v : uniq) std::cout v; std::cout \nset size uniq.size() \n; std::cout count(4) uniq.count(4) count(7) uniq.count(7) \n; return 0; }map iteration (sorted by key): alice30 bob25 carol35 insert dave: inserted1 value40 insert bob : inserted0 value25 set (dedup sorted): 1 2 3 4 5 6 9 set size 7 count(4) 1 count(7) 0三处细节都值得记住遍历输出是alice bob carol而不是插入顺序红黑树的中序即字典序insert(bob, 99)返回inserted0, value25没有覆盖原来的 25 还在这是insert与operator[]最本质的区别set把重复出现的 1 去掉了并排好序count就是「在不在」的判据。官方文档std::map — cppreference 官方文档std::set — cppreference 官方文档std::multimap — cppreference3. 陷阱一operator[] 找不到就插入operator[]的完整语义是「返回 key 对应 value 的引用key 不存在就先用默认构造塞一个进去再返回它的引用」。所以它有三个后果容器会被改size 变大value 类型必须可默认构造否则编译不过const map上根本不能用它。operator[]在写入场景很好用histogram[word]是标准写法但只读场景必须换 API// map_subscript.cpp — 编译: g -stdc17 -Wall -O2 map_subscript.cpp -o map_subscript #include iostream #include map #include stdexcept #include string int main() { std::mapstd::string, int inventory{{apple, 3}}; std::cout size before inventory.size() \n; const int missing inventory[banana]; // 反例不要这么写读一下就插进去了 std::cout inventory[\banana\] missing but size becomes inventory.size() \n; const auto found inventory.find(cherry); // 只读查询找不到不会改容器 std::cout find(\cherry\) end() ? (found inventory.end()) size inventory.size() \n; try { std::cout inventory.at(cherry) \n; } catch (const std::out_of_range e) { // 异常按引用捕按值抛 std::cout at(\cherry\) threw std::out_of_range: e.what() \n; } const std::mapstd::string, int frozen inventory; std::cout size still frozen.size() \n; return 0; }size before 1 inventory[banana] 0 but size becomes 2 find(cherry) end() ? 1 size 2 at(cherry) threw std::out_of_range: map::at size still 2三种只读写法各有取舍写法找不到时能用在const map上复杂度什么时候用m[key]插入默认值size 1不能O(log n)只在「写」的语义下用如m[k]m.at(key)抛std::out_of_range能O(log n)逻辑上必须存在不存在就是 bugm.find(key)返回end()能O(log n)常规只读查询还要拿 valuem.count(key)返回 0能O(log n)只判断存在性m.contains(key)返回false能O(log n)C20 起可用语义最直白at抛出的异常信息里那句map::at是 libstdc 的实现细节标准只要求抛std::out_of_range没规定what()内容换编译器可能不同不要拿去匹配字符串。官方文档std::map::operator[] — cppreference官方第一句话就写着「若 key 不存在则插入 value_type(key, T())」。 官方文档std::map::at — cppreference 官方文档std::map::containsC20— cppreferenceC20 才有contains在 C17 里用count代替// verify: stdc20 #include map bool has_key(const std::mapint, int table, int key) { return table.contains(key); // 需要 C20C17 写 table.count(key) ! 0 }4. 陷阱二拿 std::find 去查 map「map 的查找快」不是修辞。std::map::find走的是红黑树的搜索路径一次比较就把候选范围砍一半而std::find/std::find_if是从begin()开始逐个线性扫描完全无视树结构。给 map 的 key 装一个计数比较器、再给find_if的谓词装一个计数器就能量出差距// map_find_vs_std_find.cpp — 编译: g -stdc17 -Wall -O2 map_find_vs_std_find.cpp -o map_find_vs_std_find #include algorithm #include cstddef #include iostream #include map struct Stats { inline static std::size_t comparisons 0; // map 内部比较次数 inline static std::size_t predicate_calls 0; // find_if 谓词调用次数 }; struct Key { int id 0; }; struct CountingLess { bool operator()(const Key a, const Key b) const { Stats::comparisons; return a.id b.id; } }; constexpr int N 1000; int main() { std::mapKey, int, CountingLess table; for (int i 0; i N; i) table.emplace(Key{i}, i * 10); const Key target{500}; // 正好在中间 Stats::comparisons 0; const auto by_tree table.find(target); const std::size_t tree_cmp Stats::comparisons; Stats::predicate_calls 0; const auto by_scan std::find_if(table.begin(), table.end(), [target](const auto kv) { Stats::predicate_calls; return kv.first.id target.id; }); std::cout keys N \n; std::cout map::find comparisons tree_cmp found (by_tree ! table.end()) \n; std::cout std::find_if calls Stats::predicate_calls found (by_scan ! table.end()) \n; return 0; }keys 1000 map::find comparisons 11 found1 std::find_if calls 501 found1同样是「查一个存在的 key」写法依据复杂度1000 个 key 的实测table.find(k)红黑树搜索路径每次比较砍一半O(log n)11 次比较std::find_if(m.begin(), m.end(), ...)从头部线性扫描O(n)501 次谓词调用11 次比较正好是 log₂(1000) ≈ 10 的量级红黑树最长路径不超过 2log₂(n1)501 次是「目标在中间」的必然结果。规模再大十倍前者只多 34 次后者多十倍。用了 map 却拿std::find去查等于把 O(log n) 亲手降级成 O(n)。官方文档std::map::find — cppreference标注的复杂度就是「与容器大小的对数成正比」。 官方文档std::find_if — cppreference线性扫描的泛型版本。5. 插入 API 选型五种写法构造次数差一倍map 一次性提供了五种「插入或更新」的写法它们的区别全在构造/拷贝/移动的次数以及key 已存在时的行为。用一个自带计数器的 value 类型实测一遍// map_emplace.cpp — 编译: g -stdc17 -Wall -O2 map_emplace.cpp -o map_emplace #include cstddef #include iostream #include map #include string struct WidgetStats { inline static std::size_t default_ctors 0; inline static std::size_t value_ctors 0; inline static std::size_t copies 0; inline static std::size_t moves 0; static void reset() { default_ctors 0; value_ctors 0; copies 0; moves 0; } static std::size_t ctors() { return default_ctors value_ctors; } }; struct Widget { int id 0; Widget() { WidgetStats::default_ctors; } explicit Widget(int v) : id(v) { WidgetStats::value_ctors; } Widget(const Widget other) : id(other.id) { WidgetStats::copies; } Widget(Widget other) noexcept : id(other.id) { WidgetStats::moves; } Widget operator(const Widget other) { id other.id; WidgetStats::copies; return *this; } Widget operator(Widget other) noexcept { id other.id; WidgetStats::moves; return *this; } }; void report(const char* label) { std::cout label ctors WidgetStats::ctors() copies WidgetStats::copies moves WidgetStats::moves \n; } int main() { { std::mapstd::string, Widget m; WidgetStats::reset(); m[a] Widget{1}; // 默认构造一个 移动赋值 report(operator[] ); } { std::mapstd::string, Widget m; WidgetStats::reset(); m.insert({b, Widget{2}}); // 构造临时 pair 再移动进节点 report(insert ); } { std::mapstd::string, Widget m; WidgetStats::reset(); m.emplace(c, 3); // 就地在节点里构造零临时对象 report(emplace ); } { std::mapstd::string, Widget m; WidgetStats::reset(); m.try_emplace(d, 4); // key 不存在才构造C17 report(try_emplace ); } { std::mapstd::string, Widget m; m.emplace(e, 5); WidgetStats::reset(); m.emplace(e, 9); // key 已存在白构造一个再丢掉 report(emplace dup ); std::cout kept m.at(e).id \n; } { std::mapstd::string, Widget m; m.emplace(f, 5); WidgetStats::reset(); m.try_emplace(f, 9); // key 已存在一个对象都不构造 report(try_emplace dup ); std::cout kept m.at(f).id \n; } { std::mapstd::string, Widget m; m.emplace(g, 5); WidgetStats::reset(); m.insert_or_assign(g, Widget{9}); // C17明确要覆盖 report(insert_or_assign); std::cout kept m.at(g).id \n; } return 0; }operator[] ctors2 copies0 moves1 insert ctors1 copies0 moves2 emplace ctors1 copies0 moves0 try_emplace ctors1 copies0 moves0 emplace dup ctors1 copies0 moves0 kept 5 try_emplace dup ctors0 copies0 moves0 kept 5 insert_or_assign ctors1 copies0 moves1 kept 9把这些数字翻译成人话写法key 已存在时构造次数拷贝/移动实测ctors/copies/moves什么时候用m[k] v覆盖2默认构造 赋值1 次移动赋值2 / 0 / 1value 可默认构造且你就是要覆盖m.insert({k, v})忽略boolfalse12 次移动1 / 0 / 2需要「到底插进去了没有」的返回值m.emplace(k, args...)忽略但白构造一个1命中时也构造01 / 0 / 0dup 也是 1新 key 就地构造别对已存在的 key 用m.try_emplace(k, args...)忽略且不构造1命中时 001 / 0 / 0dup 是 0C17 起的新代码首选m.insert_or_assign(k, v)覆盖11 次移动赋值1 / 0 / 1C17语义上明确要覆盖三条结论要「插入已存在就别动」→ 用try_emplace。它是唯一在 key 已存在时连一个对象都不构造的写法实测ctors0而emplace在同样情况下白构造一个Widget再销毁实测ctors1。value 很大或是持有资源文件句柄、unique_ptr时这个差别就是实打实的开销。operator[]的代价是「默认构造 赋值」两次操作实测ctors2 moves1而且要求 value 可默认构造。它在明确的写入场景m[k] v、m[k]够用但不要用它做「不存在才插入」的逻辑。要「覆盖」→ 用insert_or_assign它的意图写在函数名里比m[k] v更明确不过它要求 value可赋值——注意上面代码里写的是Widget{9}直接写9会编译失败因为Widget的单参构造函数是explicit不存在从int到Widget的隐式赋值转换。insert的返回值std::pairiterator, bool值得单独记一笔bool告诉你「到底有没有真的插入」iterator指向「现在那个 key 所在的位置」不管是新插的还是本来就有的。上面第 3 节的insert(bob, 99)输出inserted0就是这个 boole 在起作用。官方文档std::map::emplace — cppreference 官方文档std::map::try_emplace — cppreference 官方文档std::map::insert_or_assign — cppreference还有一条必须记住的map 的 key 是const。value_type是std::pairconst Key, T所以it-second可以改it-first改不了#include map #include string void keys_are_const(std::mapint, std::string m) { auto it m.begin(); it-second value is mutable; // 可以value 非 const // 反例不要这么写编译失败 —— key_type 是 const int // it-first 5; // error: assignment of read-only member }想改 key只能erase再insert这正好也说明为什么 key 不能随便改改了树的有序性就崩了。上面的片段故意不写main()因为它是用来展示编译错误的。6. 范围查询与自定义比较器有序容器真正让人舍不得放弃的能力是范围查询lower_bound第一个 ≥ key、upper_bound第一个 key、equal_range一次拿到两者也就是[lower_bound, upper_bound)。// map_range.cpp — 编译: g -stdc17 -Wall -O2 map_range.cpp -o map_range #include functional #include iostream #include iterator #include map #include string // 踩坑用的比较器只按字符串长度比较 struct ByLength { bool operator()(const std::string a, const std::string b) const { return a.size() b.size(); } }; int main() { std::mapint, std::string m{{10, ten}, {20, twenty}, {30, thirty}, {40, forty}}; const auto lo m.lower_bound(20); // 第一个 20 const auto hi m.upper_bound(30); // 第一个 30 std::cout range [20, 30] :; for (auto it lo; it ! hi; it) std::cout it-first it-second; std::cout \n; const auto [first, last] m.equal_range(30); // 一次拿到上下界 std::cout equal_range(30) count std::distance(first, last) \n; std::mapint, std::string, std::greaterint desc{{10, ten}, {40, forty}, {20, twenty}}; std::cout descending keys:; for (const auto [key, value] : desc) std::cout key; std::cout \n; std::multimapstd::string, int scores{{alice, 80}, {bob, 90}, {alice, 95}}; const auto [af, al] scores.equal_range(alice); std::cout alice scores:; for (auto it af; it ! al; it) std::cout it-second; std::cout \n; std::mapstd::string, int, ByLength by_len; by_len[ab] 1; by_len[cd] 2; // 与 ab 等价长度相同→ 不新增条目 std::cout by_len size by_len.size() key by_len.begin()-first value by_len.begin()-second \n; return 0; }range [20, 30] : 20twenty 30thirty equal_range(30) count 1 descending keys: 40 20 10 alice scores: 80 95 by_len size 1 key ab value 2逐个看[lower_bound(20), upper_bound(30))恰好是[20, 30]下半界是闭、上半界是开所以想要「含 30」就必须用upper_bound(30)而不是lower_bound(30)。这个半开区间约定和 STL 其他算法一致。equal_range一次返回上下界用std::distance数一下就是「这个 key 有几个元素」。map里最多 1 个multimap里可以多个——所以equal_range配multimap最合适示例里 alice 的 80 和 95 都拿到了。换比较器就换了遍历顺序std::greaterint让 key 降序这是「有序」的另一个用法。最后一段是踩坑示范ByLength只比字符串长度于是ab和cd在它眼里等价谁都不小于谁map 认为它们是同一个 key——by_len[cd] 2根本没新增条目只是把ab那格的值改成了 2。输出by_len size 1 key ab value 2证实了这一点。规则自定义比较器必须是一个严格弱序strict weak ordering其中最容易被忽略的一条是「等价必须可传递」——comp(a,b)false comp(b,a)false的两个 key 会被当作同一个 key。只比一部分字段长度、大小写忽略后的样子、float的近似相等是很危险的比较器。默认的std::lessKey即operator在绝大多数场景都是对的。官方文档std::map::lower_bound — cppreference 官方文档std::lower_bound泛型算法— cppreference 官方文档std::less — cppreferencestd::map的默认比较器语义就是operator。7. 完整示例一份有序的成绩单下面这个例子把前面所有要点串起来insert的bool判重、multimap按分数排序取 Top-N、lower_bound/upper_bound做分数区间查询。Key姓名用map保证不重复且有序分数是「一对多」的所以排序输出用multimap。// score_board.cpp — 编译: g -stdc17 -Wall -O2 score_board.cpp -o score_board #include cstddef #include functional #include iostream #include map #include string #include vector class ScoreBoard { public: void add(const std::string name, int score) { const auto [it, inserted] scores_.insert({name, score}); if (!inserted) { it-second score; // 已存在就更新分数key 不可改value 可改 } } std::vectorstd::string top(std::size_t count) const { std::multimapint, std::string, std::greaterint ranked; // 分数从高到低 for (const auto [name, score] : scores_) ranked.insert({score, name}); std::vectorstd::string result; for (const auto [score, name] : ranked) { if (result.size() count) break; result.push_back(name); } return result; } std::vectorstd::string between(int low, int high) const { std::multimapint, std::string sorted; // 默认 less升序才能做区间查询 for (const auto [name, score] : scores_) sorted.insert({score, name}); std::vectorstd::string result; const auto last sorted.upper_bound(high); // 上半界开才包含 high for (auto it sorted.lower_bound(low); it ! last; it) { result.push_back(it-second); } return result; } std::size_t size() const { return scores_.size(); } private: std::mapstd::string, int scores_; // 按人名有序便于查找 }; int main() { ScoreBoard board; board.add(alice, 80); board.add(bob, 95); board.add(carol, 70); board.add(dave, 88); board.add(alice, 92); // 重名 - 更新分数不新增条目 std::cout players board.size() \n; std::cout top 3:; for (const std::string name : board.top(3)) std::cout name; std::cout \n; std::cout score in [80, 95]:; for (const std::string name : board.between(80, 95)) std::cout name; std::cout \n; return 0; }players 4 top 3: bob alice dave score in [80, 95]: dave alice bobplayers 4而不是 5说明重名的 alice 走了「更新」分支top 3按分数降序给出 bob(95)、alice(92)、dave(88)区间查询按分数升序给出 dave(88)、alice(92)、bob(95)。四个容器map/multimap× 两种比较器各司其职。8. 选型速查需求选谁理由键值映射 需要有序遍历std::map红黑树O(log n) 且 key 有序去重 有序std::set同上只存 key一对多且要有序std::multimap/std::multiset允许等价 keyequal_range拿到全部只判断存在性find/countC20 用contains别用operator[]它会插入「不存在才插入」try_emplaceC17命中时不构造任何对象「存在就覆盖」insert_or_assignC17语义明确且返回是否为新插入只需要 O(1) 平均查找、不在乎顺序std::unordered_map哈希表见《unordered_map / unordered_set 完全指南》元素很少十几个std::vector 排序小 N 时线性查找的常数因子比树更低9. 延伸阅读std::map — cppreference接口全貌注意value_type是pairconst Key, T这就是 key 不可改的来源。std::map::operator[] — cppreference官方明确写了「key 不存在时插入 value-initialized 的 value」是第 3 节的依据。std::map::try_emplace — cppreference注意「若 key 已存在则不做任何事」这句是它比emplace省的根源。std::map::lower_bound — cppreference 与 std::map::upper_bound半开区间的官方定义配合equal_range一起看。std::multimap — cppreference等价 key 的相邻性保证同一个 key 的元素在遍历中连续出现。C Core Guidelines — isocpp.github.io容器选型与「别用operator[]做查询」这类接口设计思路的来源。本知识库内的相关篇目《unordered_map / unordered_set 完全指南哈希表、rehash 与自定义哈希》 —— 讲透 std::unordered_map 的哈希表结构——桶数组加链表具体实现由标准库定义《C map 与 unordered_map 怎么选底层结构、复杂度与决策流程》 —— std::map 和 std::unordered_map 接口几乎一样底层却完全不同。《list 与 forward_list链表真的比 vector 快吗》 —— 用计数分配器和实测耗时把 std::list / std::forward_list 的真实开销算清楚10. 一句话总结std::map/std::set是一棵红黑树有序和 O(log n) 是同一套结构的两个结果中序遍历即有序所以有lower_bound/upper_bound/equal_range树高被保证在 O(log n)所以map::find查 1000 个 key 只要 11 次比较而std::find_if要扫 501 次。用之前记住三条operator[]找不到会插入默认值只读查询用find要抛异常用atC20 可contains插入用try_emplace它是唯一在 key 已存在时不构造任何对象的写法emplace会白构造一个key 是const且自定义比较器必须满足严格弱序否则「等价」的 key 会被悄悄吞掉。