unorderd_mapをまとめて削除

unorderd_mapにはerase_return_voidってのがあります。
もともと、quick_eraseという関数名だったのですが変更になったようです。

STLのeraseは削除した要素の次のイテレータを返すんですが、
unorderd_mapの場合、次のイテレータを求めるコストってのがあるらしく
何も返さないeraseであればその分速く出来るようです。

eraseの返り値を使うのは条件に合う要素をまとめて消す場合だと思います。
以下のような、ややわかりにくいコードで知られていると思います。

# include<vector>

int main(){
	std::vector<int> v;
	for (auto it = v.begin(); it != v.end();){
		if (*it % 4 == 0){
			it = v.erase(it);
		}else{
			it++;
		}
	}
}

こういうのをunorderd_mapでやる場合、どうすればいいか、ということで、
ベンチマークを取ってみました。

データを乱数で突っ込んでおいて、keyが4の倍数の要素だけ消すベンチマークです。

erase1は、vector等でも使われる、eraseで次のイテレータを受け取る形式です
erase2は、条件をまとめておいて、keyを指定してのeraseです。
erase3は、erase_return_voidを使ったやつです。

erase2,3は削除するキー分のバッファが必要ですし、毎回findの必要もあります。

# include <iostream>
# include <vector>
# include <string>
# include <boost/unordered_map.hpp>
# include <boost/timer/timer.hpp>

bool check(int n) { return n % 4 == 0;}

void erase1(boost::unordered_map<int, int *> &map)
{
	for (auto it = map.begin(); it != map.end();) {
		if (check(it->first)) {
			it = map.erase(it);
		}
		else {
			it++;
		}
	}
}

void erase2(boost::unordered_map<int, int *> &map)
{
	std::vector<int> keyvec;

	for (const auto &v : map) {
		if (check(v.first))keyvec.push_back(v.first);
	}

	for (int key : keyvec) {
		map.erase(key);
	}
}

void erase3(boost::unordered_map<int, int *> &map)
{
	std::vector<int> keyvec;

	for (const auto &v : map) {
		if (check(v.first))keyvec.push_back(v.first);
	}

	for (int key : keyvec) {
		auto it = map.find(key);
		map.erase_return_void(it);
	}
}


void speed_check(std::function<void()> func)
{
	boost::timer::auto_cpu_timer timer;

	func();

}

int main()
{
	boost::unordered_map<int, int *> map1, map2, map3;

	int value = 0;

	for (int i = 0; i < 100000; i++) {
		int key = rand();

		map1[key] = &value;
		map2[key] = &value;
		map3[key] = &value;
	}

	speed_check([&]() {erase1(map1); });
	speed_check([&]() {erase2(map2); });
	speed_check([&]() {erase3(map3); });


    return 0;
}

wandbox

そして実行結果は…ドン！

 0.012342s wall, 0.010000s user + 0.000000s system = 0.010000s CPU (81.0%)
 0.025197s wall, 0.030000s user + 0.000000s system = 0.030000s CPU (119.1%)
 0.023067s wall, 0.020000s user + 0.000000s system = 0.020000s CPU (86.7%)

無理にerase_return_voidを使うよりは、普通にループした方が倍以上速いですね。