読者です 読者をやめる 読者になる 読者になる

文字列型をキーとしたunordered_map

プログラミングをしている際、文字列型をキーとした連想配列を扱いたい時がある。

そのような時に用いられるのは多くの場合unordered_mapだ。

using Map = unordered_map<string, int>;

Map m = {
	{ "a", 1 },
	{ "b", 2 },
	{ "c", 3 },
};
m["a"]; // 1
m["b"]; // 2

ところで、unordered_map の []演算子 の引数は (const key_type&) あるいは (key_type&&) である。

そして、今 key_type は std::string だ。

そのため、

m["a"];

m.operator[](string{"a"});

と同義だ。

なんでもないアクセスのために std::string のインスタンスが生成されている。そして、std::string のコンストラクタでは "a" という文字列を格納するためのバッファが確保される。バッファの確保は大抵の場合比較的遅い。

なにか良い方法はないか。


さて、boost::string_ref と言うものが存在する。詳細な説明は省略するが、要は文字列を格納したバッファへの ポインタ と 文字数 のみを保持するだけのクラスである。

string_ref は内部でポインタを保持するだけで、一切のバッファ確保を行わない。

つまり、こいつをキーに出来れば上のような問題は起きないのだ。

そして勿論、 string_ref 等のような独自定義の型であっても、==演算子オーバーロード(あるいはコンパレータ)とハッシュ値を求めるハッシャさえ存在すれば、unordered_mapのキーとして使える。

#include <boost/utility/string_ref.hpp>
#include <boost/functional/hash.hpp> // boost::hash_range

using namespace boost;

struct Hasher {
	size_t operator()(string_ref str) const {
		return hash_range(str.cbegin(), str.cend());
	}
};

using Map = unordered_map<string_ref, int, Hasher>;

Map m = {
	{ "a", 1 },
	{ "b", 2 },
	{ "c", 3 },
};
// バッファの確保は起こらない
m["a"]; // 1
m["b"]; // 2

一見これで良さそうだ。

だが、これにもまだ問題がある。

先程も述べたように、string_ref はあくまでバッファへのポインタを保持するクラスである。つまり、文字列の本体はどこかに存在していなくてはならないのだ。

そのため、

int main() {
	Map m;

	{
		string str = "###";
		m[str] = 42;
	}// もはやstrは存在しない

	m["###"]; // ?
}

このようなコードは未定義動作となる。

何故ならば、m["###"]; が実行されるときにはもうバッファの本体たる str は破壊されているからだ。


今必要なのは、キーを登録する際には std::string のようにバッファを確保し、ただアクセスするときには boost::string_ref のようにバッファを確保せず、比較とハッシュ値の算出のみを行う型である。

では、愚直に実装してみる。

#include <boost/optional.hpp>

using namespace boost;

class Key {
	optional<string> str;
	string_ref       ref;

public:
	Key(string_ref s, bool flag = false) {
		if(flag) {
			str = s.to_string();
			ref = *str;
		}
		else {
			ref = s;
		}
	}

	Key(const Key& key)
		: str(key.str), ref(str ? *str : key.ref) {}

	Key(Key&& key)
		: str(std::move(key.str)), ref(str ? *str : key.ref) {}

	bool operator==(const Key& key) const {
		return ref == key.ref;
	}

	string_ref str() const {
		return ref;
	}
};

struct Hasher {
	size_t operator()(const Key& key) const {
		return hash_range(key.str().cbegin(), key.str().cend());
	}
};

boost::optional を用いてバッファの有効/無効を表現した。

また、コンストラクタの第二引数のフラグのon/offによってバッファを確保するかどうかを分岐させている。

実際にキーとして使用するときには以下のようになる。

using Map = unordered_map<Key, int, Hasher>;

Map m = {
	{ Key{"a", true}, 1 },
	{ Key{"b", true}, 2 },
	{ Key{"c", true}, 3 },
};

m[{"a"}]; // 1

string_ref str = "b";
m[str]; // 2   暗黙の型変換

……………………。

テキトーに時間計測を行ってみた結果、確かに、string をキーとした時よりも、速かった。とは言えそこまで大した差ではない。

ぶっちゃけこんなことするくらいならばもっと別の箇所を見直したほうがいいような気がした。