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::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

把这些数字翻译成人话：

三条结论：

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[] 做查询」这类接口设计思路的来源。

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 会被悄悄吞掉。