c++ - 什么时候值得从 std::vector 更改为 std::unordered_set？

Question

我想用很少的元素制作一个容器，我将只检查一个元素是否是该集合的一部分。我知道如果集合足够大，向量将不是合适的容器，因为每项研究都是最坏情况的 O(n)，并且有更好的选择使用散列函数或二叉树。但是我想知道如果我的集合只有很少的元素（例如只有 5 个）并且我事先知道会发生什么，将容器实现为具有哈希函数的结构是否值得？也许如果集合不够大，则必须应用散列函数引入的开销大于必须遍历 5 个元素。

例如在 C++ 中使用 std::unordered_set 而不是 std::vector。一如既往，谢谢

标签： c++

Answer 1

有许多因素会影响std::vector落后于其他方法的点。看到std::vector 比 std::unordered_set 快？和向量排序/唯一/擦除的性能与复制到 unordered_set的一些原因是这种情况。因此，对这一点的任何计算都必须相当复杂和复杂。找到这一点最方便的方法是性能测试。

请记住，某些因素取决于所使用的硬件。因此，您不仅需要在开发机器上进行性能测试，还需要在“典型”最终用户机器上进行性能测试。但是，您的开发机器可以让您进行直觉检查（就像Quick Bench之类的在线工具一样），让您知道您甚至还没有进入球场。（个别程序员的直觉是出了名的不可靠。有些人认为 100 是一个很大的数字并担心性能；另一些人直到数字达到数十亿才担心。这些人中的任何一个都会被其他人的观点所震撼。）

鉴于难以确定std::vector落后的点，我认为这是提醒人们过早优化通常是浪费时间的好地方。出于好奇调查此性能是可以的，但在将其确定为性能瓶颈之前，请不要为此搁置项目更重要方面的工作。选择最适合您的代码的方法。

话虽如此，我个人认为断点很好，超过 10 个项目。因此，对于问题的 5 元素集合，我倾向于使用向量而不是回头看。