哪个更有效,设置或矢量

Question

我有一个问题,我最近被告知,对于输入的无序值,一堆随机值,比如说它们中的1百​​万,使用集合比使用向量更有效,然后使用基本排序算法函数对所述向量进行排序,但是当我使用它们并通过时间函数检查它们时,在终端和valgrind中,它表明向量的时间复杂度和空间使用都更快,即使是添加要调用的sort函数.给我建议使用该套件的人在C++语言中比我经验丰富,但在接受人们的建议之前我总是要自己测试一下.测试代码如下.

对于Set

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

这太模糊了,忽略/忽略了几个关键因素.如果你的朋友正是这样说的,那么你的朋友(无论他或她的经历)是错的.更有可能的是,你有点误解了他们的话,并在其中阅读了简化的问题.

如果需要已排序的最终产品,则在插入集合时,排序将"分摊",因为每次都会获得一些排序操作.如果您要定期插入多次,那么工作量的扩展可能就是您想要的.加起来的总数可能仍然比矢量更多(考虑偶尔的重新平衡等等;你的矢量只需要偶尔移动到更大的内存块),但是你已经把它传播出去了以免显着减慢程序中某些其他部分的速度.

但是如果你只是将所有元素都转储到一个向量中并直接排序,那么容器和算法的工作量就会减少,但你可能不介意花费大量的时间.

你没有详细说明你的用例,所以我不会假装在这里给出具体细节,但你提出的问题唯一可能的答案是"它取决于"和"这个问题从根本上说是毫无意义"; 你不能只采取两种数据结构和排序方法,并问"哪种更有效？" 没有用例.但是,你已经正确地测量了时间和空间要求,如果你对现实世界的用例做了这样的话,那么,你有答案吗？