向量与Deque插入时间

Question

我阅读了这个不错的实验，尤其是在vector和deque容器上呼叫insert()的性能。该特定实验的结果（实验4）是deque在此操作中非常出色。

我使用我编写的简短排序功能实现了自己的测试，我应该注意使用[]运算符以及其他成员功能，并发现了截然不同的结果。例如，为了插入100,000个元素，vector花费了24.88秒，而deque则花费了374.35秒。

我该如何解释？我想这与我的分类功能有关，但是想要细节！

我使用的是没有优化的G 4.6。

这是程序：

#include <iostream>
#include <vector>
#include <deque>
#include <cstdlib>
#include <ctime>
using namespace std;
size_t InsertionIndex(vector<double>& vec, double toInsert) {
  for (size_t i = 0; i < vec.size(); ++i)
    if (toInsert < vec[i])
      return i;
  return vec.size();  // return last index+1 if toInsert is largest yet                                                                          
}
size_t InsertionIndex(deque<double>& deq, double toInsert) {
  for (size_t i = 0; i < deq.size(); ++i)
    if (toInsert < deq[i])
      return i;
  return deq.size();  // return last index+1 if toInsert is largest yet                                                                          
}
int main() {
  vector<double> vec;
  deque<double> deq;
  size_t N = 100000;
  clock_t tic = clock();
  for(int i = 0; i < N; ++i) {
    double val = rand();
        vec.insert(vec.begin() + InsertionIndex(vec, val), val);
    //        deq.insert(deq.begin() + InsertionIndex(deq, val), val);                                                                           
  }
  float total = (float)(clock() - tic) / CLOCKS_PER_SEC;
  cout << total << endl;
}

Answer 1

deque比vector要快得多的特殊情况是在容器的 front 上插入时。在您的情况下，您将在随机位置插入，这实际上将为vector提供优势。

另外，除非您使用了优化的构建，否则很有可能在库实现中有界限检查。这些检查可以大大增加时间。要进行适当的基准比较，您必须在打开所有正常优化并打开调试时运行。

Answer 2

您的代码正在执行插入排序，即O（n^2）。在deque上迭代比在vector上迭代的速度慢。

我怀疑您没有看到与发布链接相同的结果，因为您程序的运行时间由InsertionIndex中的循环主导，而不是呼叫deque::insert（或vector::insert。