C++ 关联容器：让数据按键回答问题

一份构建日志里有几十万条记录。排查问题时，我们通常不会问“第 18472 条是什么”，而会问“任务 compile-api 出现过几次”“错误码 E104 对应哪些记录”“用户 u-17 的最后状态是什么”。这些问题都从一个键出发，再寻找与键关联的数据。

关联容器正是为这种访问方式准备的。它可以只保存键，也可以保存键和值；可以拒绝重复键，也可以保留同一键的多条记录；还可以在“按键有序”和“通过哈希快速定位”之间选择。

这篇文章围绕一条完整路径展开：先把输入整理成键，再选择容器，随后处理插入、查询、重复键、比较规则和哈希规则，最后把这些工具组合成一个可查询的文本索引。示例均使用 C++17。

从词频索引理解“按键访问”

先看一个小型检索任务。我们要统计文本中的单词，同时忽略停用词。程序关心两种关系：

• 某个单词是否属于停用词集合；
• 某个单词对应多少次出现。

第一种关系只有“存在”与“不存在”，适合 set。第二种关系是“单词到次数”的映射，适合 map。

#include <cctype>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
std::string normalize_ascii_word(const std::string& token) {
    std::string word;
    for (unsigned char ch : token) {
        if (std::isalpha(ch) != 0) {
            word.push_back(static_cast<char>(std::tolower(ch)));
        }
    }
    return word;
}
 
int main() {
    const std::set<std::string> ignored = {"a", "the"};
    std::map<std::string, std::size_t> frequency;
    std::istringstream input("Map, set map; THE set index map.");
    for (std::string token; input >> token;) {
        const std::string word = normalize_ascii_word(token);
        if (!word.empty() && ignored.find(word) == ignored.end()) {
            ++frequency[word];
        }
    }
    for (const auto& [word, count] : frequency) {
        std::cout << word << ": " << count << '\n';
    }
}

输出：

index: 1
map: 3
set: 2

程序没有记录单词“位于第几个槽位”。ignored.find(word) 直接按单词判断成员资格，frequency[word] 直接按单词取得计数器。有序的 map 还让最终结果按键排列，所以输出顺序稳定。

这里的 ++frequency[word] 同时完成了两种情况：

1. 键已经存在时，取得已有计数并自增；
2. 键不存在时，先插入该键，把 std::size_t 值初始化为 0，再自增为 1。

这种下标行为非常适合累加器，却不适合单纯检查键是否存在。后文会专门比较 find、at 和 operator[]。

键和值分别承担什么职责

对 map<Key, T> 来说，Key 是身份，T 是与身份关联的数据。上例中的单词是身份，次数是可更新数据。

对 set<Key> 来说，元素本身就是身份，没有独立的 mapped value。停用词只需要回答“在不在”，保存一个额外的布尔值反而会让接口变得含糊。

选择键时应优先选稳定、能唯一表达业务身份的字段。用户名可能变化，用户编号通常更稳定；显示标题可能重复，任务编号通常更适合作为键。

小节测试

用三个问题选出合适的容器

标准库提供八种关联容器。名字虽然多，选择时只要依次回答三个问题。

有序的 map、multimap 定义在 <map>，set、multiset 定义在 <set>。无序版本分别定义在 <unordered_map> 和 <unordered_set>。

有序与无序不是“慢”和“快”的简单标签

有序关联容器的查找、插入和按键删除通常具有对数复杂度。它们持续维护比较器定义的顺序，因此适合下面这些任务：

• 直接按键升序或自定义顺序输出；
• 查询某个键区间；
• 找到不排在目标键之前的第一个元素；
• 让测试和报表拥有稳定顺序。

无序关联容器的查找、插入和按键删除平均具有常数复杂度，最坏情况仍可能退化为线性。它们适合大量精确键查找，并且调用方不依赖遍历顺序的场景。

数据规模、键比较成本、哈希质量、内存布局和输出要求都会影响真实表现。几十个元素的配置表通常不值得为了理论复杂度改写；几十万条会频繁查找的会话记录才更可能体现差异。需要性能结论时，应使用真实负载测量。

multimap 还是 map<Key, vector<T>>

这两种设计都能表达一对多，但操作重心不同。

容器类型应该体现主要操作，而不是只描述静态数据形状。如果每次查询后都要把 multimap 的结果复制到一个数组再整体处理，那么把数组放进 map 的 mapped value 可能更直接。

小节测试

看懂元素类型与插入结果

map<Key, T> 的一个元素不是单独的 T，而是一个键值对。准确地说，它的 value_type 是 std::pair<const Key, T>。

• first 是键，类型带 const；
• second 是 mapped value，可以通过非 const 迭代器修改。

键决定元素在容器中的位置。允许原地修改键会破坏容器的组织规则，所以这类代码不能通过编译：

auto it = scores.find("u-17");
// it->first = "u-18";  // 错误：键是 const
it->second = 95;         // 正确：可以修改关联值

set 的元素本身就是键，因此通过 set 迭代器也不能修改元素。需要改键时，清楚的做法是删除旧元素，再插入新元素。

唯一键容器的 insert 会报告两件事

对 map、set 以及它们的无序唯一键版本，单元素 insert 返回一个二元结果：

1. 迭代器指向容器中具有该键的元素；
2. 布尔值说明本次调用是否真的插入了新元素。

#include <iostream>
#include <map>
#include <string>
 
int main() {
    std::map<std::string, int> quotas;
    const auto first = quotas.insert({"build", 3});
    const auto second = quotas.insert({"build", 9});
    std::cout << std

输出：

first inserted: true, value: 3
second inserted: false, value: 3
build => 4

第二次插入没有用 9 覆盖已有的 3。不过返回的迭代器仍然有用：它指向已有元素，所以程序可以根据业务规则把值更新为 4。

多重键容器的单元素 insert 不需要“是否成功”的布尔值，因为重复键也能插入。它直接返回指向新元素的迭代器。

C++17 中几种常见写入方式

try_emplace 和 insert_or_assign 都是 C++17 可用的接口。它们把“不要覆盖”和“允许覆盖”写进函数名，比忽略 insert 的布尔结果更容易审查。

小节测试

把查询和写入分开

关联容器有多种看似相近的查询接口。区别集中在两个问题：查询失败时怎样报告，以及查询会不会修改容器。

在 C++17 中没有关联容器成员 contains。只检查存在性时，通常写 container.find(key) != container.end()。

下面的程序把三种访问方式放在一起，观察每一步的容器大小。

#include <iostream>
#include <map>
#include <stdexcept>
#include <string>
 
int main() {
    std::map<std::string, int> stock = {{"pen", 2}};
    std::cout << "initial size: " << stock.size() << '\n';
    const auto found = stock.

输出：

initial size: 1
find tape: false
size after find: 1
at tape: missing
size after at: 1
operator[] value: 0
size after []: 2
tape after update: 5

find 和失败的 at 都没有改变容器。stock["tape"] 则插入了一个值为 0 的元素，所以大小从 1 变成 2。

怎样选择查询接口

• 需要迭代器，或者缺失是正常分支：用 find；
• 只需要匹配数量：用 count；
• 认为缺失是调用错误，希望统一走异常路径：用 at；
• 明确要“没有就创建”，例如计数或分组：用 operator[]。

对唯一键容器，count(key) 只能是 0 或 1。对 multimap、multiset 及其无序版本，结果可能大于 1。

operator[] 需要能够为 mapped type 创建默认值。如果 mapped type 没有合适的默认构造方式，或者默认构造成本高，try_emplace 往往更合适。

const map 不能使用下标，因为下标可能插入元素；它仍可使用 find、count 和 at 的只读重载。这条限制也能帮助接口表达意图：只读函数接收 const 容器后，不会意外创建键。

小节测试

用半开范围取出所有重复键

唯一键容器中的 find 至多对应一个元素。multimap 和 multiset 允许等价键重复，只拿一次 find 的结果会漏掉其余记录。

有序多重容器把等价键放在一个连续区间里，三个接口描述了这个区间：

• lower_bound(key)：第一个不排在 key 之前的元素；
• upper_bound(key)：第一个排在 key 之后的元素；
• equal_range(key)：一次返回上面两个边界。

在默认升序比较下，可以把前两句分别理解为“第一个不小于 key”和“第一个大于 key”。使用自定义比较器时，应回到“是否排在之前”的定义。

#include <iostream>
#include <map>
#include <string>
 
int main() {
    std::multimap<std::string, int> positions = {
        {"build", 2},
        {"warn", 3},
        {"build", 5},
        {"build", 9}
    };
    const auto

输出：

count: 3
positions: 2 5 9
same range: true
missing range empty: true

equal_range 返回的是半开范围 [first, second)。目标键缺失时，两个迭代器相等，循环自然执行零次，不需要额外的异常或哨兵值。

查找之后怎样删除

删除某个键的全部匹配项，可以直接调用：

const std::size_t removed = positions.erase("build");

返回值是实际删除的元素数。若只想删除筛选后的一部分匹配项，可以先取得 equal_range，在区间中逐个判断并使用迭代器重载的 erase。

有序容器可以用 lower_bound 和 upper_bound 做范围查询，例如遍历状态码 [400, 500)。无序容器没有键顺序，因此没有这两个成员函数。不过 unordered_multimap 和 unordered_multiset 仍提供 equal_range，用来取得某个等价键的所有元素；该范围内部不承诺业务排序。

建立索引，再使用索引

一对多索引通常分两步完成：

1. 遍历基础记录，把索引键和稳定标识插入 multimap；
2. 查询时用 equal_range 取得标识，再回到基础记录读取完整数据。

这样可以针对发送者、主题、标签等字段分别建立索引，而不必把某一种查询顺序硬塞进基础数据结构。

小节测试

让比较器定义顺序和唯一性

有序关联容器默认使用 std::less<Key>。自定义键没有自然顺序，或者业务需要另一种顺序时，可以把比较器作为模板参数传给容器。

比较器不只是控制打印顺序，它还定义“哪些键等价”。对比较器 comp，两个键在容器看来等价，当且仅当：

!comp(a, b) && !comp(b, a)

这个判断不要求调用 operator==。如果比较器只看任务优先级，那么两个编号不同但优先级相同的任务会成为等价键；放进 set 时，其中一个可能无法插入。

下面的比较器先按优先级从高到低排列，再用稳定编号打破并列。

#include <iostream>
#include <set>
#include <string>
 
struct Ticket {
    int priority;
    std::string id;
};
 
struct TicketOrder {
    bool operator()(const Ticket& lhs, const Ticket& rhs) const {
        if (lhs.priority != rhs.priority) {
            return lhs.priority 

输出：

size: 3
3:A-7
2:A-1
2:B-2

重复的 {2, "A-1"} 在两个方向上都不小于另一个，因此被视为等价键。{2, "A-1"} 与 {2, "B-2"} 的优先级相同，但编号打破了并列，所以两者都能保留。

严格弱序的四条实践规则

一个可用于有序容器的比较器应形成严格弱序。写代码时至少检查下面四点：

• comp(x, x) 必须为 false；
• 如果 comp(a, b) 为 true，comp(b, a) 必须为 false；
• 顺序关系必须传递；
• 比较结果不能在容器存续期间因外部可变状态而改变。

最常见的错误是把“小于”写成“小于等于”：

// 错误示意：当 lhs 与 rhs 相同时也可能返回 true
return lhs.priority >= rhs.priority;

另一个常见问题是遗漏稳定的决胜字段。只按字符串长度比较会让所有同长度字符串都成为等价键。如果业务身份不是“长度”，应在长度相同后继续比较字符串本身。

比较器与边界查询必须一致

find、lower_bound、upper_bound、equal_range 和迭代顺序都会使用同一个比较器。若容器按优先级降序排列，“之前”和“之后”也要按降序理解，不能再套用数值升序的直觉。

可以通过 key_comp() 取得容器当前比较器的副本，但通常更好的做法是把比较规则封装成命名清楚、可独立测试的小类型。

小节测试

理解哈希、相等、桶与负载

无序关联容器先对键计算哈希值，再把元素放进某个桶。查找同一个键时，容器先定位候选桶，再用相等判断确认具体元素。

不同键得到相同哈希值是正常现象，称为碰撞。正确性不能依赖“哈希值永不重复”；哈希只负责缩小候选范围，相等判断才负责确认身份。

自定义键需要让哈希函数和相等判断使用同一套身份字段。下面的用户键由区域和编号共同确定。

#include <cmath>
#include <functional>
#include <iostream>
#include <string>
#include <unordered_map>
 
struct UserKey {
    std::string region;
    int id;
};
 
struct UserHash {
    std::size_t operator()(const UserKey& key) const noexcept {
        std::size_t seed 

输出：

found cn/42: Lin
apac/42 missing: true
size: 2
bucket capacity ready: true
load formula holds: true

程序没有输出具体桶数或遍历顺序，因为这些细节可以随标准库实现和内部扩容状态变化。可移植代码应依赖接口承诺，而不是某次运行观察到的布局。

哈希与相等必须满足的契约

如果 UserEqual{}(a, b) 为 true，那么 UserHash{}(a) 与 UserHash{}(b) 必须相同。反过来不成立：哈希相同的两个键仍然可以不相等。

如果相等判断只看 id，哈希却同时看 region 和 id，两个“相等”的键可能落入不同桶，容器就无法可靠找到已有元素。最稳妥的做法是先写清业务身份字段，再让两个函数都使用这些字段。

观察和调整桶状态

reserve 的参数是预计元素数，rehash 的参数是桶数。批量导入前知道元素规模时，reserve 通常更贴近意图。

插入元素可能触发 rehash。rehash 会让所有迭代器失效，因此不要跨越可能扩容的插入长期保存无序容器迭代器。指向元素的引用和指针在单纯 rehash 后仍保持有效，但元素被删除后当然不能继续使用。

不要依赖无序遍历顺序

unordered_map 的遍历顺序既不是插入顺序，也不是键排序结果。rehash、标准库实现变化或不同构建环境都可能改变顺序。

需要稳定输出时有两条清楚的路径：直接选择 map，或者把无序容器的结果复制到适合排序的结构中再显式排序。不要给某次观察到的顺序编写测试快照。

小节测试

把转换、统计和位置索引组合起来

一个可查询的文本处理流程通常不只需要一种关系。下面的例子同时完成四件事：

• 用 map<string, string> 保存一对一转换规则；
• 用 set<string> 保存过滤词；
• 用 map<string, size_t> 保存转换后的词频；
• 用 multimap<string, size_t> 保存一个词出现的所有输入位置。

基础输入和派生索引分开保存。以后可以增加新的索引，而不必改变每条输入记录的基本形状。

#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <vector>
 
std::string apply_rule(
    const std::string& word,
    const std::map<std::string, std::string>& rules
) {
    const

输出：

cleaned: config build warn build warn
frequency:
build=2
config=1
warn=2
build positions: 2 4

为什么转换查询不用下标

apply_rule 使用 find。如果规则不存在，它直接返回输入单词，不会把“缺失规则”插入规则表。

如果写成 rules[word]，函数就需要接收非 const 映射，还会为每个没有转换规则的单词创建空字符串。这既改变数据，又把“没有规则”和“规则结果为空”混在一起。

缺失与空值经常代表不同状态：

• 缺失规则：保持输入不变；
• 规则存在但值为空：可能表示删除该词；
• 词频为 0：可能是显式初始化，也可能是下标误插入。

接口设计应保留这些区别，不要用一个默认值掩盖所有情况。

为什么位置索引保存编号

例子在 multimap 里保存位置编号，而没有保存指向 cleaned 元素的迭代器。vector 后续扩容可能移动元素，旧迭代器和指针会失效；整数位置更容易跨越扩容保存。

在真实系统中，还可以保存稳定记录 ID，再通过另一张唯一键映射取得完整记录。这种分层方式允许建立多个索引：

上线前的检查顺序

面对新的按键查询需求，可以按下面的顺序审查设计：

1. 键是否经过统一、确定的规范化；
2. 键表达的是稳定身份，还是会变化的显示字段；
3. 同一键是一条记录还是多条记录；
4. 缺失键应返回空范围、异常、默认值，还是创建新元素；
5. 重复写入应保留旧值、覆盖旧值，还是并存；
6. 调用方是否依赖按键顺序或区间查询；
7. 自定义比较、哈希与相等是否使用一致的身份规则；
8. 索引保存的引用、指针、迭代器或编号是否在基础数据变化后仍然有效。

这些问题回答清楚后，容器名称通常会自然确定。类型本身也会记录约束：set 表达成员资格，map 表达唯一映射，multi 表达重复关系，unordered 表达不承诺顺序。

动手扩展

可以在上面的程序上继续完成三项练习：

• 增加 ASCII 小写化和标点清理，验证不同写法会合并为同一个键；
• 增加按频次从高到低的报表，注意频次排序不等于键排序；
• 把位置索引换成 unordered_multimap 并测量大输入，但不要让输出测试依赖遍历顺序。

小节测试