我有以下场景:
- 我有一堆不需要按连续顺序排列的元素。
- 我将能够在初始化期间第一时间插入元素
- 我需要执行 containerA == containerB 操作。
N元素的个数最多可以是 100 个，但是要经过 avg。案例分析目的，我会说N可以是 100、10k 或 100k
鉴于 ，我的要求 std::set 不是一个好的选择。我可以使用 push_back N*O(1) 和 std::sort O(NlogN) 在向量中插入所有元素，并进行相等比较 (N) ; 2N+NlogN 的总数将轻松击败 std::set 内存/速度。
该主题已在此处得到很好的评价: http://lafstern.org/matt/col1.pdf 和这里: What is the difference between std::set and std::vector?
让我们看看如果我使用新的 unordered_set 会怎样。 N 元素的插入(N*O(1)) + 相等查找(N 平均情况)总计为 2N.
现在，我需要为 unordered_set 创建一个哈希器，这对我的情况来说并不容易。而且我猜测对于我的复杂数据结构，仅散列部分将导致它超过 2N。
但是，为什么对于一个简单的 unique_ptr 值插入，有人会得到以下性能结果: http://kohei.us/2010/03/31/stl-container-performance-on-data-insertion/
似乎向量排序 + 相等仍然比 unordered_set 效果更好，直到大量元素(100k)。 unordered_set 不使用红黑树吧？那么这种性能下降是从哪里来的呢？
这里有一个稍微相关的帖子: Performance of vector sort/unique/erase vs. copy to unordered_set
最佳答案
如果您的元素有一个简单的排序函数，并且您知道它们是不同的，那么最好将它们放在一个向量中并对其进行排序。理论上，具有良好哈希函数的基于哈希表的解决方案可以进行 O(n) 而不是 O(n log n) 的比较，但有许多缓解因素:
log n 是一个小数字。如果 n 是两亿，例如，log n 是 31(使用二进制日志，这通常是隐含的)。
标准库无序集合需要为每个元素分配一个空间。这是规范的有效要求，因为将元素添加到无序集合不会使对现有元素的引用无效，这与标准库向量的情况不同。
无序集合的迭代是按桶完成的(同样，这在规范中)，因此迭代涉及随机内存访问。对向量的迭代是顺序的，这对缓存更友好。
简而言之，即使排序是 O(n log n)，基于 O(n) 哈希的解决方案很可能具有较大的每个元素常量，并且由于 log n 是一个小数，因此基于矢量的解决方案会更快。通常要快得多。
基于哈希的解决方案会慢多少取决于分配器的速度，并且不同的标准库实现之间存在相当大的差异。但即使是超快速的分配器也不太可能为您提供具有竞争力的性能，并且当您的表变得足够大时，哈希表的缓存不友好性将变得很重要。
即使您有一些重复元素，使用向量可能会更好，但这取决于您有多少重复项。由于哈希表占用的内存可能至少是具有相同元素数量的向量的两倍，所以一个简单的经验法则可能是使用向量，只要您不期望元素的数量超过独特元素数量的两倍。 (排序后很容易消除重复项。有一个标准库函数可以做到这一点。)
关于STL vector+sort+equality vs. unordered_set vs. using pure set 的性能(内存和速度方面)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29194904/