STL vector+sort+equality 与 unordered_set 与使用纯集的性能（内存和速度方面）
Performance(memory and speed wise) for a STL vector+sort+equality vs. unordered_set vs. using pure set
我有以下场景：
- 我有一堆不需要按连续顺序排列的元素。
- 我可以在初始化时第一时间插入元素
- 我需要执行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 memory/speed。
该主题已在此处得到很好的评价：
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不会用红黑树吧？那么这种性能下降来自哪里？
稍微相关的 post 在这里：
Performance of vector sort/unique/erase vs. copy to unordered_set
如果您的元素具有简单的排序功能，并且您知道它们是不同的，那么最好将它们放在一个向量中并对其进行排序。理论上，具有良好散列函数的基于散列 table 的解决方案可以进行 O(n) 而不是 O(n log n) 的比较，但有许多缓解因素：
log n 是一个小数。如果n是两亿，比如log n就是31（使用二进制日志，通常是隐含的）
标准库无序集合需要为每个元素进行分配。这是规范的有效要求，因为将元素添加到无序集合不会使对现有元素的引用无效，这与标准库向量的情况不同。
无序集合的迭代是按桶完成的（同样，这在规范中），结果是迭代涉及随机内存访问。迭代向量是顺序的，这对缓存更友好。
简而言之，即使排序是 O(n log n)，基于 O(n) 哈希的解决方案很可能具有较大的每个元素常量，并且由于 log n 是一个小数，基于矢量的解决方案会更快。通常要快得多。
基于哈希的解决方案会慢多少取决于分配器的速度，并且不同的标准库实现之间存在相当大的差异。但即使是超快速分配器也不太可能为您提供有竞争力的性能，并且当您的 table 变得足够大时，散列 table 的缓存不友好性将变得很重要。
即使您有一些重复元素，使用向量可能会更好，但这取决于您有多少重复元素。由于散列 table 可能占用的内存至少是具有相同元素数量的向量的两倍，所以一个简单的经验法则可能是使用向量，只要您不期望元素的数量是独特元素数量的两倍以上。 （排序后很容易消除重复项。有一个标准库函数可以做到这一点。）
我有以下场景：
- 我有一堆不需要按连续顺序排列的元素。
- 我可以在初始化时第一时间插入元素
- 我需要执行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 memory/speed。
该主题已在此处得到很好的评价： 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不会用红黑树吧？那么这种性能下降来自哪里？
稍微相关的 post 在这里： Performance of vector sort/unique/erase vs. copy to unordered_set
如果您的元素具有简单的排序功能，并且您知道它们是不同的，那么最好将它们放在一个向量中并对其进行排序。理论上，具有良好散列函数的基于散列 table 的解决方案可以进行 O(n) 而不是 O(n log n) 的比较，但有许多缓解因素：
log n 是一个小数。如果n是两亿，比如log n就是31（使用二进制日志，通常是隐含的）
标准库无序集合需要为每个元素进行分配。这是规范的有效要求，因为将元素添加到无序集合不会使对现有元素的引用无效，这与标准库向量的情况不同。
无序集合的迭代是按桶完成的（同样，这在规范中），结果是迭代涉及随机内存访问。迭代向量是顺序的，这对缓存更友好。
简而言之，即使排序是 O(n log n)，基于 O(n) 哈希的解决方案很可能具有较大的每个元素常量，并且由于 log n 是一个小数，基于矢量的解决方案会更快。通常要快得多。
基于哈希的解决方案会慢多少取决于分配器的速度，并且不同的标准库实现之间存在相当大的差异。但即使是超快速分配器也不太可能为您提供有竞争力的性能，并且当您的 table 变得足够大时，散列 table 的缓存不友好性将变得很重要。
即使您有一些重复元素，使用向量可能会更好，但这取决于您有多少重复元素。由于散列 table 可能占用的内存至少是具有相同元素数量的向量的两倍，所以一个简单的经验法则可能是使用向量，只要您不期望元素的数量是独特元素数量的两倍以上。 （排序后很容易消除重复项。有一个标准库函数可以做到这一点。）