Zenn
🌲

[C++]std::mapに[]でアクセスする場合の作用について

2021/04/20に公開
C++
#
map
tech
追記：（これコンパイラの最適化対象なのでは・・・？）と心配になったので計測してみた

下記のコードで、mapが空だった場合と、満たされている（？）場合について記事中のいくつかのアクセス方法で1000万回アクセスして時間を計測してみました。
概ね思惑通りの結果でした。（ホッ）

コンパイラはclangでオプションに-O3を指定しています。
（getGood(empty)は作用がないので消された感がありますね・・・。こういうのどうやって検証したら良いのでしょう？）

printf見出し 概要 経過時間(マイクロ秒) 備考
getGood(empty) 空のmapに対してfind 0
getGood(filled) 満たされたmapに対してfind 457369
getBad(empty) 空のmapに対してfind 2866
getBad(filled) 満たされたmapに対してfindと[] 1081415
insertGood(empty) 空のmapに対してinsert（毎回成功） 1952194 毎回要素数が増えていく
insertGood(filled) 満たされたmapに対してinsert（毎回失敗） 567700
insertBad(empty) 空のmapに対してfind, [], [] 3827796 毎回要素数が増えていく
insertBad(filled) 満たされたmapに対してfind, [] 1090565 
#include <stdio.h>
#include <map>
#include <chrono>

using namespace std;

int getGood(map<int,int> &m, int key, int default_value) {
	auto found = m.find(key);
	if(found == end(m)) {
		return default_value;
	}
	return found->second;
}
int getBad(map<int,int> &m, int key, int default_value) {
	if(m.find(key) == end(m)) {
		return default_value;
	}
	return m[key];
}
int insertGood(map<int,int> &m, int key, int default_value) {
	return m.insert(make_pair(key, default_value)).first->second;
}
int insertBad(map<int,int> &m, int key, int default_value) {
	if(m.find(key) == end(m)) {
		m[key] = default_value;
	}
	return m[key];
}



int main(int argc, char *argv[]) {
	int dst;
	map<int,int> m;
	const int times = 10000000;
	{
		m.clear();
		auto start = std::chrono::system_clock::now();
		for(int i = 0; i < times; ++i) {
			dst = getGood(m, i, i);
		}
		auto end = std::chrono::system_clock::now();
		printf("getGood(empty): %lld\n", std::chrono::duration_cast<std::chrono::microseconds>(end-start).count());
	}
	{
		m.clear();
		for(int i = 0; i < times; ++i) {
			m[i] = i;
		}
		auto start = std::chrono::system_clock::now();
		for(int i = 0; i < times; ++i) {
			dst = getGood(m, i, i);
		}
		auto end = std::chrono::system_clock::now();
		printf("getGood(filled): %lld\n", std::chrono::duration_cast<std::chrono::microseconds>(end-start).count());
	}
	{
		m.clear();
		auto start = std::chrono::system_clock::now();
		for(int i = 0; i < times; ++i) {
			dst = getBad(m, i, i);
		}
		auto end = std::chrono::system_clock::now();
		printf("getBad(empty): %lld\n", std::chrono::duration_cast<std::chrono::microseconds>(end-start).count());
	}
	{
		m.clear();
		for(int i = 0; i < times; ++i) {
			m[i] = i;
		}
		auto start = std::chrono::system_clock::now();
		for(int i = 0; i < times; ++i) {
			dst = getBad(m, i, i);
		}
		auto end = std::chrono::system_clock::now();
		printf("getBad(filled): %lld\n", std::chrono::duration_cast<std::chrono::microseconds>(end-start).count());
	}
	{
		m.clear();
		auto start = std::chrono::system_clock::now();
		for(int i = 0; i < times; ++i) {
			dst = insertGood(m, i, i);
		}
		auto end = std::chrono::system_clock::now();
		printf("insertGood(empty): %lld\n", std::chrono::duration_cast<std::chrono::microseconds>(end-start).count());
	}
	{
		m.clear();
		for(int i = 0; i < times; ++i) {
			m[i] = i;
		}
		auto start = std::chrono::system_clock::now();
		for(int i = 0; i < times; ++i) {
			dst = insertGood(m, i, i);
		}
		auto end = std::chrono::system_clock::now();
		printf("insertGood(filled): %lld\n", std::chrono::duration_cast<std::chrono::microseconds>(end-start).count());
	}
	{
		m.clear();
		auto start = std::chrono::system_clock::now();
		for(int i = 0; i < times; ++i) {
			dst = insertBad(m, i, i);
		}
		auto end = std::chrono::system_clock::now();
		printf("insertBad(empty): %lld\n", std::chrono::duration_cast<std::chrono::microseconds>(end-start).count());
	}
	{
		m.clear();
		for(int i = 0; i < times; ++i) {
			m[i] = i;
		}
		auto start = std::chrono::system_clock::now();
		for(int i = 0; i < times; ++i) {
			dst = insertBad(m, i, i);
		}
		auto end = std::chrono::system_clock::now();
		printf("insertBad(filled): %lld\n", std::chrono::duration_cast<std::chrono::microseconds>(end-start).count());
	}
	printf("dst: %d", dst);
}

std::mapのoperator[](key_type &&)またはoperator[](const key_type &)を使うときは作用を理解してから使おうなというお話。

特に以下の点が意識されていないコードをよく見かける気がするので書いてみてます。

  • operator[]にはreadだけでなくwriteの作用もある
  • operator[]を使うとmap::find相当の処理が走る
  • map::find相当の処理コストは（一般に）軽くないので、最低限にする

以下、std::mapは単にmapと書くことにします。
また、特に断りがない場合、スコープに以下が宣言されているものとします。

  • using namespace std;
  • std::map<int,int> m;

大前提

mapへの要素の追加（挿入）には大きく分けて以下の二つの方法があります。

  • insert / emplace 系関数
  • operator[]

これらはすでに指定のキーを持つ要素が存在する場合、動作が異なります。
前者は挿入に失敗します。
後者は値が上書きされます。

また、mapの要素は挿入時にキーでソートされます。
つまり、ただ要素を挿入するだけでも、どこに挿入するかを探索する処理（map::find相当）が走ることになります。
※mapの中身について事前に知っている場合は挿入位置を示すイテレータを指定できる系の挿入関数を使うとコストを緩和できます

要素を追加や編集するとき

存在しない場合は追加、存在する場合は無視

ここで以下のコードを見てみましょう。

if(m.find(0) == end(m)) {
	m[0] = 10;
}

このコードはワーストケースではm.find(0)とm[0]で二度検索してしまいます。
今回は「キーが存在しない場合のみ追加する」動作だったので、素直にそれそのものをやってくれるinsertを使いましょう。
これでOKです。

m.insert(make_pair(0, 10));

存在しない場合は無視、存在する場合は上書き

以下のコードを見てみましょう。
（わざと下手に書いている感じで恐縮ですが・・・）

if(m.find(0) != end(m)) {
	m[0] = 10;
}

これもワーストケースでは二度検索が走りますね。
map::findの戻り値を利用してこう書きましょう。

auto found = m.find(0);
if(found != end(m)) {
	found->second = 10;
}

存在しない場合は追加、存在する場合は上書き

もはや悪い例のコードを書く意味がなくなってきましたが、

if(m.find(0) == end(m)) {
	m.insert(make_pair(0,10));
}
else {
	m[0] = 10;
}

これはoperator[]の働きそのものなので、単にこれでOKです。

m[0] = 10;

もっと意図を明確にしたい場合はこう書くのも良いかもしれません。

auto result = m.insert(make_pair(0,10));
if(!result.second) {
	result.first->second = 10;
}

要素にアクセスするとき

キーが存在する場合はその値を、しない場合は指定の値を使用する関数（指定の値を追加しない）

こちらのコードを見てみましょう。
指定のキーが存在しない場合は良いのですが、存在する場合、やはり二度探索してしまいます。

int get(int key, int default_value) {
	if(m.find(key) == end(m)) {
		return default_value;
	}
	return m[key];
}

また、結果的に上のコードではmは変化しないのですが
int get(const map<int,int> &m, int key, int default_value)
とmをconstで受けた場合や、
mとgetがSomeClassクラスのメンバだったとして
int SomeClass::get(int key, int default_value) const
と宣言していた場合、これはコンパイルエラーになります。

m[key]がmを変化させてしまう作用を持っているからです。
正確にいうと、operator[]がconstメンバではないからです。

コストの問題だけではなく、constにできるものはconstにしたいので、ここではoperator[]を使うのをやめましょう。
挿入するつもりがないのに挿入する作用がある記述をするのはバグの元ですし、コードの意図が伝わりにくくもなります。

int get(int key, int default_value) {
	auto found = m.find(key);
	if(found == end(m)) {
		return default_value;
	}
	return found->second;
}

キーが存在する場合はその値を、しない場合は指定の値を使用する関数（指定の値を追加する）

例えばつい書いてしまうコードとしてはこんな感じでしょうか。

int get(int key, int default_value) {
	if(m.find(key) == end(m)) {
		m[key] = default_value;
	}
	return m[key];
}

これはワーストケースでは三回の探索が走ります。
これまでの例に共通することですが、要素の探索を含むアクセスは一度で済むはずです。

int get(int key, int default_value) {
	auto result = m.insert(make_pair(key, default_value));
	if(result.second) {
		return result.first->second;
	}
	else {
		return default_value;
	}
}

ちなみにわざと冗長に書いてしまいましたが、これでOKです。

int get(int key, int default_value) {
	return m.insert(make_pair(key, default_value)).first->second;
}

（余談）存在する場合はその値を、しない場合はデフォルト値を返す

これでOKです。
※map::mapped_type（値の型）がデフォルトコンストラクタを持つ場合に限る

int get(int key) {
	return m[key];
}

まとめ（再掲）

  • operator[]にはreadだけでなくwriteの作用もある
  • operator[]を使うとmap::find相当の処理が走る
  • map::find相当の処理コストは（一般に）軽くないので、最低限にする

Discussion