最常用数据结构是std::unordered_map；词项为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
<p>常见错误：<br>• 忘记预排序：如果 vector 没排序（比如插入时乱序），归并失效，结果错漏<br>• 用 <code>std::set_intersection</code> 却传入非随机访问迭代器（如 list），性能暴跌<br>• 对 OR 查询也硬套 AND 归并逻辑，其实 OR 应该用 merge + unique，或直接用 <code>std::set_union</code></p>
<h3>如何支持短语查询（"C++ standard" 相邻匹配）</h3>
<p>光靠倒排索引的文档 ID 列表不够，必须额外记录词在文档内的位置（position）。把 value 类型升级为 <code>std::vector<:pair std::vector>>></:pair></code>：外层 vector 按 doc ID 排序，每个元素是 <code>(doc_id, positions)</code>，其中 <code>positions</code> 是该词在该文档中所有出现的位置（比如 <code>[3, 15, 22]</code>）。</p>
<p>查短语时，先取各词的 position 列表，再对齐 doc ID，然后检查是否存在一组位置满足相邻关系。例如查 <code>"A B"</code>，对某个共同 doc ID，遍历 A 的每个 pos_a，看 pos_a + 1 是否在 B 的 positions 里——用 <code>std::binary_search</code> 查，别用线性 find。</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/gongju/2823" title="C++14"><img
src="https://img.php.cn/upload/manual/001/431/639/6ac8b33c327c4749.png" alt="C++14" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="overflowclass">C++14</a>
<p class="overflowclass">C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。</p>
</div>
<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
<p>容易被忽略的点：<br>• 位置索引让内存占用翻倍以上，上线前务必压测内存<br>• 中英文分词差异大：C++ 代码里 “<code>std::vector</code>” 是一个 token 还是三个？取决于你的分词器，不是倒排索引本身能解决的<br>• 标点符号处理不干净会导致位置偏移，建议分词后统一过滤掉纯标点 token</p>
<h3>什么时候该加锁，以及为什么不能只锁整个 map</h3>
<p>多线程构建索引时，不同线程写不同词项（key），所以用 <code>std::shared_mutex</code> 给每个 bucket 或每个 key 加细粒度锁，比全局 <code>std::mutex</code> 高效得多。C++17 起可用 <code>std::shared_mutex</code>，读多写少场景尤其明显。</p>
<p>但如果只是单次构建 + 多次只读查询，构建完调用 <code>index.shrink_to_fit()</code>，然后用 <code>const</code> 引用传递给查询线程，根本不需要锁——这才是最高效的做法。</p>
<p>踩坑提醒：<br>• 在查询路径里用 <code>std::map</code> 替代 <code>std::unordered_map</code>，以为能省锁，结果哈希冲突多时单次查找退化成 O(n)，得不偿失<br>• 写日志或统计时在查询关键路径里加锁 printf，IO 拖垮吞吐<br>• 忘记 <code>std::vector</code> 的 <code>push_back</code> 在扩容时可能触发重分配，导致迭代器失效——构建阶段避免边遍历边修改同一容器</p>
<p>倒排索引真正的复杂点不在数据结构本身，而在于分词一致性、位置精度控制、以及构建与查询阶段的内存生命周期管理——这些地方出问题，性能会断崖式下跌，但错误往往不报异常，只表现为召回率低或响应变慢。</p></size_t></size_t></size_t></size_t>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
