連想配列 std::unordered_map のキーの一致条件を自分で決める - C++ プログラミング
PROGRAM
std::unordered_map<> のキーの一致条件を自分で決める
C++11 では、キーと値をセットで管理する連想配列を簡単に利用できる std::unordered_map<> というテンプレートクラスが用意されていて、これを使用することで、ひとつのキーに対するひとつの値を簡単に管理できるようになります。
これの使い方は 連想配列 std::unordered_map を使用する で記してあります。
この std::unordered_map<> のキーはハッシュを使って管理されていて、並び順は保証されていません。そして、格納されている値はキーを頼りに検索されます。
このとき、通常であれば、キーは std::hash<> 構造体と std::equal_to<> 構造体を使って比較が行われるので、つまり std::unordered_map<> のキーを std::string 型にしている場合は、大文字小文字を含めた完全一致で、キーの一致判定が行われます。
この一致判定は自分で独自のものに差し替えることができます。
たとえばキーの大文字と小文字は区別せずに同じ値として扱いたいというようなとき、わざわざ全てを小文字に変換してから std::unordered_map<> に格納しなくても、キーの一致判定を予め指定しておくことで、文字列をそのままキーとして指定できます。
std::unordered_map<> でキーを大文字・小文字を無視して扱うようにする
実際に std::unordered_map<> で扱うキーの大文字と小文字を区別しないようにしてみます。
std::unordered_map<> でキーの一致判定をするとき、キーのハッシュ値と同値判定を組み合わせて判定しています。ハッシュ値で大まかなアタリをつけて、その中から同値判定でキーを探し出す感じになるのでしょうか。
ここで使う、ハッシュ値を取得する関数と同値判定で使う関数は、std::unordered_map<> 型の変数を定義するときに、テンプレート引数として指定することができます。
ちなみにこれらは、既定ではそれぞれ std::hash<> 構造体と std::unordered_map<> 構造体になっています。
キーの判定関数を自作する
大文字と小文字の違いを無視してキーを扱うために、キーの一致判定で使うハッシュ値を取得する関数と同値判定関数を自作します。
今回は、キーは std::string 型で扱おうと思うので、ここではそれに特化したものを作成します。
ハッシュ値を取得する関数を作成する
今回のハッシュ値を計算する関数では、キーとして指定された文字列を全て小文字に変換して、変換後の文字列で取得したハッシュ値を返すようにしてみます。
この関数は構造体またはクラスで用意して、キーを 1 つ受け取ってハッシュ値を返す () 演算子を実装しておく必要があります。
class CIgnoreCaseStringHash
{
public:
// 渡された source からハッシュ値を取得して返します。
size_t operator()(const std::string& source) const
{
// 渡された source に含まれる大文字を小文字に変換します。
std::string buffer;
buffer.resize(source.size());
std::transform(source.cbegin(), source.cend(), buffer.begin(), tolower);
// 小文字に変換した文字列のハッシュを取得します。
return std::hash<std::string>()(buffer);
}
};
これで、キーの大文字・小文字の違いに影響を受けないハッシュ値を計算する関数を用意できました。
このようなクラスや構造体の用意の仕方については STL でよく使う関数（述語）を構造体で作る に記しておきます。
また、大文字を小文字に変換するコードについては std::string の小文字を大文字に変換する を、変換後の文字列を使ってハッシュ値を計算するコードについては std::string のハッシュ値を取得する を参考にしてください。
同値判定を行う関数を作成する
同値判定を行う関数では、比較する二つのキーが () 演算子に渡されるので、今回はそれらを大文字小文字を区別せずに比較した結果を返すようにしてみます。
この関数も構造体またはクラスで用意する必要があるようでした。
class CIgnoreCaseStringEqualTo : public std::binary_function<std::string, std::string, bool>
{
public:
// 扱う型を定義します。（今回は必須ではありません）
typedef std::string first_argument_type;
typedef std::string second_argument_type;
typedef bool result_type;
// 渡された二つのキーの一致状況を判定します。
bool operator()(const std::string& lhs, const std::string& rhs) const
{
// 大文字は小文字とみなして、両方が一致するかを判定します。
return std::equal(lhs.cbegin(), lhs.cend(), rhs.cbegin(), [](char lhs, char rhs) { return tolower(lhs) == tolower(rhs); });
}
};
これで、大文字・小文字の違いに影響を受けない一致判定関数を用意できました。
このようなクラスや構造体の用意の仕方については STL でよく使う関数（述語）を構造体で作る に記しておきます。
また、大文字を小文字とみなして比較するコードについては std::string を大文字小文字を区別しないで比較する を参考にしてください。
独自のキー判定を行う std::unordered_map を定義する
ハッシュを生成する関数と同値判定の関数ができたら、それを使う std::unordered_map の定義は簡単です。
// 独自のキーの扱いを定義した std::unordered_map<> インスタンスを作成します。
std::unordered_map<std::string, int, CIgnoreCaseStringHash, CIgnoreCaseStringEqualTo> map;
このように std::unordered_map<> のテンプレート引数で、普段通りのキーの型と値の型の指定に続けて、ハッシュを生成するのに使う構造体と、一致判定を行うのに使う構造体を指定します。
これだけで、独自のキーの扱い方をする std::unordered_map<> を用意することができました。
今回の例では、キーを大文字と小文字を無視して扱うようにしてあるので、キーとして "Key" を指定しても "KEY" を指定しても、同じキーが指定されたものとして振る舞ってくれるようになりました。
[ もどる ]