連想配列 std::unordered_map を使用する - C++ プログラミング

C++11 では、キーと値をセットで管理する連想配列を簡単に利用できる std::unordered_map<> というテンプレートクラスが用意されています。

これを使用することで、キーに対する値を追加したり削除したり、挿入したりといったことが簡単にできます。テンプレートクラスなので、任意のデータ型を扱えるのも便利です。

ここでは、その std::unordered_map<> の基本的な使い方について見て行きます。

 

ちなみに、std::unordered_map<> は、キーを登録した順番とは関係なく（ハッシュを使って）格納するタイプのものになります。

キーを順番通りに（キーと値を辞書的順序で）格納したい場合は <map> ヘッダーに定義されている std::map<> を使用します。std::map<> と std::unordered_map<> の使い方は基本的に同じです。

 

また、キーの扱い方を自分で定義することも出来るようになっています。

そちらについては 連想配列 std::unordered_map のキーの一致条件を自分で決める で紹介します。

 

使用準備

C++11 で std::unordered_map<> を使用するには、次のようにヘッダーファイルをインクルードする必要があります。

このようにすることで、std::unordered_map<> テンプレートクラスが利用できるようになります。

 

初期化

std::unordered_map<> インスタンスは、最初に「キー」で使うデータ型を、続いて「値」で使うデータ型を指定して生成します。

左側で指定している "std::unordered_map<std::string, int>" がデータ型になります。

これで、キーの型が "std::string" で、値が "int" の連想配列 "hash" を定義することができました。

 

利用できるメソッド

std::unordered_map<> には、連想配列を操作するためのメソッドがいくつか用意されています。

その中の、よく使いそうなメソッドをいくつか紹介します。

 

基本操作

VALUE_TYPE& at(KEY_TYPE key) const VALUE_TYPE& at(KEY_TYPE key) const	指定したキーの値を取得します。[] 演算子と違って、指定されたキーが存在しない場合は "std::out_of_range" 例外が発生します。読み取り専用のインスタンスでも使用できます。
VALUE_TYPE& operator[KEY_TYPE key]	指定したキーの値を取得します。at メソッドと違って、指定したキーが存在しない場合は、そのキーが初期値で作成されます。値の追加で使用できます。読み取り専用のインスタンスでは使用できません。
void clear()	格納されているキーと値のセットを全て削除します。
size_t erase(const KEY_TYPE& key)	指定したキーを削除します。イテレータを使って削除する範囲を指定することもできます。削除したキーの数を返します。

 

値の設定は [] 演算子を使って行います。

[] の中にキーの値を指定すると、そのキーと値を格納できる領域が確保されます。

値を設定するとき、指定したキーが既に存在している場合には、そのキーの値が新しい値に上書きされます。

 

また、at 関数を使って、値の取得や設定ができるようにもなっています。

[] 演算子との違いは、こちらの at 関数の場合は、存在しないキーを指定した場合は "std::out_of_range" 例外が発生するところです。

存在しないキーで値を取得しようとしたときに既存のキーが勝手に増えることがないので、設定済みの std::unordered_map<> の値を安全に参照することができます。

内部のキーの値を登録することがないので、読み取り専用のインスタンスでも使用できます。

 

要素の設定

std::pair<iterator,bool> insert(const std::pair<KEY_TYPE, VALUE_TYPE>)	インスタンスにキーと値のセットを追加します。戻り値で、iterator で挿入された位置が、bool で挿入されたかどうかが返されます。

std::pair<KEY_TYPE, VALUE_TYPE> 型で指定したキーと値のセットを挿入します。

このとき、指定したキーと値のセットと同じキーが既に存在している場合には、そのセットは登録されずに戻り値の second の値が false になります。

 

そのため、既存の値がなければ新規に追加して、あれば値を書き換えたいような場合には、演算子 [] を使った方が簡潔にプログラミングできます。

insert 関数を使うメリットとしては、クラスを扱うような場合に std::pair のコンストラクタでクラスを指定することで、コピーコンストラクタによって値を初期化できるところでしょうか。

[] 演算子の場合は、存在しないキーを指定すると、まず最初にディフォルトコンストラクタでクラスの値が初期化されてから、代入演算子が実行されるので、ディフォルトコンストラクタ分の処理が無駄にかかります。

 

状態の取得

size_t size()	保持しているキーの数を取得します。
void empty()	キーがひとつも存在しない場合に true を返します。

std::unordered_map<> には、キーの数を知るための size メソッドの他にも、キーがひとつも登録されていないことを調べるための empty メソッドも用意されています。

 

イテレータ

iterator begin()	先頭のキーと値のセットを取得します。キーと値のセットは std::pair<KEY_TYPE, VALUE_TYPE> で取得できます。
iterator end()	キーと値のセットの末端（最後の次）を取得します。

イテレータというのは、繰り返し処理を支援する仕組みです。

イテレータの、間接演算子 (*) またはアロー演算子 (->) を使うと、std::unordered_map<> では std::pair<KEY_TYPE, VALUE_TYPE> 型の値を取得できます。

この std::pair<KEY_TYPE, VALUE_TYPE> の first メンバ変数でキーを、second メンバ変数で値を、取得できます。

 

begin 関数では最初の要素が取得でき、end 関数では最後の要素の次が取得できます。

std::unordered_map<> では、イテレータで取得できる要素の並び順は、システムが都合のいいように並び替えられています。キーの順番通りに要素を扱いたい場合は std::map<> を使用します。

 

要素の検索

iterator find(const KEY_TYPE key) const_iterator find(const KEY_TYPE key) const	指定したキーが設定されているものを見つけます。見つかったものはイテレータで返し、イテレータで取得できる値は std::pair<KEY_TYPE, VALUE_TYPE> 型になります。指定したキーが見つからなかった場合は、末端を示すイテレータ (end) を返します。
size_t count(const KEY_TYPE key) const	指定したキーを持つ要素の数を取得します。

 

std::unordered_map<> が、あるキーを持っているかは count 関数を使って判定できます。

std::unordered_map<> や std::map<> では同じキーは存在しないはずなので、キーが存在すれば 1 が得られると思いますが、少なくともキーが存在しない場合は 0 が得られるため、これが 0 でなければキーが存在しません。

 

また、少しわかりにくくなりますが、find 関数を使ってもキーの存在判定ができます。

探したいキーを find 関数に渡すとそのキーを持っている要素が最初に現れた位置を示したイテレータが取得できます。指定したキーが存在しない場合には、末端を示すイテレーターが返されます。

これを使って、たとえば "key1" が存在するかを調べることができます。

 

要素の交換

void swap(std::unordered_map<>& source)	指定された std::unordered_map<> の要素と、自身が保持する要素とを入れ替えます。

このような 2 つの std::unordered_map<> の要素を交換するメソッドも用意されています。

 

使用できる演算子

一致の判定

==	ふたつの std::unordered_map<> が一致するかを調べます。要素は == 演算子を使って評価されます。
!=	ふたつの std::unordered_map<> が一致しないかを調べます。要素は == 演算子を使って評価されます。

std::unordered_map<> での一致判定は、2 つの std::unordered_map<> の .size() が一致するかどうかと、各キーの要素数が同じで、それぞれの値が同一順序で正しいかどうかで判定されます。要素毎の判定では等価演算子 (==) が使用されます。

全てを満たす時に true、どれかが満たされない場合に false となります。

 

順位の判定

std::unordered_map<> では、順位判定の演算子は実装されていません。

 

要素の操作

[]	std::unordered_map<> の指定されたキーの std::pair<KEY_TYPE, VALUE_TYPE> を取得します。

std::unordered_map<T> では [] 演算子を使って指定したキーの値を取り出せるようになっています。

取り出せる値は std::pair<KEY_TYPE, VALUE_TYPE> 型で、これの first メンバ変数でキーが、second メンバ変数でその値が、それぞれ取得できます。

 

存在しないキーを指定すると、そのキーが新たに生成され、値には既定値（クラスならディフォルトコンストラクタ）が設定されます。

勝手にキーが生成されると困る場合は at() メソッドを使うことで、存在しないキーにアクセスしたときに out_of_range 例外が発生するようにすることができます。

 

クラスの値を扱う場合

std::std::unordered_map<> ではクラスインスタンスも扱うことができます。

たとえばこのようにすることで、キーが std::string 型で値が CMyClass 型の std::unordered_map<> を使えます。

この時、挿入されるインスタンスは、通常はコピーコンストラクタまたは代入演算子を使って生成された新しいインスタンスになります。erase メソッドなどで削除されたインスタンスは、デストラクタが呼び出されます。

 

ただし、クラスにムーブコンストラクタが実装されている場合には、std::move 関数を使って代入すれば、委譲という形で代入することもできます。

委譲については 右辺値参照とムーブコンストラクタの使い方 に詳しくまとめておきます。

 

ところで、std::unordered_map<> には 2 つの要素追加の方法があります。

使いやすい [] 演算子の場合、存在しないキーを指定した場合には新しくそのキーと値のセットが作成されるのですが、このときの値は、ディフォルトコンストラクタを使って生成されたクラスになります。

その後で、代入演算子を使ってそのキーに値を代入するので、ディフォルトコンストラクタを使って生成されたインスタンスは、すぐに代入演算子で上書き（コピーまたは委譲）されます。

 

ディフォルトコンストラクタの処理コストが小さければ問題ありませんが、その 1 回の無駄なコピーコンストラクタの処理を省きたい場合は insert 関数を使います。

insert 関数では std::pair<KEY_TYPE, VALUE_TYPE> を引数に取ってキーと値のセットを追加します。

このとき std::pair<KEY_TYPE, VALUE_TYPE> のコンストラクタを使って初期化すると、このキーと値のセットを CMyClass のコピーコンストラクタを使って初期化できます。

それを insert 関数に std::move を使って渡すことで、ムーブコンストラクタで値を追加できます。

こうすることで、無意味にディフォルトコンストラクタを呼び出すことなく、値をセットすることができました。

 

クラスのポインターを扱う場合

クラスのポインターを持つ std::unordered_map<> を作成した場合は、そこに格納したポインタが指すインスタンスの管理は自分で行う必要があります。

この場合は、キーと値のセットを [] 演算子や at 関数、insert 関数などで設定するときや、clear 関数や erase 関数を使って破棄する前に、値として格納しているインスタンスの構築や破棄を適切に行う必要があります。

または、スマートポインタ を使って自動管理するのもいいかもしれません。

 

std::unordered_map<> ではイテレータを使って繰り返し処理を行えます。

このとき、イテレータの型は std::unordered_map<>::iterator になり、これに整数を足したり引いたりすることで任意の場所へ簡単に移動することができるようになっています。

const 指定の std::unordered_map<> の場合には、イテレータは std::unordered_map<>::const_iterator を使います。

このように、イテレータを for 構文の中で使用して、最初に取得できた要素を使って初期化してから、最後を示すイテレータが現れるまでの間、イテレータをひとつひとつ進めることで、全ての要素を繰り返し処理しています。

このとき、end メソッドで取得できる最後のイテレータは、最後の要素の次の位置を示しているので、end メソッドによって得られたイテレータと一致したタイミングでループを抜けられます。

 

std::unordered_map<> で取得できるイテレータは、キーと値のセットを std::pair<KEY_TYPE, VALUE_TYPE> で返すようになっているので、取得した std::pair<> の first メンバ変数で対象要素のキーを、second メンバ変数で値を、それぞれ取得できます。

 

std::unordered_map<> は <algorithm> ヘッダーに定義されている std::sort 関数を使って並び替えることはできません。

ただ、<map> ヘッダーには std::map<> というキーで整列されるクラスがあるので、これに値をコピーすることで並び替えを実現できます。

これで hash をキー順に並び替えた sortedHash を取得できました。

std::unordered_map<> が持っていた各要素は、それぞれ std::map<> へコピーコンストラクタを使って複製されます。

 

このとき、std::unordered_map<> のキーの型と値の型と、std::map<> のキーの型と値の型とが同じでないと、コンパイル時にエラーになるので注意が必要です。

また、母体となるクラスが std::unordered_map<> から std::map<> に変わりますが、どちらも同じように操作できます。

 

なお、この方法だとコピーが行われるため、並び替え前の値と並び替え後の値は、実体は別のものになります。

どちらからでも同じ実体にアクセスさせたい場合には、扱う値をポインターにする必要があります。ただ、純粋なポインターだと管理が難しくなりがちなので、std::shared_ptr などの スマートポインタ が便利です。

 

C++11 では、一時変数から保存用の変数に std::unordered_map<> を移すようなときに、不必要なコピー処理を行わなくて済むようにするための右辺値参照という仕組みが規定されています。

それについては 右辺値参照とムーブコンストラクタの使い方 で詳しく紹介してありますが、std::unordered_map<> も右辺値参照を引数に取る代入演算子とムーブコンストラクタが用意されているので、簡単に委譲することができます。

このように、右辺を std::move 関数を使って明示的に右辺値参照とすることで、今回の例では oldHash に格納されている要素をそのまま newHash に移動させることができます。

このとき、右辺に指定した oldHash の内容は破壊されるので、これ以降は使えなくなります。

 

実際にこれを行ってみると、oldHash が持っている要素をひとつも破棄することなく、newHash に持たせる要素をひとつも新規生成することなく、std::unordered_map<> の値を oldHash から newHash へ移行することができました。

特に std::unordered_map<> でクラスを扱っている場合はコピーのコストが大きくなりがちなので、可能なところは積極的に使って行くのが良さそうです。

ちなみに、関数の戻り値で受け取ったクラスを変数に受けるときは、戻り値は自動的に右辺値参照として扱われるため、明示的に std::move 関数を呼び出さなくて大丈夫です。

---

[ もどる ]