c++ - std::set 和 std::vector 有什么区别？

Question

我现在正在学习 STL。我读到了 set 容器。当您想使用 set 时，我有疑问？看完description of set看起来它没用，因为我们可以用 vector 代替它。您能否说说 vector 与 set 容器的优缺点。谢谢

Answer 1

一个 set 是有序的。根据您提供的仿函数，保证保持特定顺序。无论您添加或删除什么元素(除非您添加重复项，这在 set 中是不允许的)，它始终是有序的。

vector 完全具有并且仅 您明确给出的顺序。 vector 中的项目是您放置它们的位置。如果你把它们乱序，那么它们就是乱序的；您现在需要对容器进行排序以将它们按顺序放回原处。

诚然，set 的用途相对有限。通过适当的纪律，可以将项目插入 vector 并使其保持有序。但是，如果您不断地在容器中插入和删除项目，vector 会遇到很多问题。它将执行大量元素的复制/移动等操作，因为它实际上只是一个数组。

将一个项目插入到 vector 所需的时间与 vector 中已有的项目数成正比。将项目插入 set 所需的时间与项目数的 log₂ 成正比。如果项目的数量很大，那将是一个巨大的差异。 log2(100,000) 是 ~16；这是一个重大的速度改进。移除也是如此。

但是，如果您在初始化时一次性完成所有插入操作，则没有问题。您可以将所有内容插入到 vector 中，对其进行排序(支付一次)，然后使用标准算法对已排序的 vectors 查找元素并遍历已排序的列表。虽然对 set 元素的迭代并不是很慢，但对 vector 的迭代更快。

所以在某些情况下，排序的 vector 优于 set。话虽如此，除非您知道有必要，否则您真的不应该为这种优化的费用而烦恼。所以使用 set 除非你对你正在编写的系统有经验(因此知道你需要那种性能)或者手头有分析数据告诉你需要一个 vector 而不是set。