我应该使用std::set还是std::unordered_set来存储指针集合？

Question

我有一组指针。第一步，我插入数据指针；第二步，遍历整个集合并对元素执行一些操作。顺序不重要，只需避免重复，而使用指针比较可以很好地实现此功能。

我的问题是，是否使用无序集合可能更有优势？无序集合的插入速度是否更快？

- Fabian

---

“顺序无关紧要”-一旦你决定了这一点，可以使用unordered_set。有序容器唯一的优点是… 顺序。 - Ami Tavory

我们要讨论多少个元素？并且您是对每个项目进行计算密集型工作，还是更像对所有元素进行求和/乘法运算？ - MikeMB

有序容器还有一个重要的优势，就是可以保证每个操作的时间复杂度为O(lg n)，而无序容器在最坏情况下需要O(n)。因此，如果你想对复杂度做出承诺，应该使用std::set。 - James

@James：这适用于哪些操作，例如？在我的用例中，我仅限于使用clear()、insert()和iteration。 - Fabian

@Fabian：如果所有元素最终都落在同一个桶中，insert()的时间复杂度可能为O(n)，但使用指针会非常不幸。 - MikeMB

Answer 1

如Ami Tavory所述，如果你不需要顺序，则通常最好选择无序容器。原因是，如果顺序在某种程度上改善了性能，则无序容器仍可免费使用它，并且从根本上获得相同或更好的复杂度。

无序集合的一个缺点是，它们通常需要一个关键类型的哈希函数。如果制作哈希函数太困难或成本太高，则可能更好地使用不使用哈希的容器。

在C++标准库中，std::set的平均插入复杂度为O(log(N))，而std::unordered_set的插入复杂度为O(1)。除此之外，使用std::unordered_set时平均缓存未命中可能较少。

但归根结底，这只是理论。你应该尝试一些听起来足够好的方法，并对其进行分析以查看是否真的有效。

- Yam Marcovic

---

对于指针，这就是问题所在，标准库中有一个“std::hash”的专门化，所以不用担心。 - Jonas Schäfer

既然你提到了复杂度：最坏情况下的查找对于原始问题并不相关，但是无序集合的O(N)可能是选择有序集合的原因。另一个支持默认使用无序集合的论点是表达意图：读者可以看出你不关心顺序。 - peterchen

@Revolver_Ocelot 实际上，我认为在C++中结果只是未指定的。此外，std::set使用std::less，即使对于指针也保证了完全排序。 - MikeMB

可能相关：Chandler Carruth（clang和编译器优化方面的专家）认为，在当今的缓存行为下，std::unordered_map 应该成为首选的默认方式，而不是 std::map。他指出，每次在代码中看到 std::map，就意味着在性能方面存在问题。 - Yam Marcovic

@Revolver_Ocelot：没有异议。我只是说它是未指定的而不是未定义的（我仍然相信这一点），更重要的是，在std::set中使用指针是安全的。我认为我们在后者上达成了共识，这使得前者有些离题，但如果你愿意，我们可以在聊天中讨论这个问题。 - MikeMB