std::vector::eraseが遅いような気がする

ちょっと遅いんちゃう？

#はじめに
故あってベクターコンテナから要素を`erase`したかったんだけど、
何故か妙に遅い気がしたので、ちょっと速度計測。
`std::vector`と、比較のために`std::list`に**114514**個のランダムな要素を突っ込んで、偶数のときだけ`erase`します。
(要素数に特に意味は)ないです。

乱数生成器はメルセンヌ・ツイスタで種は**1919810**にしました
(特に意味は)ないです。

レギュレーションは以下の4つ。
(1)`std::vector`に`erase`
(2)`std::list`に`erase`
(3)`std::vector`に`erase-remove`
(4)`std::vector`に`swap-pop_back`
はい、よーいスタート(空耳)

```cpp
#include <vector>
#include <list>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <chrono>
#include <random>

template <class RNG, class container> void SetNumber(container& x){
	RNG random(1919810);
	for(auto it = x.begin() ; it != x.end() ; ++ it){
		*it = random();
	}
}

template <class container> auto TimeAttackErase(const std::size_t Nelem){
	container x(Nelem);
	SetNumber<std::mt19937>(x);
	auto start = std::chrono::system_clock::now();
	for(auto it = x.begin() ; it != x.end() ; ++ it){
		if(*it % 2 == 0){
			x.erase(it);
			-- it;
		}
	}
	auto end = std::chrono::system_clock::now();
	return std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
}

template <class container> auto TimeAttackEraseRemove(const std::size_t Nelem){
	container x(Nelem);
	SetNumber<std::mt19937>(x);
	auto start = std::chrono::system_clock::now();
	x.erase(remove_if(x.begin(), x.end(), [](const int i){ return i % 2 == 0; }), x.end());
	auto end = std::chrono::system_clock::now();
	return std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
}

template <class container> auto TimeAttackSwap(const std::size_t Nelem){
	container x(Nelem);
	SetNumber<std::mt19937>(x);
	auto start = std::chrono::system_clock::now();
	for(int i = 0 ; i < x.size() ; ++ i){
		if(x[i] % 2 == 0){
			x[i --] = x[x.size() - 1];
			x.pop_back();
		}
	}
	auto end = std::chrono::system_clock::now();
	return std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
}

int main(void){
	std::cout << "Erase" << std::endl;
	std::cout << "      time = " << TimeAttackErase<std::vector<int> >(114514) << " micro sec" << std::endl;
	std::cout << "Erase Remove" << std::endl;
	std::cout << "      time = " << TimeAttackEraseRemove<std::vector<int> >(114514) << " micro sec" << std::endl;
	std::cout << "Erase (list)" << std::endl;
	std::cout << "      time = " << TimeAttackErase<std::list<int> >(114514) << " micro sec" << std::endl;
	std::cout << "Swap & pop_back()" << std::endl;
	std::cout << "      time = " << TimeAttackSwap<std::vector<int> >(114514) << " micro sec" << std::endl;
	return 0;
}
```

#結果
```
Erase
      time = 1693880 micro sec
Erase Remove
      time = 473 micro sec
Erase (list)
      time = 1686 micro sec
Swap & pop_back()
      time = 651 micro sec
```
ちょっと`erase`おそすぎなんちゃう？
一方`erase-remove`は(`erase`より)ずっと、はやい！！
それでも、`std::list`からの`erase`は`std::vector`からのそれよりもずっと高速。

#なんで？
(よく覚えてないからうろ覚え)
`std::vector`は、要素がメモリ上に連続して格納されている事を規定するため、
末尾以外への挿入・削除を行おうとすると、その地点から後ろの要素を全てずらす必要があるため、遅い。
一方、添字で要素にアクセスしようとかなると、早い。

`std::list`は、そうなっていないので、定数時間で終わる。だから早い。

`erase-remove`は`swap-pop_back`と大してやっている事は変わらないはずで、
一回不要な要素を後ろにまとめて隔離して切り落とすか、見つけ次第切り落とすかの違い。
僅かに`erase-remove`の方が早い。
(何でかな。ちゃんと考えれば理由が出てくるんだろうけど)

#結論
じゃけん`erase-remove`使いましょうね〜。