c++ - 为什么在这种排序算法实现中 vector 比数组显着慢？

Question

MergeSort的实现是使用vector s从参数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 完成的工作量比动态数组要大得多。