什么场景下值得将std::vector替换为std::unordered_set？

核心结论 #

元素量稳定在10个以内时，优先选择std::vector做线性遍历查找，完全没必要使用std::unordered_set。

原因说明 #

• 哈希计算有固定基础开销：即便是int这类最简单的键类型，标准库哈希函数的单次计算耗时，已经相当于3~5次整数相等比较的耗时；如果是字符串、自定义结构体这类复杂键，哈希计算的开销还会更高，远超过遍历5个元素的总比较成本。
• std::unordered_set存在额外隐性开销：除了哈希计算，查找时还需要处理哈希冲突、跳转访问哈希桶节点，这些操作属于随机内存访问，对CPU缓存极不友好。而std::vector的元素连续存储，遍历时CPU可以提前做缓存预取，实际运行效率远高于O(n)时间复杂度的理论预估。

切换std::unordered_set的阈值 #

• 一般当元素量超过20~30个时，std::unordered_set的平均查找性能才会反超线性遍历的std::vector，具体阈值和键类型、哈希函数实现有关，你可以针对自己的业务场景做简单基准测试确认。
• 如果你的场景存在频繁的插入、删除操作，哪怕元素量偏小也可以考虑std::unordered_set，避免std::vector插入删除时移动元素的开销，但元素量只有5个的场景下，这点开销差异基本可以忽略。

额外优化建议 #

如果你的容器元素上限固定且数值很小，甚至可以直接手写硬编码的相等判断逻辑，性能比遍历std::vector还要高。

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