高效遍历嵌套vector构建反向映射实现快速查找的方法

首先明确：你提到的两层遍历构建unordered_map反向索引的思路，本身就是这个需求的标准解法，只要是拿到getSsc()结果后一次性构建索引、后续所有查询直接读索引，这个方案的时间复杂度已经是理论最优级别：构建总耗时O(M)（M是所有cid的总数量），单次查询平均O(1)，不存在量级上更优的算法。你能做的优化都是针对具体数据特征、降低实现的常数项开销，根据你的业务数据特征可以选下面几种方案：

1. cid为稠密整数时：用vector替代unordered_map，性能拉满 #

如果你的cid是整数类型，且取值分布集中（比如从1到10000连续排布，没有很大的数值空洞），直接用连续内存的vector存反向映射，比unordered_map快30%以上，内存占用也低很多：

• 先遍历一遍所有cid，找到cid的最小值、最大值，确定vector需要的长度
• 第二次遍历SSC结构，把每个cid对应的sid直接存在vector对应下标的位置
• 查询的时候直接按下标取值，连哈希计算、冲突判断的开销都没有
  参考实现：

// 这里假设cid、sid都是无符号整数类型，根据你的实际类型修改即可
cid_type min_cid = std::numeric_limits<cid_type>::max();
cid_type max_cid = std::numeric_limits<cid_type>::min();
// 第一遍扫描确定cid范围
for (const auto& s_entry : SSC) {
    for (auto cid : s_entry.cid_list) {
        min_cid = std::min(min_cid, cid);
        max_cid = std::max(max_cid, cid);
    }
}
// 构建vector索引
std::vector<sid_type> cid2sid(max_cid - min_cid + 1);
for (sid_type sid = 0; sid < SSC.size(); sid++) {
    for (auto cid : SSC[sid].cid_list) {
        cid2sid[cid - min_cid] = sid;
    }
}
// 查询示例：找cid=5对应的sid，直接取cid2sid[5 - min_cid]即可

2. cid分布稀疏、查询QPS极高：用高性能平坦哈希表替代STL unordered_map #

如果cid取值很分散、用vector会浪费大量内存，且你的服务查询量很大，可以换用开放寻址法实现的平坦哈希表存反向映射，相比STL默认采用链地址法实现的unordered_map，构建和查询速度可以提升2~5倍，内存占用也更低，本质还是O(1)的查询复杂度，只是常数项小很多。

3. 极端内存受限场景：不建全量索引，用排序+二分 #

如果你实在拿不出额外内存存全量cid的映射，且sid的总数量远小于cid总数量，可以退而求其次：

• 拿到SSC后，给每个sid下属的cid列表做原地排序
• 查询目标cid时，遍历每个sid，在其排序后的cid列表里做二分查找，判断cid是否存在
  这个方案不需要额外存全量映射，但是单次查询复杂度是O(S * logC)（S是sid总数，C是单个sid下的平均cid数），只有sid数量特别少的时候才划算，99%的业务场景都不推荐用。

避坑提醒 #

不要每次查询都临时两层遍历SSC做匹配，这种方式单次查询复杂度就是O(M)，只要查询次数超过1次，总耗时就远高于提前建一次索引反复使用。
不存在“零开销还能比反向索引更快”的黑科技，所有快速查找本质都是用提前构建的时间成本、存储的空间成本换查询速度，根据自己的数据特征选常数开销最低的索引结构就行。

内容的提问来源于stack exchange，提问作者vijaychsk