「std::vector」観察記録
～慣れ親しんだ可変長配列の仕組みとふるまいを検証してみた

処理速度

　コンテナへの要素の挿入／削除／etc.に要する時間は、そりゃ短いに越したことはありません。が、vectorの各要素は連続、つまりスキマなくきっちり並んでいなくてはなりません。従ってvectorの指定位置に要素を挿入するには、後続する全要素を1つずつ順送りに移動して空席を設け、そこにハメ込むことになります。削除も同様に後続する要素を移動して空席を埋めなくては。なので挿入／削除位置より後にある要素が多いほど時間がかかっちゃいます。最悪ケースは先頭に挿入／先頭から削除、ですね。

　実測しましょう。高精度計時関数: QueryPerformanceCounter()を用い、関数fをn回呼ぶのに要する時間を測る関数: measure()を用意し、vector<int>の先頭／末尾に要素を1万回／2万回挿入して所要時間を計測します。

VectorExample07.cpp

#include <iostream>
#include <vector>
#include <list>

#include <cassert>
#include <Windows.h>

using namespace std;

template<typename Function, typename ...Args>
double measure(size_t times, Function f, Args... args) {
  LARGE_INTEGER freq;
  BOOL ret = QueryPerformanceFrequency(&freq);
  assert( ret );
  LARGE_INTEGER start;
  ret = QueryPerformanceCounter(&start);
  assert( ret );
  LARGE_INTEGER current;
  while ( times-- ) {
    f(args...);
  }
  ret = QueryPerformanceCounter(&current);
  assert( ret );
  return static_cast<double>(current.QuadPart - start.QuadPart)/freq.QuadPart;
}

int main() {
  {
  cout << "\n----- vector<int>::insert(front) 10000times : ";
  vector<int> c;
  cout << measure(10000, [](vector<int>& c) { c.insert(c.begin(), 0); }, ref(c)) << endl;
  }

  {
  cout << "\n----- vector<int>::insert(front) 20000times : ";
  vector<int> c;
  cout << measure(20000, [](vector<int>& c) { c.insert(c.begin(), 0); }, ref(c)) << endl;
  }

  {
  cout << "\n----- vector<int>::insert(back)  10000times : ";
  vector<int> c;
  cout << measure(10000, [](vector<int>& c) { c.insert(c.end(), 0); }, ref(c)) << endl;
  }

  {
  cout << "\n----- vector<int>::insert(back)  20000times : ";
  vector<int> c;
  cout << measure(20000, [](vector<int>& c) { c.insert(c.end(), 0); }, ref(c)) << endl;
  }

  cout << "-----" << endl;

  // list<int>に対しても同様（省略）

}

fig07

　ごらんのとおり、先頭への挿入にはかなり時間がかかっています。また、要素数を2倍にすると所要時間は2倍以上になっています。要素数に比例して時間を要する処理をN回繰り返すので、要素数N倍になると所要時間はN^2になります。ってことは要素数が100だったら1万のときの1/10000以下になるのだから、そこそこのサイズで使うならコピー（移動）がコスト高でない限り、そんなに気にすることはないとも言えます。

　対して末尾への挿入は高速です。あらかじめreserve()しておけるなら領域拡張の手間が省け、もっと速くなります。

　きょうびのCPUはかなり大きなキャッシュ・メモリを積んでいます。vectorは内包する要素が連続領域に無駄なく配置されているため、他のコンテナに比べより多くの要素をCPUキャッシュ上に置くことができます。そのため、実メモリへの書き込み（変更）を伴わない操作であればより高速に動作することが期待できます。そのことを併せて考慮すれば、「コンテナの選定に悩んだらひとまずvector使っとけ」はあながちマチガイではなさそうです。