ちょっと遅いんちゃう？

はじめに

故あってベクターコンテナから要素を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
はい、よーいスタート(空耳)

# 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使いましょうね〜。