std :: set和std :: vector之间有什么区别? [英] What is the difference between std::set and std::vector?
问题描述
我现在正在学习STL。我阅读了关于 set
容器。我有问题,当你想使用 set
?在阅读描述集后,它看起来是无用的,因为我们可以用向量
。你能说出向量
vs 设置
容器的优点和cos。感谢
订购设置
。根据您提供的函子,它会保证保持在特定的顺序中。无论您添加或删除什么元素(除非您添加重复,这不允许在设置
),它将始终是有序的。
A 向量
只有您明确给出的顺序。 向量
中的项目是您放置它们的位置。如果你把它们乱序,那么它们就出错了;您现在需要排序
容器以将它们按顺序放回。
诚然, set
使用相对有限。通过适当的纪律,可以将项目插入向量
并保持顺序。但是,如果您经常从容器中插入和删除项目,则向量
将遇到许多问题。它会做很多复制/移动的元素等等,因为它实际上只是一个数组。
将一个项目插入一个向量
与已经在向量
中的项目数成正比。将项目插入集
所需的时间与项目数量的 log 2 成正比。如果项目数量很大,这是一个巨大的区别。 log 10(100,000)为〜16;这是一个重大的速度改进。这同样适用于删除。
但是,如果您立即执行所有插入操作,则在初始化时,这没有问题。您可以将所有内容插入向量
,对其排序(支付一次价格),然后对排序的向量使用标准算法
来查找元素并遍历排序的列表。虽然对 set
的元素的迭代不是很慢,但是在向量
上的迭代更快。 p>
所以有些情况下,一个排序的向量击败一个
set
。话虽如此,你真的不应该费心这种优化,除非你知道这是必要的。所以使用 set
,除非你有你所写的系统的经验(因此知道你需要的性能)或有分析数据在手,告诉你,您需要一个向量
,而不是设置
。
I am learning STL now. I read about set
container. I have question when you want to use set
? After reading description of set it looks like it is useless because we can substitute it by vector
. Could you say pros and cos for vector
vs set
containers. Thanks
A set
is ordered. It is guaranteed to 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.
A vector
has exactly and only the ordering you explicitly give it. Items in a vector
are where you put them. If you put them in out of order, then they're out of order; you now need to sort
the container to put them back in order.
Admittedly, set
has relatively limited use. With proper discipline, one could insert items into a vector
and keep it ordered. However, if you are constantly inserting and removing items from the container, vector
will 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.
The time it takes to insert an item into a vector
is proportional to the number of items already in the vector
. The time it takes to insert an item into a set
is 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.
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 vectors
to find elements and iterate over the sorted list. And while iteration over the elements of a set
isn't exactly slow, iterating over a vector
is faster.
So there are cases where a sorted vector
beats 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 set
unless 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 vector
and not a set
.
这篇关于std :: set和std :: vector之间有什么区别?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!