c++ - 为什么在排序算法的实现中 vector 明显慢于数组？

Question

MergeSort 的实现是使用 vector 从参数toBeSorted复制数据。通过更改它，以便分配常规数组并“手动”复制每个值，程序的执行速度会更快(详细信息在底部)。

我预计会有一些开销，但差异的规模让我感到惊讶。我认为构造一个 vector 几乎不会比使用 new 分配数组慢。

代码(我删除了实际合并以最小化示例):

#include <iostream>
#include <vector>
#include <time.h>

using namespace std;

#define USE_VECTORS

void Merge(vector<int>& toBeSorted, int left, int middle, int right) {
  int rightPartSize = (-1) * (middle - right);
  int leftPartSize = (middle - left) + 1;

#ifdef USE_VECTORS

  vector<int> leftPart{toBeSorted.begin() + left,
                            toBeSorted.begin() + left + leftPartSize};

  vector<int> rightPart{toBeSorted.begin() + middle + 1,
                            toBeSorted.end()};
#else

  int* leftPart = new int[leftPartSize];
  for (int i = 0; i < leftPartSize; i++) {
    leftPart[i] = (toBeSorted[left + i]);
  }

  int* rightPart = new int[rightPartSize];
  for (int i = 0; i < rightPartSize; i++) {
    rightPart[i] = (toBeSorted[middle + i + 1]);
  }

  delete[] leftPart;
  delete[] rightPart;
#endif
}

void MergeSort(vector<int>& toBeSorted, int left, int right) {
  if (left < right) {
    int middle = (left + right) / 2;
    MergeSort(toBeSorted, left, middle);
    MergeSort(toBeSorted, middle + 1, right);
    Merge(toBeSorted, left, middle, right);
  }
}

int main() {

  const int SIZE = 100000;
  std::vector<int> x(SIZE, 0);

  clock_t t_start = clock();
  MergeSort(x, 0, int(x.size()) - 1);
  clock_t t_end = clock();

  double elapsedTime = (t_end - t_start) / (double)CLOCKS_PER_SEC;
  cout << "Time: " << elapsedTime << endl;

  return 0;
}

在rextester上运行它，我得到的时间约为 1.2 秒。
取消注释 #define USE_VECTORS 以查看数组版本的时间。为此，我看到大约 0.009 秒。

Answer 1

计算 rightPartSize 的代码与创建 rightPart vector 的方式不一致。您可以通过添加以下语句轻松检查:

if( static_cast<size_t>( rightPartSize ) != rightPart.size() ) 
      cout << rightPartSize << " != " << rightPart.size() << endl;

创建rightPart后:

1 != 99999
1 != 99997
2 != 99998
1 != 99995
1 != 99994
3 != 99996
1 != 99992
1 != 99991
1 != 99989
1 != 99988
3 != 99990
6 != 99993
1 != 99986
1 != 99985
1 != 99983
...

因此 vector 完成的工作量明显大于使用动态数组所做的工作量。