std :: set和std :: vector有什么区别？(What is the difference between std::set and std::vector?)

std :: set和std :: vector有什么区别？(What is the difference between std::set and std::vector?)

我现在在学STL 我读了关于set容器。 有什么时候想使用set吗？ 在阅读了设置的描述之后，它看起来像是没用的，因为我们可以用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 ），它都会被订购。

一个vector 只有你明确给出的顺序。 vector中的项目是你放在哪里的。 如果你把它们搞乱了，那么他们就是乱序了; 您现在需要sort容器进行sort以将其重新排列。

诚然， set用途相对有限。 通过适当的纪律，可以将项目插入vector并保持命令。 但是，如果您不断地从容器中插入和移除项目，则vector将遇到许多问题。 它会做很多复制/移动元素等等，因为它只是一个数组。

将项目插入vector所需的时间与vector已经存在的项目数成正比。 将项目插入到set所需的时间与项目数量的log 2成正比。 如果物品数量很大，这是一个巨大的差异。 log 2（100,000）为〜16; 这是一个重大的进步。 删除也是一样。

但是，如果您一次性执行所有插入操作，那么在初始化时就没有任何问题。 您可以将所有内容插入vector ，排序（支付该价格一次），然后使用标准算法进行排序vectors查找元素并对排序列表进行迭代。 而对于一个set的元素的迭代不是很慢，迭代一个vector就更快。

所以有一些排序的vector敲击一个set 。 话虽如此，你真的不应该费心的这种优化，除非你知道这是有必要的。 所以使用一个set除非你有你所写的那种系统的经验（因此知道你需要这个性能），或者有一个分析数据在手，告诉你，你需要一个vector而不是一个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.

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.