set 和 vector 哪个效率更高

Question

我有一点问题，最近有人告诉我，对于输入的无序值，一堆随机值，假设有 100 万个，使用集合比使用一个向量，然后使用基本排序算法函数对所述向量进行排序，但是当我使用它们并通过时间函数检查它们时，在终端和 valgrind 中，它表明时间复杂度和 space 用法对于向量来说速度更快，即使添加了被调用的排序函数。给我建议使用该集合的人在 C++ 语言方面比我更有经验，但在接受人们的建议之前，我总是必须自己测试一下。测试代码如下。

为集合

std::set<int> testSet;
  for(int i(0); i<= 1000000; ++i)
    testSet.insert(-i);

对于矢量

 std::vector<int> testVector;
  for(int i(0); i<= 1000000; ++i)
    testVector.push_back(i * -1);

  std::sort(testVector.begin(), testVector.end());

我知道这些不是随机变量，这不公平，因为 set 不允许重复，而 vector 不允许重复，所以对于这个基本功能点，它们的大小不同。任何人都可以澄清为什么应该使用该集合，没有重复的点。

我也没有对无序集做任何测试。不太确定两个给定点之间的差异。

Answer 1

这太模糊了，ignores/misses 列出了几个关键因素。如果你的朋友正是这样说的，那么你的朋友（不管他或她的经历如何）就错了。更有可能的是，您在某种程度上误解了他们的话，并向他们解读了事情的简化版本。

当你想要一个排序的最终产品时，当你插入一个集合时排序是 "amortized"，因为你每次都会得到一点点排序操作。如果您将定期多次插入，那么分散工作量可能就是您想要的。总数加起来可能仍然比向量多（考虑偶尔的重新平衡等等；你的向量只需要偶尔移动到更大的内存块），但你已经把它分散了以免明显减慢程序的某些其他部分。

但是，如果您只是将所有元素转储到一个向量中并立即排序，不仅容器和算法要做的工作更少，而且您可能不介意它花费大量时间.

你还没有真正详细地说明你的用例，所以我不会在这里假装给出具体细节，但你提出的问题唯一可能的答案是 "it depends" 和 "the question is fundamentally somewhat meaningless";您不能只采用两种数据结构和排序方法，然后在没有用例的情况下询问 "which is more efficient?"。但是，您已经正确地 测量了 时间和 space 要求，如果您已经针对您的实际用例做到了这一点，那么，您就有了答案你不是吗？

set 和 vector 哪个效率更高

Which is more efficient, set or vector

c++

vector

set