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

What is the difference between std::set and std::vector?

提问by ashim

I am learning STL now. I read about setcontainer. I have question when you want to use set? After reading description of setit looks like it is useless because we can substitute it by vector. Could you say pros and cos for vectorvs setcontainers. Thanks

我现在正在学习 STL。我读过set容器。我有疑问，你什么时候想用set？在阅读了 set 的描述之后，它看起来没什么用，因为我们可以用 来代替它vector。你能说一下vectorvsset容器的优缺点吗？谢谢

回答by Nicol Bolas

A setis ordered. It is guaranteedto remain in a specific ordering, according to a functor that you provide. No matter what elements you add or remove (unless you add a duplicate, which is not allowed in a set), it will always be ordered.

Aset被订购。根据您提供的函子，它保证保持特定顺序。无论您添加或删除什么元素（除非您添加重复项，这在 a 中是不允许的set），它将始终按顺序排列。

A vectorhas exactly and onlythe ordering you explicitly give it. Items in a vectorare where you put them. If you put them in out of order, then they're out of order; you now need to sortthe container to put them back in order.

Avector完全且仅具有您明确给出的顺序。avector中的项目是您放置它们的位置。如果你把它们弄乱了，那么它们就乱了；您现在需要到sort容器中将它们放回原处。

Admittedly, sethas relatively limited use. With proper discipline, one could insert items into a vectorand keep it ordered. However, if you are constantly inserting and removing items from the container, vectorwill run into many issues. It will be doing a lot of copying/moving of elements and so forth, since it is effectively just an array.

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

The time it takes to insert an item into a vectoris proportional to the number of items already in the vector. The time it takes to insert an item into a setis proportional to the log?of the number of items. If the number of items is large, that's a huge difference. log?(100,000) is ~16; that's a major speed improvement. The same goes for removal.

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

However, if you do all of your insertions at once, at initialization time, then there's no problem. You can insert everything into the vector, sort it (paying that price once), and then use standard algorithms for sorted vectorsto find elements and iterate over the sorted list. And while iteration over the elements of a setisn't exactly slow, iterating over a vectoris faster.

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

So there are cases where a sorted vectorbeats a set. That being said, you really shouldn't bother with the expense of this kind of optimization unless you know that it is necessary. So use a setunless you have experience with the kind of system you're writing (and thus know that you need that performance) or have profiling data in hand that tells you that you need a vectorand not a set.

因此，在某些情况下，排序vector优于 a set。话虽如此，除非您知道这是必要的，否则您真的不应该为这种优化的费用而烦恼。因此，set除非您对正在编写的系统类型有经验（因此知道您需要该性能）或手头有分析数据告诉您需要 avector而不是set.

回答by dasblinkenlight

They are different things: you decide how vectors are ordered, and you can also put as many equal things into a vector as you please. Sets are ordered in accordance to that set's internal rules (you may set the rules, but the set will deal with the ordering), and you cannot put multiple equal items into a set.

它们是不同的东西：你决定向量的排序方式，你也可以根据需要将尽可能多的相等的东西放入向量中。集合按照集合的内部规则进行排序（您可以设置规则，但是集合会处理排序），并且您不能将多个相等的项目放入一个集合中。

Of course you could maintain a vector of unique items, but your performance would suffer a lot when you do set-oriented operations. For example, assume that you have a set of 10000 items and a vector of 10000 distinct unordered items. Now suppose that you need to check if a value X is among the values in the set (or among the values in the vector). When X is not among the items, searching the vector would be some 100 times slower. You would see similar performance differences on calculating set unions and intersections.

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

To summarize, sets and vectors have different purposes. You can use a vector instead of a set, but it would require more work, and would likely hurt the performance rather severely.

总而言之，集合和向量有不同的目的。您可以使用向量而不是集合，但这需要更多的工作，并且可能会严重损害性能。

回答by jo_

form cpluplus.comset:

表单cluplus.com集：

Sets are containers that store unique elements following a specific order.

集合是按照特定顺序存储唯一元素的容器。

so the set is ordered AND item are uniquely represented

所以集合是有序的，并且项目是唯一表示的

while vect:

而向量：

Vectors are sequence containers representing arrays that can change in size.

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

so vector is in the order you fill it AND can hold multiple identical items

所以向量按照你填写的顺序，并且可以容纳多个相同的项目

prefer set:

喜欢套装：

• if you wish to filter multiple identical values
• if you wish to parse items in a specified order (doing this in vector requires to specifically sort vector).

• 如果您希望过滤多个相同的值
• 如果您希望以指定的顺序解析项目（在向量中执行此操作需要专门对向量进行排序）。

prefer vector:

更喜欢向量：

• if you want to keep identical values
• if you wish to parse items in same order as you pushed them (assuming you don't process the vector order)

• 如果你想保持相同的值
• 如果您希望以与推送它们相同的顺序解析项目（假设您不处理向量顺序）

回答by Zang MingJie

it is faster to search an item against a set than a vector (O(log(n)) vs O(n)). To search an item against a vector, you need to iterate all items in the vector, but the set use red-black tree to optimize the search, only a few item will be looked to find a match.

针对集合搜索项目比向量更快（O（log（n））vs O（n））。要针对向量搜索项目，您需要迭代向量中的所有项目，但该集合使用红黑树来优化搜索，只会查找少数项目以找到匹配项。

The set is ordered, it means you can only iterate it from smallest one to biggest one by order, or the reversed order.

集合是有序的，这意味着你只能从最小的一个到最大的一个按顺序迭代它，或者相反的顺序。

But the vector is unordered, you can travel it by the insert order.

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

回答by Sriram Murali

The simple difference is that set can contain only unique values, and it is sorted. So you can use it for the cases where you need to continuously sort the values after every insert / delete.

简单的区别是 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;

The output is

输出是

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