c++ - set 和 vector 哪个效率更高

Question

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

对于集合

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

对于 vector

 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

这太含糊了，忽略/遗漏了几个关键因素。如果你的 friend 正是这样说的，那么你的 friend (不管他或她的经历如何)就错了。更有可能的是，您在某种程度上误解了他们的话，并向他们解读了事情的简化版本。

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

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

你还没有真正详细地说明你的用例，所以我不会在这里假装给出具体细节，但对你提出的问题唯一可能的答案是“这取决于”和“这个问题从根本上来说有点毫无意义";你不能只采用两种数据结构和排序方法，然后问“哪个更有效？”没有用例。但是，您已经正确地测量了时间和空间要求，如果您已经针对您的实际用例做到了这一点，那么您就有答案了，不是吗？