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

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

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

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

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

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

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

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

cpp

#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';
    }
}

输出：

text

index: 1
map: 3
set: 2

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

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

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

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

容器只负责按键组织数据，不负责自动清洗键。示例先统一 ASCII 大小写并丢弃标点，否则 Map、map, 和 map 会成为三个不同的键。实际项目应先定义清楚分词和规范化规则，再建立索引。

键和值分别承担什么职责

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

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

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

小节测试

只需要判断某个错误码是否在禁用名单中，最贴合语义的容器是哪一个？

执行 `++frequency[word]` 时，如果 word 尚不存在，整数计数器会先被值初始化为 ____。

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

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

先判断元素形状。只保存身份或成员资格时选 set 家族；一个键还要关联一份数据时选 map 家族。

再判断键是否允许重复。每个键只能代表一项时选唯一键版本；同一键需要保留多条独立记录时选 multi 版本。

最后判断是否需要按键遍历、边界查询或稳定排序输出。需要这些能力时选有序版本；只关心按键查找且数据量足够大时，可以考虑 unordered 版本。

元素形状	键是否重复	按键有序	不保证顺序
只保存键	否	`set<Key>`	`unordered_set<Key>`
只保存键	是	`multiset<Key>`	`unordered_multiset<Key>`
保存键值对	否	`map<Key, T>`	`unordered_map<Key, T>`
保存键值对	是	`multimap<Key, T>`	`unordered_multimap<Key, T>`

关联容器选择路径：从仅键或键值对、唯一键或重复键，再到有序树或哈希桶，映射到 set、map、multi 与 unordered 家族 — 先确定元素形状和重复策略，再决定是否需要按键顺序；三个问题共同收敛到合适的关联容器。

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

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

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

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

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

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

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

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

需求	更自然的选择
每条关联记录独立插入，并按键遍历全部记录	`multimap<Key, T>`
经常整体替换某个键对应的列表	`map<Key, vector<T>>`
每个关联值本身要参与容器级迭代	`multimap<Key, T>`
需要直接取得并修改整组值	`map<Key, vector<T>>`
同一键的值还需要自行排序、去重或随机访问	`map<Key, vector<T>>`

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

不要因为容器名里有 unordered 就默认它更合适。只要最终输出必须按键排序，无序容器就还需要额外排序；这部分成本和代码复杂度也应计入选择。

小节测试

下面哪些需求天然需要允许等价键重复？

只要查找很多，就一定应该把 std::map 换成 std::unordered_map。

看懂元素类型与插入结果

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

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

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

cpp

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

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

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

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

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

cpp

#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::boolalpha;
    std::cout << "first inserted: " << first.second
              << ", value: " << first.first->second << '\n';
    std::cout << "second inserted: " << second.second
              << ", value: " << second.first->second << '\n';
    if (!second.second) {
        ++second.first->second;
    }
    for (const auto& [key, value] : quotas) {
        std::cout << key << " => " << value << '\n';
    }
}

输出：

text

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

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

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

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

操作	键已存在时	适合的意图
`insert({key, value})`	保留旧值	只允许首次登记
`emplace(key, value)`	保留旧值	就地构造候选元素
`try_emplace(key, args...)`	不构造 mapped value	mapped value 构造较贵
`insert_or_assign(key, value)`	覆盖旧值	明确表达新增或更新
`operator[](key) = value`	先默认构造再赋值	mapped type 便宜且确实需要下标

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

忽略 insert 返回值之前，先确认重复键时的行为确实是“保留旧记录”。如果需求是用最新配置覆盖旧配置，应明确使用赋值或 insert_or_assign。

小节测试

向 `map<string, int>` 连续插入键相同、值分别为 3 和 9 的两个元素，第二次普通 insert 的结果是什么？

`std::map<Key, T>::value_type` 中，键的类型是 `____ Key`，因此不能通过迭代器原地修改。

把查询和写入分开

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

接口	缺失键的结果	会插入吗	适用对象
`find(key)`	返回 `end()`	否	所有关联容器
`count(key)`	返回匹配数量	否	所有关联容器
`at(key)`	抛出 `std::out_of_range`	否	`map`、`unordered_map`
`operator[](key)`	返回新插入的默认值	是	`map`、`unordered_map`

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

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

cpp

#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.find("tape");
    std::cout << std::boolalpha;
    std::cout << "find tape: " << (found != stock.end()) << '\n';
    std::cout << "size after find: " << stock.size() << '\n';
    try {
        static_cast<void>(stock.at("tape"));
    } catch (const std::out_of_range&) {
        std::cout << "at tape: missing\n";
    }
    std::cout << "size after at: " << stock.size() << '\n';
    std::cout << "operator[] value: " << stock["tape"] << '\n';
    std::cout << "size after []: " << stock.size() << '\n';
    stock["tape"] += 5;
    std::cout << "tape after update: " << stock.at("tape") << '\n';
}

输出：

text

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

map 操作状态对比：find 和 at 不改变容器，operator[] 为缺失键插入默认值，insert 返回迭代器与是否成功的布尔值 — 同样是按键访问，接口对缺失键的处理完全不同；把容器大小和旧值一起观察，副作用就会变得直观。

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 容器后，不会意外创建键。

这类判断 if (sessions[id].active) 会在 id 缺失时创建一条会话记录。检查存在性时先调用 find，只有业务确实要求创建记录时才使用下标。

小节测试

对一个空的 `map<string, int>` 调用 `find` 查询缺失键后，容器大小仍为 0。

下面哪些操作可能在键原本不存在时增加 `map` 的大小？

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

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

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

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

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

cpp

#include <iostream>
#include <map>
#include <string>
 
int main() {
    std::multimap<std::string, int> positions = {
        {"build", 2},
        {"warn", 3},
        {"build", 5},
        {"build", 9}
    };
    const auto range = positions.equal_range("build");
    std::cout << "count: " << positions.count("build") << '\n';
    std::cout << "positions:";
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << ' ' << it->second;
    }
    std::cout << '\n';
    const auto lower = positions.lower_bound("build");
    const auto upper = positions.upper_bound("build");
    std::cout << std::boolalpha;
    std::cout << "same range: "
              << (lower == range.first && upper == range.second) << '\n';
    const auto missing = positions.equal_range("error");
    std::cout << "missing range empty: "
              << (missing.first == missing.second) << '\n';
}

输出：

text

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

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

查找之后怎样删除

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

cpp

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

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

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

建立索引，再使用索引

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

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

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

如果索引值保存指针或迭代器，必须保证基础记录的生命周期足够长，而且后续操作不会让这些位置失效。保存稳定编号通常更容易维护。

小节测试

遍历 `auto range = mm.equal_range(key)` 返回的全部匹配项时，循环终点应写成 `range.____`。

哪个接口能一次取得有序 multimap 中某个键的完整连续范围？

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

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

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

cpp

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

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

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

cpp

#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 > rhs.priority;
        }
        return lhs.id < rhs.id;
    }
};
 
int main() {
    std::set<Ticket, TicketOrder> queue = {
        {2, "B-2"},
        {3, "A-7"},
        {2, "A-1"},
        {2, "A-1"}
    };
    std::cout << "size: " << queue.size() << '\n';
    for (const Ticket& ticket : queue) {
        std::cout << ticket.priority << ':' << ticket.id << '\n';
    }
}

输出：

text

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；
顺序关系必须传递；
比较结果不能在容器存续期间因外部可变状态而改变。

multimap 等价键连续区间与比较器关系：lower_bound 和 upper_bound 形成半开范围，双向都不靠前的键彼此等价 — 边界查询与等价判断使用同一个比较器；严格弱序既决定遍历次序，也决定哪些键能落在同一连续范围内。

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

cpp

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

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

不要修改有序容器中参与比较的键。也不要让比较器读取一个会随时变化的全局开关。容器内部已经按照旧结果组织元素，比较规则中途变化会破坏所有查找前提。

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

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

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

小节测试

下面哪些性质是合格有序容器比较器应满足的？

有序 set 判断两个键是否等价时，必然调用这两个键的 operator==。

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

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

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

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

cpp

#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 = std::hash<std::string>{}(key.region);
        const std::size_t part = std::hash<int>{}(key.id);
        seed ^= part + 0x9e3779b9U + (seed << 6U) + (seed >> 2U);
        return seed;
    }
};
 
struct UserEqual {
    bool operator()(const UserKey& lhs, const UserKey& rhs) const noexcept {
        return lhs.region == rhs.region && lhs.id == rhs.id;
    }
};
 
int main() {
    using Directory =
        std::unordered_map<UserKey, std::string, UserHash, UserEqual>;
 
    Directory users;
    users.max_load_factor(1.0F);
    users.reserve(8);
    users.emplace(UserKey{"cn", 42}, "Lin");
    users.emplace(UserKey{"eu", 7}, "Mira");
    const auto found = users.find(UserKey{"cn", 42});
    std::cout << std::boolalpha;
    std::cout << "found cn/42: " << found->second << '\n';
    std::cout << "apac/42 missing: "
              << (users.find(UserKey{"apac", 42}) == users.end()) << '\n';
    std::cout << "size: " << users.size() << '\n';
    std::cout << "bucket capacity ready: "
              << (users.bucket_count() >= 8U) << '\n';
    const double computed_load =
        static_cast<double>(users.size()) /
        static_cast<double>(users.bucket_count());
    const double reported_load = static_cast<double>(users.load_factor());
    std::cout << "load formula holds: "
              << (std::fabs(computed_load - reported_load) < 0.000001) << '\n';
}

输出：

text

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

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

unordered_map 查找与扩容示意：键经过哈希进入桶，再由相等函数确认；rehash 改变桶布局、负载因子和迭代路径 — 哈希负责缩小候选桶，相等判断负责确认身份；扩容可以改善负载，却不会提供稳定的遍历顺序。

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

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

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

观察和调整桶状态

接口	含义
`bucket_count()`	当前桶数量
`bucket_size(i)`	第 i 个桶中的元素数
`bucket(key)`	某个键当前对应的桶号
`load_factor()`	`size() / bucket_count()`
`max_load_factor()`	容器允许的最大平均负载目标
`reserve(n)`	为大约 n 个元素预留桶容量
`rehash(n)`	请求至少能满足 n 个桶的布局

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

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

不要依赖无序遍历顺序

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

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

平均常数查找依赖合理的哈希分布。大量键集中到少数桶时，查找成本会升高。遇到性能异常时，应观察桶分布和负载，并检查哈希函数，而不是只调大桶数。

小节测试

自定义无序键必须满足哪条关系？

某无序容器有 10 个元素和 20 个桶，它的 load factor 是 ____。

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

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

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

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

cpp

#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 auto it = rules.find(word);
    return it == rules.end() ? word : it->second;
}
 
int main() {
    const std::map<std::string, std::string> rules = {
        {"cfg", "config"},
        {"tmp", "temporary"}
    };
    const std::set<std::string> ignored = {"temporary"};
    std::map<std::string, std::size_t> frequency;
    std::multimap<std::string, std::size_t> positions;
    std::vector<std::string> cleaned;
    std::istringstream input("cfg build warn build tmp warn");
    std::size_t position = 0;
    for (std::string raw; input >> raw;) {
        ++position;
        const std::string word = apply_rule(raw, rules);
        if (ignored.find(word) != ignored.end()) {
            continue;
        }
        cleaned.push_back(word);
        ++frequency[word];
        positions.emplace(word, position);
    }
    std::cout << "cleaned:";
    for (const std::string& word : cleaned) {
        std::cout << ' ' << word;
    }
    std::cout << '\n';
    std::cout << "frequency:\n";
    for (const auto& [word, count] : frequency) {
        std::cout << word << '=' << count << '\n';
    }
    const auto range = positions.equal_range("build");
    std::cout << "build positions:";
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << ' ' << it->second;
    }
    std::cout << '\n';
}

输出：

text

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，再通过另一张唯一键映射取得完整记录。这种分层方式允许建立多个索引：

查询	索引形状
单词到次数	`map<string, size_t>`
单词到全部位置	`multimap<string, size_t>`
记录 ID 到完整记录	`map<Id, Record>` 或无序版本
标签是否被屏蔽	`set<string>` 或无序版本

上线前的检查顺序

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

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

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

动手扩展

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

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

小节测试

综合文本索引中，哪些设计能避免只读查询意外改变数据？

如果最终报表必须稳定地按键升序输出，直接使用 map 往往比依赖 unordered_map 的遍历结果更清楚。

一个单词要关联所有出现位置，并且每个位置都要独立保留，最直接的索引形状是什么？

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

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

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

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

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

cpp

#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';
    }
}

输出：

text

index: 1
map: 3
set: 2

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

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

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

键和值分别承担什么职责

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

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

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

小节测试

只需要判断某个错误码是否在禁用名单中，最贴合语义的容器是哪一个？

执行 `++frequency[word]` 时，如果 word 尚不存在，整数计数器会先被值初始化为 ____。

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

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

先判断元素形状。只保存身份或成员资格时选 set 家族；一个键还要关联一份数据时选 map 家族。

再判断键是否允许重复。每个键只能代表一项时选唯一键版本；同一键需要保留多条独立记录时选 multi 版本。

最后判断是否需要按键遍历、边界查询或稳定排序输出。需要这些能力时选有序版本；只关心按键查找且数据量足够大时，可以考虑 unordered 版本。

元素形状	键是否重复	按键有序	不保证顺序
只保存键	否	`set<Key>`	`unordered_set<Key>`
只保存键	是	`multiset<Key>`	`unordered_multiset<Key>`
保存键值对	否	`map<Key, T>`	`unordered_map<Key, T>`
保存键值对	是	`multimap<Key, T>`	`unordered_multimap<Key, T>`

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

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

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

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

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

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

需求	更自然的选择
每条关联记录独立插入，并按键遍历全部记录	`multimap<Key, T>`
经常整体替换某个键对应的列表	`map<Key, vector<T>>`
每个关联值本身要参与容器级迭代	`multimap<Key, T>`
需要直接取得并修改整组值	`map<Key, vector<T>>`
同一键的值还需要自行排序、去重或随机访问	`map<Key, vector<T>>`

不要因为容器名里有 unordered 就默认它更合适。只要最终输出必须按键排序，无序容器就还需要额外排序；这部分成本和代码复杂度也应计入选择。

小节测试

下面哪些需求天然需要允许等价键重复？

只要查找很多，就一定应该把 std::map 换成 std::unordered_map。

看懂元素类型与插入结果

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

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

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

cpp

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

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

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

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

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

cpp

#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::boolalpha;
    std::cout << "first inserted: " << first.second
              << ", value: " << first.first->second << '\n';
    std::cout << "second inserted: " << second.second
              << ", value: " << second.first->second << '\n';
    if (!second.second) {
        ++second.first->second;
    }
    for (const auto& [key, value] : quotas) {
        std::cout << key << " => " << value << '\n';
    }
}

输出：

text

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

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

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

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

操作	键已存在时	适合的意图
`insert({key, value})`	保留旧值	只允许首次登记
`emplace(key, value)`	保留旧值	就地构造候选元素
`try_emplace(key, args...)`	不构造 mapped value	mapped value 构造较贵
`insert_or_assign(key, value)`	覆盖旧值	明确表达新增或更新
`operator[](key) = value`	先默认构造再赋值	mapped type 便宜且确实需要下标

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

忽略 insert 返回值之前，先确认重复键时的行为确实是“保留旧记录”。如果需求是用最新配置覆盖旧配置，应明确使用赋值或 insert_or_assign。

小节测试

向 `map<string, int>` 连续插入键相同、值分别为 3 和 9 的两个元素，第二次普通 insert 的结果是什么？

`std::map<Key, T>::value_type` 中，键的类型是 `____ Key`，因此不能通过迭代器原地修改。

把查询和写入分开

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

接口	缺失键的结果	会插入吗	适用对象
`find(key)`	返回 `end()`	否	所有关联容器
`count(key)`	返回匹配数量	否	所有关联容器
`at(key)`	抛出 `std::out_of_range`	否	`map`、`unordered_map`
`operator[](key)`	返回新插入的默认值	是	`map`、`unordered_map`

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

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

cpp

#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.find("tape");
    std::cout << std::boolalpha;
    std::cout << "find tape: " << (found != stock.end()) << '\n';
    std::cout << "size after find: " << stock.size() << '\n';
    try {
        static_cast<void>(stock.at("tape"));
    } catch (const std::out_of_range&) {
        std::cout << "at tape: missing\n";
    }
    std::cout << "size after at: " << stock.size() << '\n';
    std::cout << "operator[] value: " << stock["tape"] << '\n';
    std::cout << "size after []: " << stock.size() << '\n';
    stock["tape"] += 5;
    std::cout << "tape after update: " << stock.at("tape") << '\n';
}

输出：

text

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 往往更合适。

这类判断 if (sessions[id].active) 会在 id 缺失时创建一条会话记录。检查存在性时先调用 find，只有业务确实要求创建记录时才使用下标。

小节测试

对一个空的 `map<string, int>` 调用 `find` 查询缺失键后，容器大小仍为 0。

下面哪些操作可能在键原本不存在时增加 `map` 的大小？

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

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

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

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

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

cpp

#include <iostream>
#include <map>
#include <string>
 
int main() {
    std::multimap<std::string, int> positions = {
        {"build", 2},
        {"warn", 3},
        {"build", 5},
        {"build", 9}
    };
    const auto range = positions.equal_range("build");
    std::cout << "count: " << positions.count("build") << '\n';
    std::cout << "positions:";
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << ' ' << it->second;
    }
    std::cout << '\n';
    const auto lower = positions.lower_bound("build");
    const auto upper = positions.upper_bound("build");
    std::cout << std::boolalpha;
    std::cout << "same range: "
              << (lower == range.first && upper == range.second) << '\n';
    const auto missing = positions.equal_range("error");
    std::cout << "missing range empty: "
              << (missing.first == missing.second) << '\n';
}

输出：

text

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

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

查找之后怎样删除

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

cpp

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

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

建立索引，再使用索引

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

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

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

如果索引值保存指针或迭代器，必须保证基础记录的生命周期足够长，而且后续操作不会让这些位置失效。保存稳定编号通常更容易维护。

小节测试

遍历 `auto range = mm.equal_range(key)` 返回的全部匹配项时，循环终点应写成 `range.____`。

哪个接口能一次取得有序 multimap 中某个键的完整连续范围？

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

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

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

cpp

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

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

cpp

#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 > rhs.priority;
        }
        return lhs.id < rhs.id;
    }
};
 
int main() {
    std::set<Ticket, TicketOrder> queue = {
        {2, "B-2"},
        {3, "A-7"},
        {2, "A-1"},
        {2, "A-1"}
    };
    std::cout << "size: " << queue.size() << '\n';
    for (const Ticket& ticket : queue) {
        std::cout << ticket.priority << ':' << ticket.id << '\n';
    }
}

输出：

text

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；
顺序关系必须传递；
比较结果不能在容器存续期间因外部可变状态而改变。

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

cpp

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

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

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

小节测试

下面哪些性质是合格有序容器比较器应满足的？

有序 set 判断两个键是否等价时，必然调用这两个键的 operator==。

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

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

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

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

cpp

#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 = std::hash<std::string>{}(key.region);
        const std::size_t part = std::hash<int>{}(key.id);
        seed ^= part + 0x9e3779b9U + (seed << 6U) + (seed >> 2U);
        return seed;
    }
};
 
struct UserEqual {
    bool operator()(const UserKey& lhs, const UserKey& rhs) const noexcept {
        return lhs.region == rhs.region && lhs.id == rhs.id;
    }
};
 
int main() {
    using Directory =
        std::unordered_map<UserKey, std::string, UserHash, UserEqual>;
 
    Directory users;
    users.max_load_factor(1.0F);
    users.reserve(8);
    users.emplace(UserKey{"cn", 42}, "Lin");
    users.emplace(UserKey{"eu", 7}, "Mira");
    const auto found = users.find(UserKey{"cn", 42});
    std::cout << std::boolalpha;
    std::cout << "found cn/42: " << found->second << '\n';
    std::cout << "apac/42 missing: "
              << (users.find(UserKey{"apac", 42}) == users.end()) << '\n';
    std::cout << "size: " << users.size() << '\n';
    std::cout << "bucket capacity ready: "
              << (users.bucket_count() >= 8U) << '\n';
    const double computed_load =
        static_cast<double>(users.size()) /
        static_cast<double>(users.bucket_count());
    const double reported_load = static_cast<double>(users.load_factor());
    std::cout << "load formula holds: "
              << (std::fabs(computed_load - reported_load) < 0.000001) << '\n';
}

输出：

text

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) 必须相同。反过来不成立：哈希相同的两个键仍然可以不相等。

观察和调整桶状态

接口	含义
`bucket_count()`	当前桶数量
`bucket_size(i)`	第 i 个桶中的元素数
`bucket(key)`	某个键当前对应的桶号
`load_factor()`	`size() / bucket_count()`
`max_load_factor()`	容器允许的最大平均负载目标
`reserve(n)`	为大约 n 个元素预留桶容量
`rehash(n)`	请求至少能满足 n 个桶的布局

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

不要依赖无序遍历顺序

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

小节测试

自定义无序键必须满足哪条关系？

某无序容器有 10 个元素和 20 个桶，它的 load factor 是 ____。

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

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

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

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

cpp

#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 auto it = rules.find(word);
    return it == rules.end() ? word : it->second;
}
 
int main() {
    const std::map<std::string, std::string> rules = {
        {"cfg", "config"},
        {"tmp", "temporary"}
    };
    const std::set<std::string> ignored = {"temporary"};
    std::map<std::string, std::size_t> frequency;
    std::multimap<std::string, std::size_t> positions;
    std::vector<std::string> cleaned;
    std::istringstream input("cfg build warn build tmp warn");
    std::size_t position = 0;
    for (std::string raw; input >> raw;) {
        ++position;
        const std::string word = apply_rule(raw, rules);
        if (ignored.find(word) != ignored.end()) {
            continue;
        }
        cleaned.push_back(word);
        ++frequency[word];
        positions.emplace(word, position);
    }
    std::cout << "cleaned:";
    for (const std::string& word : cleaned) {
        std::cout << ' ' << word;
    }
    std::cout << '\n';
    std::cout << "frequency:\n";
    for (const auto& [word, count] : frequency) {
        std::cout << word << '=' << count << '\n';
    }
    const auto range = positions.equal_range("build");
    std::cout << "build positions:";
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << ' ' << it->second;
    }
    std::cout << '\n';
}

输出：

text

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

为什么转换查询不用下标

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

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

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

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

为什么位置索引保存编号

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

查询	索引形状
单词到次数	`map<string, size_t>`
单词到全部位置	`multimap<string, size_t>`
记录 ID 到完整记录	`map<Id, Record>` 或无序版本
标签是否被屏蔽	`set<string>` 或无序版本

上线前的检查顺序

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

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

动手扩展

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

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

小节测试

综合文本索引中，哪些设计能避免只读查询意外改变数据？

如果最终报表必须稳定地按键升序输出，直接使用 map 往往比依赖 unordered_map 的遍历结果更清楚。

一个单词要关联所有出现位置，并且每个位置都要独立保留，最直接的索引形状是什么？

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

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

键和值分别承担什么职责

小节测试

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

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

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

小节测试

看懂元素类型与插入结果

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

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

小节测试

把查询和写入分开

怎样选择查询接口

小节测试

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

查找之后怎样删除

建立索引，再使用索引

小节测试

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

严格弱序的四条实践规则

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

小节测试

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

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

观察和调整桶状态

不要依赖无序遍历顺序

小节测试

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

为什么转换查询不用下标

为什么位置索引保存编号

上线前的检查顺序

动手扩展

小节测试

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

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

键和值分别承担什么职责

小节测试

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

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

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

小节测试

看懂元素类型与插入结果

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

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

小节测试

把查询和写入分开

怎样选择查询接口

小节测试

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

查找之后怎样删除

建立索引，再使用索引

小节测试

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

严格弱序的四条实践规则

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

小节测试

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

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

观察和调整桶状态

不要依赖无序遍历顺序

小节测试

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

为什么转换查询不用下标

为什么位置索引保存编号

上线前的检查顺序

动手扩展

小节测试

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

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

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

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