vectorとlistの追加処理の時間差を比べてみた

#はじめに
以前、vectorとlistの追加処理に関して記事を書いた際に、ありがたい事に自分の中の「実行時間に関する感覚」がズレているかもしれないという事が発覚したので、しっかりプログラムを書いて確認しようと思いやってみたという感じです。

#目次

1. 前置き
2. シンプルに後ろに追加してみる
3. 真ん中あたりに追加してみる
4. 先頭に追加してみる
5. まとめ

#前置き
###どんなプログラムを書いたのか
配列に数万回値を追加し続けるという最高にロックな実験プログラムです。

###インクルードについて

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

この記事に乗せているプログラムには、この４つをインクルードしてあります。
###使う関数について
今回は比較のため一括で**「insert」関数を使用**します。
push_backやpush_frontなど便利な関数があるとの事ですが、
今回は知らないふりをします。

#シンプルに後ろに追加してみる
まずはとりあえず後ろにどんどん追加していく処理を書いてみた。

const int LOOP_NUM = 100000;//追加する回数
std::vector<int>vec;
std::list<int>lis;

//vectorについて
clock_t startV = clock();
for (int i = 0; i < LOOP_NUM; i++) {
	vec.insert(vec.end(),1);//今ある配列データの最後に「１」という値を追加する。
}
clock_t endV = clock();

double timeV = (static_cast<double>(endV) - static_cast<double>(startV)) / CLOCKS_PER_SEC * 1000.0;
std::cout << "vectorの追加速度:" << timeV << "ms\n";

//listについて
clock_t startL = clock();
for (int i = 0; i < LOOP_NUM; i++) {
	lis.insert(lis.end(),1);//今ある配列データの最後に「１」という値を追加する。
}
clock_t endL = clock();

double timeL = (static_cast<double>(endL) - static_cast<double>(startL)) / CLOCKS_PER_SEC * 1000.0;
std::cout << "listの追加速度:" << timeL << "ms\n";

これを実行してみると、このような結果になった。

vectorの追加速度:111ms
listの追加速度:167ms

…vectorのが速いではないか！

#真ん中あたりに追加してみる
今度は配列の真ん中に追加していく処理を書いた。
（プログラムは上の続きになります。なのですでにLOOP_NUM分のデータが配列に入った状態です。）

//vectorについて
startV = clock();
for (int i = 0; i < LOOP_NUM; i++) {
	vec.insert(vec.begin() + vec.size() / 2, 1);//配列の先頭から「配列のサイズ÷２」分進んだ場所に追加。
}
endV = clock();

timeV = (static_cast<double>(endV) - static_cast<double>(startV)) / CLOCKS_PER_SEC * 1000.0;
std::cout << "vectorの追加速度:" << timeV << "ms\n";

//listについて
std::list<int>::iterator ite = lis.begin();
for (int cnt = 0; cnt < lis.size() / 2; cnt++) {
	ite++;//イテレーターを配列データの真ん中まで移動させる。
}

startL = clock();
for (int i = 0; i < LOOP_NUM; i++) {
	lis.insert(ite,1);//真ん中あたりに追加。
}
endL = clock();

timeL = (static_cast<double>(endL) - static_cast<double>(startL)) / CLOCKS_PER_SEC * 1000.0;
std::cout << "listの追加速度:" << timeL << "ms\n";

こちらの結果は…

vectorの追加速度:940ms
listの追加速度:142ms

listのが速い！

#先頭に追加してみる
最後に先頭に追加してみる。
（プログラムは、先ほどと同じくLOOP_NUM分だけ入った状態の続きです。）

//vectorについて
startV = clock();
for (int i = 0; i < LOOP_NUM; i++) {
	vec.insert(vec.begin(), 1);//先頭に１を追加。
}
endV = clock();

timeV = (static_cast<double>(endV) - static_cast<double>(startV)) / CLOCKS_PER_SEC * 1000.0;
std::cout << "vectorの追加速度:" << timeV << "ms\n";

//listについて
startL = clock();
for (int i = 0; i < LOOP_NUM; i++) {
	lis.insert(lis.begin(), 1);//先頭に１を追加。
}
endL = clock();

timeL = (static_cast<double>(endL) - static_cast<double>(startL)) / CLOCKS_PER_SEC * 1000.0;
std::cout << "listの追加速度:" << timeL << "ms\n";

実行結果は…

vectorの追加速度:1867ms
listの追加速度:161ms

これまたlistのが速い！

#まとめ
雑にまとめるとこんな感じ。

種類	先頭に追加	中央に追加	最後に追加
vector	負け	負け	勝ち
list	勝ち	勝ち	負け

いつでもlistのが速いという訳ではないという事が分かった。
そしてlistは、前中後のどこに追加処理を書いても実行時間がほぼ変わらないのは面白いなと思った。
…だがなぜ真ん中への追加処理が一番早いのだろうか。begin、endの関数がちょっと重たいのかな？