std::vector, std::deque, std::listの各操作に掛かる時間について計測してみた。

# はじめに
こんにちは。
[42tokyo](https://42tokyo.jp/)といったところで、コンピュータサイエンス？を学んでいます。
最近、[Merge-insertion sort(Ford–Johnson algorithm)](https://en.wikipedia.org/wiki/Merge-insertion_sort)の実装を行う課題を通して、C++98のコンテナについて調べました。
今回は、std::vector, std::deque, std::listの各操作に掛かる時間を計測した結果をまとめます。

間違い等があれば、ご指摘ください。

# 参考

https://en.wikipedia.org/wiki/Merge-insertion_sort

https://en.cppreference.com/w/cpp/container

https://en.cppreference.com/w/cpp/container/vector

https://en.cppreference.com/w/cpp/container/deque

https://en.cppreference.com/w/cpp/container/list

# 実行環境

```: 環境
MacBook Pro
プロセッサ　2.3 GHz 8 コア Intel Core i9
```

```: c++ -v
Apple clang version 15.0.0 (clang-1500.3.9.4)
Target: x86_64-apple-darwin23.5.0
Thread model: posix
```

# まとめ
各操作の実行結果は画像の通り
![スクリーンショット 2024-06-19 15.10.40.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/282897/3d02854b-3ce2-31b0-8782-48dcd25f0962.png)

# 各コンテナの概要
### std::vector
* 連続したメモリ領域を確保し要素を格納する
* 必要に応じて動的にメモリを確保する
* 末尾に対する操作が高速で行われる
<table>
  <caption>各操作に掛かる計算量</caption>
  <thead>
    <tr>
      <th>操作</th> <th>計算量（$O(x)$）</th>
    </tr>
  </thead>
  <tr>
    <td> ランダムアクセス </td> <td>少ない（常に$O(1)$）</td>
  </tr>
  <tr>
    <td> 終端に要素の追加、または削除 </td> <td>少ない（常に$O(1)$）</td>
  </tr>
  <tr>
    <td> 終端以外に要素の追加、または削除 </td> <td>終端までの距離（$n$）に比例（$O(n)$）</td>
  </tr>
</table>

### std::deque
* 固定サイズの配列を確保し要素を格納する
* 必要に応じて動的にメモリを確保するが、各配列は連続したメモリ領域に配置されない
* 先頭と末尾に対する操作が高速で行われる
<table>
  <caption>各操作に掛かる計算量</caption>
  <thead>
    <tr>
      <th>操作</th> <th>計算量（$O(x)$）</th>
    </tr>
  </thead>
  <tr>
    <td> ランダムアクセス </td> <td>少ない（常に$O(1)$）</td>
  </tr>
  <tr>
    <td> 終端に要素の追加、または削除 </td> <td>少ない（常に$O(1)$）</td>
  </tr>
  <tr>
    <td> 終端以外に要素の追加、または削除 </td> <td>全体の要素数（$n$）に比例（$O(n)$）</td>
  </tr>
</table>

### std::list
* 双方向リスト
<table>
  <caption>各操作に関して</caption>
  <thead>
    <tr>
      <th>操作</th> <th>計算量（$O(x)$）</th>
    </tr>
  </thead>
  <tr>
    <td> ランダムアクセス </td> <td>高速なアクセスとは言えない</td>
  </tr>
  <tr>
    <td> 要素の追加、または削除 </td> <td>常に一定時間を要する</td>
  </tr>
</table>

# 各テストのコード
### 事前準備
```
~ ~ ~
std::srand(std::time(NULL));
std::clock_t	start, finish;
double			time;

int nums[1000000];
for (int i = 0; i < 1000000; i++) { nums[i] = std::rand() % 1000000; }

std::vector<int>	vec;
std::deque<int>		deq;
std::list<int>		lst;
~ ~ ~
```
### 終端に要素を追加するテスト
:::note info
計測した処理の実装のみ記述
:::

```
start = std::clock();
for (int i = 0; i < 1000000; i++) { vec.push_back(nums[i]); }
finish = std::clock();
time = static_cast<double>(finish - start) / CLOCKS_PER_SEC * 1000.0;

start = std::clock();
for (int i = 0; i < 1000000; i++) { deq.push_back(nums[i]); }
finish = std::clock();
time = static_cast<double>(finish - start) / CLOCKS_PER_SEC * 1000.0;

start = std::clock();
for (int i = 0; i < 1000000; i++) { lst.push_back(nums[i]); }
finish = std::clock();
time = static_cast<double>(finish - start) / CLOCKS_PER_SEC * 1000.0;
```

### ランダムな位置の要素にアクセスするテスト
:::note info
このテストでは、[終端に要素を追加するテスト](#終端に要素を追加するテスト)で作成したコンテナを使用
:::

```
start = std::clock();
for (int i = 0; i < 1000000; i++) { vec[nums[i]] = nums[i]; }
finish = std::clock();
time = static_cast<double>(finish - start) / CLOCKS_PER_SEC * 1000.0;

start = std::clock();
for (int i = 0; i < 1000000; i++) { deq[nums[i]] = nums[i]; }
finish = std::clock();
time = static_cast<double>(finish - start) / CLOCKS_PER_SEC * 1000.0;

std::list<int>::iterator	beginIt = lst.begin();
std::list<int>::iterator	endIt = lst.end();
int							lstSize = lst.size();
int							middleIndex = lstSize / 2;
start = std::clock();
for (int i = 0; i < 1000; i++) {
    if (nums[i] < middleIndex) {
    	std::advance(beginIt, nums[i]);
    	*beginIt = nums[i];
    	beginIt = lst.begin();
    } else {
    	std::advance(endIt, nums[i] - lstSize);
    	*endIt = nums[i];
    	endIt = lst.end();
    }
}
finish = std::clock();
time = static_cast<double>(finish - start) / CLOCKS_PER_SEC * 1000.0;
```

### ランダムな位置で要素を追加するテスト
:::note info
このテストでは、[終端に要素を追加するテスト](#終端に要素を追加するテスト)で作成したコンテナを使用
:::
```
std::vector<int>::iterator	vecBeginIt, vecEndIt;
int							vecSize = vec.size();
int							vecMiddleIndex = vecSize / 2;
start = std::clock();
for (int i = 0; i < 1000; i++) {
	if (nums[i] < vecMiddleIndex) {
		vecBeginIt = vec.begin();
		std::advance(vecBeginIt, nums[i]);
		vec.insert(vecBeginIt, nums[i]);
	} else {
		vecEndIt = vec.end();
		std::advance(vecEndIt, nums[i] - vecSize);
		vec.insert(vecEndIt, nums[i]);
	}
	vecSize = vec.size();
	vecMiddleIndex = vecSize / 2;
}
finish = std::clock();
time = static_cast<double>(finish - start) / CLOCKS_PER_SEC * 1000.0;

std::deque<int>::iterator	deqBeginIt, deqEndIt;
int							deqSize = deq.size();
int							deqMiddleIndex = deqSize / 2;
start = std::clock();
for (int i = 0; i < 1000; i++) {
	if (nums[i] < deqMiddleIndex) {
		deqBeginIt = deq.begin();
		std::advance(deqBeginIt, nums[i]);
		deq.insert(deqBeginIt, nums[i]);
	} else {
		deqEndIt = deq.end();
		std::advance(deqEndIt, nums[i] - deqSize);
		deq.insert(deqEndIt, nums[i]);
	}
	deqSize = deq.size();
	deqMiddleIndex = deqSize / 2;
}
finish = std::clock();
time = static_cast<double>(finish - start) / CLOCKS_PER_SEC * 1000.0;

std::list<int>::iterator	lstBeginIt, lstEndIt;
int							lstSize = lst.size();
int							lstMiddleIndex = lstSize / 2;
start = std::clock();
for (int i = 0; i < 1000; i++) {
	if (nums[i] < lstMiddleIndex) {
		lstBeginIt = lst.begin();
		std::advance(lstBeginIt, nums[i]);
		lst.insert(lstBeginIt, nums[i]);
	} else {
		lstEndIt = lst.end();
		std::advance(lstEndIt, nums[i] - lstSize);
		lst.insert(lstEndIt, nums[i]);
	}
	lstSize = lst.size();
	lstMiddleIndex = lstSize / 2;
}
finish = std::clock();
time = static_cast<double>(finish - start) / CLOCKS_PER_SEC * 1000.0;
```

### 先頭に要素を追加するテスト
```
	std::vector<int>	vec;
	std::deque<int>		deq;
	std::list<int>		lst;

	start = std::clock();
	for (int i = 0; i < 100000; i++) { vec.insert(vec.begin(), nums[i]); }
	finish = std::clock();
	time = static_cast<double>(finish - start) / CLOCKS_PER_SEC * 1000.0;

	start = std::clock();
	for (int i = 0; i < 100000; i++) { deq.push_front(nums[i]); }
	finish = std::clock();
	time = static_cast<double>(finish - start) / CLOCKS_PER_SEC * 1000.0;

	start = std::clock();
	for (int i = 0; i < 100000; i++) { lst.push_front(nums[i]); }
	finish = std::clock();
	time = static_cast<double>(finish - start) / CLOCKS_PER_SEC * 1000.0;
```

# さいごに
初めて、比較することを意識してコードを書いてみました。
正直なところ「これで正しく比較ができているのか？」といった気持ちです。
不備があればお申し付けください。
ありがとうございました。