std::set 和 std::vector 有什么区别? [英] What is the difference between std::set and std::vector?

问题描述

我现在正在学习 STL.我阅读了 set 容器.我有疑问什么时候要使用 set?看了set的描述后觉得没用，因为我们可以用vector代替代码>.你能说一下 vector 和 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

推荐答案

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

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.

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

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.

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

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.

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

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.

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

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.

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

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屋！