企业官网建设流程全解析

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::map<Key, 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 家族有四个成员，区别只在「允不允许重复」：

// map_basic.cpp — 编译: g++ -std=c++17 -Wall -O2 map_basic.cpp -o map_basic #include <iostream> #include <map> #include <set> #include <string> int main() { std::map<std::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 返回 pair<iterator, bool>：bool 说明到底插进去了没有 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::set<int> 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): alice=30 bob=25 carol=35 insert dave: inserted=1 value=40 insert bob : inserted=0 value=25 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)返回inserted=0, value=25，没有覆盖，原来的 25 还在，这是insert与operator[]最本质的区别；set把重复出现的 1 去掉了并排好序，count就是「在不在」的判据。

官方文档：std::map — cppreference 官方文档：std::set — cppreference 官方文档：std::multimap — cppreference

3. 陷阱一：operator[] 找不到就插入

operator[]的完整语义是「返回 key 对应 value 的引用；key 不存在就先用默认构造塞一个进去，再返回它的引用」。所以它有三个后果：容器会被改（size 变大）；value 类型必须可默认构造（否则编译不过）；const map上根本不能用它。

operator[]在写入场景很好用（histogram[word]++是标准写法），但只读场景必须换 API：

// map_subscript.cpp — 编译: g++ -std=c++17 -Wall -O2 map_subscript.cpp -o map_subscript #include <iostream> #include <map> #include <stdexcept> #include <string> int main() { std::map<std::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::map<std::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

三种只读写法各有取舍：

at抛出的异常信息里那句map::at是 libstdc++ 的实现细节（标准只要求抛std::out_of_range，没规定what()内容），换编译器可能不同，不要拿去匹配字符串。

官方文档：std::map::operator[] — cppreference：官方第一句话就写着「若 key 不存在则插入 value_type(key, T())」。 官方文档：std::map::at — cppreference 官方文档：std::map::contains（C++20）— cppreference

C++20 才有contains，在 C++17 里用count代替：

// verify: std=c++20 #include <map> bool has_key(const std::map<int, int>& table, int key) { return table.contains(key); // 需要 C++20；C++17 写 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++ -std=c++17 -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::map<Key, 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 found=1 std::find_if calls = 501 found=1

同样是「查一个存在的 key」：

11 次比较正好是 log₂(1000) ≈ 10 的量级（红黑树最长路径不超过 2log₂(n+1)）；501 次是「目标在中间」的必然结果。规模再大十倍，前者只多 3～4 次，后者多十倍。用了 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++ -std=c++17 -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::map<std::string, Widget> m; WidgetStats::reset(); m["a"] = Widget{1}; // 默认构造一个 + 移动赋值 report("operator[] "); } { std::map<std::string, Widget> m; WidgetStats::reset(); m.insert({"b", Widget{2}}); // 构造临时 pair 再移动进节点 report("insert "); } { std::map<std::string, Widget> m; WidgetStats::reset(); m.emplace("c", 3); // 就地在节点里构造，零临时对象 report("emplace "); } { std::map<std::string, Widget> m; WidgetStats::reset(); m.try_emplace("d", 4); // key 不存在才构造（C++17） report("try_emplace "); } { std::map<std::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::map<std::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::map<std::string, Widget> m; m.emplace("g", 5); WidgetStats::reset(); m.insert_or_assign("g", Widget{9}); // C++17：明确要覆盖 report("insert_or_assign"); std::cout << " kept = " << m.at("g").id << '\n'; } return 0; }

operator[] ctors=2 copies=0 moves=1 insert ctors=1 copies=0 moves=2 emplace ctors=1 copies=0 moves=0 try_emplace ctors=1 copies=0 moves=0 emplace dup ctors=1 copies=0 moves=0 kept = 5 try_emplace dup ctors=0 copies=0 moves=0 kept = 5 insert_or_assign ctors=1 copies=0 moves=1 kept = 9

把这些数字翻译成人话：

三条结论：

1. 要「插入，已存在就别动」→ 用try_emplace。它是唯一在 key 已存在时连一个对象都不构造的写法（实测ctors=0），而emplace在同样情况下白构造一个Widget再销毁（实测ctors=1）。value 很大或是持有资源（文件句柄、unique_ptr）时，这个差别就是实打实的开销。
2. operator[]的代价是「默认构造 + 赋值」两次操作（实测ctors=2 moves=1），而且要求 value 可默认构造。它在明确的写入场景（m[k] = v、m[k]++）够用，但不要用它做「不存在才插入」的逻辑。
3. 要「覆盖」→ 用insert_or_assign，它的意图写在函数名里，比m[k] = v更明确；不过它要求 value可赋值——注意上面代码里写的是Widget{9}，直接写9会编译失败，因为Widget的单参构造函数是explicit，不存在从int到Widget的隐式赋值转换。

insert的返回值std::pair<iterator, bool>值得单独记一笔：bool告诉你「到底有没有真的插入」，iterator指向「现在那个 key 所在的位置」（不管是新插的还是本来就有的）。上面第 3 节的insert("bob", 99)输出inserted=0就是这个 boole 在起作用。

官方文档：std::map::emplace — cppreference 官方文档：std::map::try_emplace — cppreference 官方文档：std::map::insert_or_assign — cppreference

还有一条必须记住的：map 的 key 是const。value_type是std::pair<const Key, T>，所以it->second可以改，it->first改不了：

#include <map> #include <string> void keys_are_const(std::map<int, 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++ -std=c++17 -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::map<int, 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::map<int, std::string, std::greater<int>> desc{{10, "ten"}, {40, "forty"}, {20, "twenty"}}; std::cout << "descending keys:"; for (const auto& [key, value] : desc) std::cout << ' ' << key; std::cout << '\n'; std::multimap<std::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::map<std::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] : 20=twenty 30=thirty 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::greater<int>让 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::less<Key>（即operator<）在绝大多数场景都是对的。

官方文档：std::map::lower_bound — cppreference 官方文档：std::lower_bound（泛型算法）— cppreference 官方文档：std::less — cppreference：std::map的默认比较器，语义就是operator<。

7. 完整示例：一份有序的成绩单

下面这个例子把前面所有要点串起来：insert的bool判重、multimap按分数排序取 Top-N、lower_bound/upper_bound做分数区间查询。Key（姓名）用map保证不重复且有序；分数是「一对多」的，所以排序输出用multimap。

// score_board.cpp — 编译: g++ -std=c++17 -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::vector<std::string> top(std::size_t count) const { std::multimap<int, std::string, std::greater<int>> ranked; // 分数从高到低 for (const auto& [name, score] : scores_) ranked.insert({score, name}); std::vector<std::string> result; for (const auto& [score, name] : ranked) { if (result.size() == count) break; result.push_back(name); } return result; } std::vector<std::string> between(int low, int high) const { std::multimap<int, std::string> sorted; // 默认 less：升序，才能做区间查询 for (const auto& [name, score] : scores_) sorted.insert({score, name}); std::vector<std::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::map<std::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 bob

players = 4而不是 5，说明重名的 alice 走了「更新」分支；top 3按分数降序给出 bob(95)、alice(92)、dave(88)；区间查询按分数升序给出 dave(88)、alice(92)、bob(95)。四个容器（map/multimap× 两种比较器）各司其职。

8. 选型速查

9. 延伸阅读

• std::map — cppreference：接口全貌；注意value_type是pair<const 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（要抛异常用at，C++20 可contains）；插入用try_emplace，它是唯一在 key 已存在时不构造任何对象的写法（emplace会白构造一个）；key 是const，且自定义比较器必须满足严格弱序，否则「等价」的 key 会被悄悄吞掉。