最常用数据结构是std::unordered_map<std::string, std::vector<size_t>>；词项为key，文档ID列表为value，用双指针归并实现高效AND查询。
倒排索引该用什么数据结构存词项和文档ID
直接用 std::unordered_map<:string std::vector>></:string> 是最常见也最实用的选择。词项（term）做 key，对应的所有文档 ID（用 size_t 表示 doc ID）存在 vector 里。别一上来就考虑跳表或 B+ 树——除非你明确要支持亿级文档且要求毫秒级范围查询，否则 vector 的局部性好、插入快、遍历时 cache 友好，比 std::set 或 std::unordered_set 更合适。
注意两点：
• 文档 ID 建议从 0 开始连续编号，避免用原始文件路径或 UUID 当 ID，否则排序/交集计算会变慢
• 如果需要支持“同一个文档中多次出现某词”，vector 里就存重复 ID；若只需知道“是否出现”，插入前查重或改用 std::unordered_set，但实测中多数场景保留重复更利于 TF 计算
怎么高效合并多个词项的文档列表（AND 查询）
核心是双指针归并，不是暴力嵌套循环。比如查 "cpp AND template"，拿到两个已排序的 std::vector<size_t></size_t>，用两个下标同步前进：
std::vector<size_t> intersect(const std::vector<size_t>& a, const std::vector<size_t>& b) {
std::vector<size_t> res;
size_t i = 0, j = 0;
while (i < a.size() && j < b.size()) {
if (a[i] == b[j]) {
res.push_back(a[i]);
++i; ++j;
} else if (a[i] < b[j]) {
++i;
} else {
++j;
}
}
return res;
}
常见错误：
• 忘记预排序：如果 vector 没排序（比如插入时乱序），归并失效，结果错漏
• 用 std::set_intersection 却传入非随机访问迭代器（如 list），性能暴跌
• 对 OR 查询也硬套 AND 归并逻辑，其实 OR 应该用 merge + unique，或直接用 std::set_union
立即学习“C++免费学习笔记（深入）”；
如何支持短语查询（"C++ standard" 相邻匹配）
光靠倒排索引的文档 ID 列表不够，必须额外记录词在文档内的位置（position）。把 value 类型升级为 std::vector<:pair std::vector>>></:pair>：外层 vector 按 doc ID 排序，每个元素是 (doc_id, positions)，其中 positions 是该词在该文档中所有出现的位置（比如 [3, 15, 22]）。
查短语时，先取各词的 position 列表，再对齐 doc ID，然后检查是否存在一组位置满足相邻关系。例如查 "A B"，对某个共同 doc ID，遍历 A 的每个 pos_a，看 pos_a + 1 是否在 B 的 positions 里——用 std::binary_search 查，别用线性 find。
容易被忽略的点：
• 位置索引让内存占用翻倍以上，上线前务必压测内存
• 中英文分词差异大：C++ 代码里 “std::vector” 是一个 token 还是三个？取决于你的分词器，不是倒排索引本身能解决的
• 标点符号处理不干净会导致位置偏移，建议分词后统一过滤掉纯标点 token
什么时候该加锁，以及为什么不能只锁整个 map
多线程构建索引时，不同线程写不同词项（key），所以用 std::shared_mutex 给每个 bucket 或每个 key 加细粒度锁，比全局 std::mutex 高效得多。C++17 起可用 std::shared_mutex，读多写少场景尤其明显。
但如果只是单次构建 + 多次只读查询，构建完调用 index.shrink_to_fit()，然后用 const 引用传递给查询线程，根本不需要锁——这才是最高效的做法。
踩坑提醒：
• 在查询路径里用 std::map 替代 std::unordered_map，以为能省锁，结果哈希冲突多时单次查找退化成 O(n)，得不偿失
• 写日志或统计时在查询关键路径里加锁 printf，IO 拖垮吞吐
• 忘记 std::vector 的 push_back 在扩容时可能触发重分配，导致迭代器失效——构建阶段避免边遍历边修改同一容器
倒排索引真正的复杂点不在数据结构本身，而在于分词一致性、位置精度控制、以及构建与查询阶段的内存生命周期管理——这些地方出问题，性能会断崖式下跌，但错误往往不报异常，只表现为召回率低或响应变慢。
