std::set和std::vector有什么区别？

Question

我现在正在学习STL。我读了有关set容器的内容。当你想使用set时有什么问题吗？阅读set的描述后，它看起来毫无用处，因为我们可以用vector代替它。您能说出vector与set容器的优缺点吗？谢谢。

- ashim

---

既然你已经了解了集合，那么也要了解映射。然后再试着进行比较！ - Vinayak Garg

请慎重选择您的容器 - Mr.Anubis

Answer 1

一个set是有序的。根据你提供的函数对象，它保证始终保持在特定顺序中。无论添加或删除什么元素（除非你添加了重复项，在set中不允许），它总是有序的。

一个vector只有你明确给出的顺序。在vector中的项目就在你放置它们的位置。如果你按照顺序放置它们，那么它们就是有序的；否则，你现在需要对容器进行排序，以使它们重新排列。

诚然，set的使用相对有限。通过适当的约束，可以将项插入到vector中并保持其有序。但是，如果你不断地向容器中添加和移除项，则vector将遇到许多问题。它将执行许多元素的复制/移动等操作，因为它实际上只是一个数组。

向vector中插入一项所需的时间与vector中已经存在的项的数量成正比。向set中插入一项所需的时间与项数的log₂成正比。如果项数很大，则这是一个巨大的速度改进。log₂(100,000)约为16；这是一个重大的速度改进。移除也是如此。

但是，如果你在初始化时一次性完成所有插入，则没有问题。你可以将所有内容插入vector，对其进行排序（支付那个价格一次），然后使用排序vectors的标准算法来查找元素并迭代排序列表。虽然遍历set中的元素不是特别慢，但遍历vector更快。

有些情况下，经过排序的vector会比set更快。尽管如此，除非你知道这种优化是必要的，否则你真的不应该费心去做。所以，除非你对你正在编写的系统有经验（从而知道你需要这种性能），或者手头有分析数据告诉你需要使用vector而不是set，否则请使用set。

- Nicol Bolas

---

但是 set 是否被排序只是一种实现细节，从数学角度来讲，集合本身没有顺序。 - Paul Manta

一个 std::set 并不是由数学定义的，它是由 C++ 规范定义的。规范指定它是有序的。 - Nicol Bolas

除非有好的理由，否则请使用集合。嗯...也许最好遵循Stroupstrup的建议：“是的，我的建议是默认使用std::vector。更一般地说，除非有充分的理由不这样做，否则请使用连续表示。” - user146043

@Alex：在这种情况下，不需要。如果你考虑使用set，那么顺序显然对你很重要。保持std::vector排序需要大量的努力。你基本上必须围绕容器构建一个类型。所以我不建议这样做，除非你知道有合法的性能提升。当然，如果你有访问flat_set的权限，那么几乎没有理由使用常规的set。 - Nicol Bolas

Python用户需要注意的一个陷阱是：Python中的set是无序的，但C++中的std::set则是有序的。 - liberforce

Answer 2

它们是不同的东西：向量的排序由您决定，并且您还可以将任意数量的相等元素放入到向量中。集合按照该集合的内部规则排序（您可以设置规则，但集合会处理排序），并且您不能在集合中放入多个相等的项。

当然，您可以维护一个唯一项的向量，但是当您执行面向集合的操作时，性能会受到很大影响。例如，假设您有一个包含10000个项的集合和一个包含10000个不同无序项的向量。现在假设您需要检查值X是否在集合中（或者在向量中的值中）。当X不在这些项中时，在向量中搜索会慢大约100倍。计算集合的并集和交集时也会出现类似的性能差异。

总之，向量和集合有不同的目的。您可以使用向量代替集合，但这需要更多的工作，并且可能会严重影响性能。

- Sergey Kalinichenko

---

独特性值得点赞，我无法相信没有其他人注意到这一点。独特性是主要的优点。虽然不想贬低它，但即使在理论上速度可能会慢一些 - 尽管通常只在设置部分而不是速度要求高的部分中出现幷且我只担心以后只能勉强读懂代码！例如，我想确保将一个项目放入容器中，但只能放一次; 写 set.emplace(it) 似乎要好得多，而不是 if (vec.find(it) != vec.end() ) { vec.emplace(it) }（对于 erase 更是如此！） - underscore_d

Answer 3

表单 cpluplus.com 中的set：

set是一种容器，它按照特定顺序存储唯一元素。

因此，set是有序的并且项目具有唯一性。

而vect：

向量是表示可以改变大小的数组的序列容器。

因此，vector按您填充它的顺序，并且可以容纳多个相同的项。

推荐使用set：

• 如果您希望过滤多个相同的值
• 如果您希望按指定顺序解析项目（在vector中执行此操作需要明确地对vector进行排序）。

推荐使用vector：

• 如果您想保留相同的值
• 如果您希望按您将它们推入的顺序解析项目（假设您不处理vector顺序）

- jo_

---

在我看来，这是最好的答案。被采纳的回答太难理解了。这个回答直截了当。 - Sriram Murali

Answer 4

简单的区别是set只能包含唯一的值，并且它是有序的。因此，你可以将其用于需要在每次插入/删除后连续排序值的情况。

set<int> a;
vector<int> b;
for (int i = 0; i < 10; ++i)
{
    int val = rand() % 10;
    a.insert(val);
    b.push_back(val);
}
cout << "--SET---\n"; for (auto i : a) cout << i << ","; cout << endl;
cout << "--VEC---\n"; for (auto j : b) cout << j << ","; cout << endl;

输出为：

--SET---
0,1,2,4,7,8,9,
--VEC---
1,7,4,0,9,4,8,8,2,4,

- Sriram Murali

Answer 5

对比向量（O(n)）和集合（O(log(n))），在集合中搜索项目更快。使用向量搜索项目需要迭代向量中的所有项目，但是集合使用红黑树来优化搜索，只需查找少量项目即可找到匹配项。

集合是有序的，这意味着您只能按顺序从最小的开始迭代它，或者按相反的顺序。

但是向量是无序的，您可以按插入顺序遍历它。

- Zang MingJie

---

不是真的。你可以在std :: vector上执行std :: binary_search，它会进行对数次比较。 - Arlen

只有在向量已经排序的情况下，二分查找才是有效的。 - rsaxvc