キーを重複して持てる連想配列を使用する - C++ プログラミング
PROGRAM
キーを重複して持てる連想配列を使用する
C++11 では、キーと値をセットで管理する連想配列を簡単に利用できるテンプレートクラスが用意されています。
よくある連想配列は std::unordered_map<> という同じ値のキーが 1 つしか登録されないタイプのものなのですけど、C++11 にはもうひとつ std::unordered_multimap<> というものも用意されています。
こちらは同じ値のキーを複数持つことができるので、たとえば「キー」をグループ名にして、そのグループに属するものを「値」で管理するようなときに便利です。
ここでは std::unordered_multimap<> について std::unordered_map<> と比較しながら、その基本的な使い方を見て行きます。
ちなみに、std::unordered_multimap<> は、キーを登録した順番とは関係なく（ハッシュを使って）格納するタイプのものになります。また、同じキーに対する値の並び順も定められていない様子です。
キーを順番通りに（キーと値を辞書的順序で）格納したい場合は <multimap> ヘッダーに定義されている std::multimap<> を使用します。std::multimap<> と std::unordered_multimap<> の使い方は基本的に同じです。
使用準備
std::unordered_multimap<> は std::unordered_map<> と同じヘッダー <unrodered_map> に定義されています。
#include <unordered_map>
これで std::unordered_multimap<> テンプレートクラスが利用できるようになります。
初期化
std::unordered_multimap<> インスタンスは、std::unordered_mup<> と同じように宣言できて、最初に「キー」で使うデータ型を、続いて「値」で使うデータ型を指定して生成します。
std::unordered_multimap<std::string, int> hash;
左側で指定している "std::unordered_multimap<std::string, int>" がデータ型になります。
これで、キーの型が "std::string" で、値が "int" の連想配列 "hash" を定義することができました。今回は unordered_multimap<> なので、同じキーで複数の値（同じキーのキーと値のセット）を持つことができます。
利用できるメソッド
std::unordered_multimap<> には、連想配列を操作するためのメソッドがいくつか用意されています。
その中の、よく使いそうなメソッドをいくつか紹介します。
| std::pair<iterator,bool> insert(const std::pair<KEY_TYPE, VALUE_TYPE>) |
インスタンスにキーと値のセットを追加します。戻り値で、iterator で挿入された位置が、bool で挿入されたかどうかが返されます。 |
|---|---|
| std::pair<iterator, iterator> equal_range(const KEY_TYPE key) const; |
指定したキーが設定されている要素の、最初の要素を示すイテレーターと末端を表すイテレーターを std::pair<> で返します。定したキーが見つからなかった場合は、どちらとも末端を示すイテレータ (end) になります。 |
| size_t count(const KEY_TYPE key) const | 指定したキーを持つ要素の数を取得します。 |
| void clear() | 格納されているキーと値のセットを全て削除します。 |
| size_t erase(const KEY_TYPE& key) | 指定したキーを削除します。イテレータを使って削除する範囲を指定することもできます。削除したキーの数を返します。 |
std::unordered_multimap<> の std::unordered_map<> との大きな違いは、[] 演算子と at 関数がないところです。
std::unordered_multimap<> では、同じキーを持つ複数のキーと値のセットを持つことができるので、std::unordered_map<> のときのように、キーの名前からひとつのキーと値のセットを決定することができません。
そのため、値を追加するときには insert 関数を、値を取得するときには find 関数を、使う必要があります。
要素の追加
値の追加は、次のように insert 関数を使って、キーと値のセットを指定して追加します。
// std::unrodered_multimap<> と同型の値を取る std::pair<> を作って insert 関数に渡します。
hash.insert(std::pair<std::string, int>("key1", 100));
std::unordered_multimap<> を定義したときのキーと値のセットと同じ型を std::pair<> に指定して作成したインスタンスを、insert 関数の引数として指定すれば、その std::pair<> の値が複製されて std::unordered_multimap<> に追加されます。
このとき、insert 関数の引数のところで直接 std::pair<> のコンストラクタで作成したものを指定するか、関数の戻り値から得られたものを指定すれば、右辺値参照を使って値を設定できて処理効率が良くなります。
insert 関数の呼び出しとは分けて、いったん std::pair<> 変数にセットした値を insert 関数で指定する場合は、そのまま指定するとコピーコンストラクタでの複製になるので、代入後に元の値を使う予定がない場合は std::move 関数を通して引数に渡すと、ムーブコンストラクタが使えて効率的です。
右辺値参照とムーブコンストラクタについては 右辺値参照とムーブコンストラクタの使い方 で詳しく紹介してあります。
値の取得
std::unordered_multimap<> では、ひとつのキーに対して、キーと値のセットがいくつあるか判りません。
そのため、値の取得には equal_range 関数を使って、指定したキーを持つキーと値のセットを順次取得する必要があります。
// equal_range 関数を使って、指定したキーの最初と終端の位置を示すイテレータを std::pair<> で取得します。
std::pair<std::unordered_multimap<std::string, int>::iterator, std::unordered_multimap<std::string, int>::iterator> range = hash.equal_range("key1")
// 取得したイテレータの範囲をループで回します。
for (std::unordered_multimap<std::string, int>::iterator iterator = range.first; iterator != range.second; iterator++)
{
// ここで、"key1" をキーに持つキーと値のセットをひとつひとつ処理します。
std::pair<std::string, int> target = *iterator;
}
イテレータの型が "std::unordered_multimap<std::string, int>::iterator" と長いので、C++11 で追加された auto による型推論を使うとずいぶん簡単で見通しのいいプログラムになります。
// equal_range 関数を使って、指定したキーの最初と終端の位置を示すイテレータを std::pair<> で取得します。
auto range = hash.equal_range("key1")
// 取得したイテレータの範囲をループで回します。
for (auto iterator = range.first; iterator != range.second; iterator++)
{
// ここで、"key1" をキーに持つキーと値のセットをひとつひとつ処理します。
auto target = *iterator;
}
ひとつ前のプログラムとこのプログラムは同じ処理をするプログラムになっているので、本来の動きの感じを掴めたら、このように型推論を使ってプログラムするのがおすすめです。
ここでもし、指定したキーがひとつも見つからなかった場合は、equal_range 関数が返すイテレータのペアはどちらも末端を示すイテレータ（end 関数が返すイテレータ）と同じになります。
そのため、見つからなかったことは "range.first == hash.end()" で判定できますし、また、先ほどの for ループにそのまま渡してもループを実行することなく抜けられます。
ちなみに std::unordered_map<> では find という関数もありましたが、この関数では、指定したキーを持つ最初のキーと値のセットの位置がイテレータで取得できます。
このイテレータはあくまでも最初の位置を取得できるだけなので、イテレータを進めて行くとそのうち次のキーに移動するので、キーの値が 1 つとは限らない std::unordered_multimap<> で値を取得するのには向きません。
キーが重複している数を取得
あるキーがいくつ登録されているかを知るには count 関数を使います。
// 指定したキーの登録数を調べます。
size_t count = hash.count("key1");
登録数を知りたいキーを count 関数の引数に渡すと、そのキーを持つキーと値のセットがいくつ登録されているかを取得できます。
登録されていない場合は 0 が得られます。
キーと値のセットの状態取得
| size_t size() | 保持されているキーの数を取得します。 |
|---|---|
| void empty() | キーがひとつも存在しない場合に true を返します。 |
std::unordered_multimap<> には、std::unordered_map<> と同様に、キーの数を知るための size メソッドと、キーがひとつも登録されていないことを調べるための empty メソッドが用意されています。
要素の数を取得する count メソッドもありますが、それはキーを指定してそのキーがいくつ登録されているかを知るものなのに対し、こちらは全体の数を知るためのものになります。
イテレータ
| iterator begin() | 先頭のキーと値のセットを取得します。キーと値のセットは std::pair<KEY_TYPE, VALUE_TYPE> で取得できます。 |
|---|---|
| iterator end() | キーと値のセットの末端（最後の次）を取得します。 |
begin 関数では最初の要素が取得でき、end 関数では最後の要素の次が取得できます。
同じキーで複数の値が存在する場合は、その値それぞれが、キーと値のセットで 1 つずつ取得されます。
std::unordered_multimap<> では、イテレータで取得できる要素の並び順は、システムが都合のいいように並び替えられています。キーの順番通りに要素を扱いたい場合は std::multimap<> を使用します。
要素の検索
std::unordered_multimap<> では、指定したキーを持つ値を探す関数として find 関数が用意されています。
| iterator find(const KEY_TYPE key) const_iterator find(const KEY_TYPE key) const |
指定したキーが設定されているものを見つけます。見つかったものはイテレータで返し、イテレータで取得できる値は std::pair<KEY_TYPE, VALUE_TYPE> 型になります。指定したキーが見つからなかった場合は、末端を示すイテレータ (end) を返します。 |
|---|
ただ std::unordered_multimap<> の場合は、ひとつのキーに対して複数の値が存在する場合があるため、この find 関数を使って値を取得しても、そのうちの最初の 1 つの場所しか得られません。
そのため、指定したキーのキーと値のセットを取得したい場合は、値の取得のところで書いた equal_range 関数の方が使い勝手が良さそうです。
また、指定したキーが存在するかを調べたい場合も、count 関数を使って要素数が 0 かどうかを調べる方が明瞭です。
要素の交換
| void swap(std::unordered_multimap<>& source) | 指定された std::unordered_multimap<> の要素と、自身が保持する要素とを入れ替えます。 |
|---|
このような 2 つの std::unordered_multimap<> の要素を交換するメソッドも用意されています。
使用できる演算子
一致の判定
| == | ふたつの std::unordered_multimap<> が一致するかを調べます。要素は == 演算子を使って評価されます。 |
|---|---|
| != | ふたつの std::unordered_multimap<> が一致しないかを調べます。要素は == 演算子を使って評価されます。 |
std::unordered_multimap<> での一致判定は、2 つの std::unordered_multimap<> の .size() が一致するかどうかと、各キーの要素数が同じで、それぞれの値が同一順序で正しいかどうかで判定されます。要素毎の判定では等価演算子 (==) が使用されます。
全てを満たす時に true、どれかが満たされない場合に false となります。
順位の判定
std::unordered_multimap<> では、順位判定の演算子は実装されていません。
登録されているキーの一覧を取得する
std::unordered_multimap<> には、登録されているキーを重複のない形で取得する関数はありません。
そのため、登録されているキーの一覧を取得したい場合には、std::unordered_set<> や std::vector などを使ってキーのリストを取得する必要があります。
std::unordered_set<> なら、キーをハッシュで管理してくれるのと、重複が自動で省かれるので、向いているような気がします。
// キーと同じ型の値を扱う std::unordered_set<> を定義します。
std::unordered_set<std::string> keys;
// そこに std::unordered_multimap<> の全ての要素のキーを挿入します。
std::for_each(hash.begin(), hash.end(), [&keys](std::pair<std::string, int> element) { keys.insert(element.first); });
この例では std::for_each と ラムダ関数 を使ってキーの一覧を作成しています。
やっていることは、std::unordered_multimap<> の begin() から end() までの値（つまり最初から最後まで）を、std::for_each 関数に指定した次のラムダ関数を使って、見つかったキーを順次 std::unordered_set<> に追加しています。
[&keys](std::pair<std::string, int> element)
{
keys.insert(element.first);
}
ラムダ関数だけ取り出して整えると判りやすくなりますが、要はイテレータから取得できる値 (std::pair<std::string, int>) を受け取って、それのキーの値が格納されている first を、クロージャに参照で渡しておいた keys に追加しています。
std::unordered_set<> の特徴上、同じキーが複数登録されることはないので、これで重複しないキーの一覧を取得することができました。
std::unordered_multimap<> でクラスインスタンスを扱う場合
クラスの値を扱う場合
std::std::unordered_multimap<> ではクラスインスタンスも扱うことができます。
std::unordered_multimap<std::string, CMyClass> hash;
たとえばこのようにすることで、キーが std::string 型で値が CMyClass 型の std::unordered_multimap<> を使えます。
この時、挿入されるインスタンスは、通常はコピーコンストラクタまたは代入演算子を使って生成された新しいインスタンスになります。erase メソッドなどで削除されたインスタンスは、デストラクタが呼び出されます。
値の追加は std::unordered_multimap<> では [] 演算子がないので insert 関数を使いますが、この引数で指定した std::pair<> の値はコピーコンストラクタを使って複製されます。
このとき、格納されているクラスのインスタンスもコピーされます。
クラスがムーブコンストラクタを実装していて、設定し終えたキーと値のセットを入れた変数をそれ以降使わない前提であれば、std::move 関数を使って委譲という形で代入することもできます。
委譲については 右辺値参照とムーブコンストラクタの使い方 に詳しくまとめておきます。
// このインスタンスを値としてセットしたいとします。ここでコンストラクタを使って値をセットします。
CMyClass value(100);
// std::pair<> を使ってキーと値のセットを構築します。このときセットする値を右辺値参照で std::pair<> に委譲すれば、ムーブコンストラクタで値を格納できます。
std::pair<std::string, CMyClass> keyValue = std::pair<std::string, CMyClass>("key1", std::move(value));
// 用意したキーと値のセットを insert 関数に渡す時にも右辺値参照で渡すことで、値をムーブコンストラクタで std::unordered_map<> に委譲できます。
hash.insert(std::move(keyValue));
こうすることで、コピーコンストラクタを使わずに、効率的に値をセットすることができました。
クラスのポインターを扱う場合
クラスのポインターを持つ std::unordered_multimap<> を作成した場合は、そこに格納したポインタが指すインスタンスの管理は自分で行う必要があります。
std::unordered_multimap<std::string, CMyClass*> hash;
この場合は、キーと値のセットを insert 関数で設定するときや、clear 関数や erase 関数を使って破棄する前に、値として格納しているインスタンスの構築や破棄を適切に行う必要があります。
または、スマートポインタ を使って自動管理するのもいいかもしれません。
イテレータを使って繰り返し処理を行う
std::unordered_multimap<> でも、std::unordered_map<> と同じようにイテレータを使って繰り返し処理を行えます。
このとき、イテレータの型は std::unordered_multimap<>::iterator になり、これに整数を足したり引いたりすることで任意の場所へ簡単に移動することができるようになっています。
const 指定の std::unordered_multimap<> の場合には、イテレータは std::unordered_multimap<>::const_iterator を使います。
// イテレータを格納する変数を準備します。
std::unordered_multimap<std::string, CMyClass>::iterator iterator;
// 最初のイテレータから、最後のイテレータになるまで、イテレータを一つずつ先に進めます。
for (iterator = hash.begin(); iterator != hash.end(); iterator++)
{
// ここで、要素毎の操作を行います。
std::pair<std::string, CMyClass> element = *iterator;
}
このように、イテレータを for 構文の中で使用して、最初に取得できた要素を使って初期化してから、最後を示すイテレータが現れるまでの間、イテレータをひとつひとつ進めることで、全ての要素を繰り返し処理しています。
このとき、end メソッドで取得できる最後のイテレータは、最後の要素の次の位置を示しているので、end メソッドによって得られたイテレータと一致したタイミングでループを抜けられます。
std::unordered_multimap<> で取得できるイテレータは、キーと値のセットを std::pair<KEY_TYPE, VALUE_TYPE> で返すようになっているので、取得した std::pair<> の first メンバ変数で対象要素のキーを、second メンバ変数で値を、それぞれ取得できます。
なお、unordered_multimap<> ではひとつのキーに対して複数の値が持てるようになっていますが、内部的には同じキーの値を持つ「キーと値のセット」が複数存在していて、イテレータではこれらのキーと値のセットが 1 組みずつ順番に取得されます。
std::unordered_multimap<> を並び替える
std::unordered_multimap<> は <algorithm> ヘッダーに定義されている std::sort 関数を使って並び替えることはできません。
ただ、<map> ヘッダーには std::multimap<> というキーで整列されるクラスがあるので、これに値をコピーすることで並び替えを実現できます。
// 任意の並び順の std::unordered_map<std::string, CMyClass> があります。
std::unordered_multimap<std::string, CMyClass> hash;
// それを、キーでソートされる std::map<std::string, CMyClass> にコピーします。
std::multimap<std::string, CMyClass> sortedHash(hash.begin(), hash.end());
これで hash をキー順に並び替えた sortedHash を取得できました。
std::unordered_multimap<> が持っていた各要素は、それぞれ std::multimap<> へコピーコンストラクタを使って複製されます。
このとき、std::unordered_multimap<> のキーの型と値の型と、std::multimap<> のキーの型と値の型とが同じでないと、コンパイル時にエラーになるので注意が必要です。
また、母体となるクラスが std::unordered_multimap<> から std::multimap<> に変わりますが、どちらも同じように操作できます。
なお、この方法だとコピーが行われるため、並び替え前の値と並び替え後の値は、実体は別のものになります。
どちらからでも同じ実体にアクセスさせたい場合には、扱う値をポインターにする必要があります。ただ、純粋なポインターだと管理が難しくなりがちなので、std::shared_ptr などの スマートポインタ が便利です。
std::unordered_multimap<> を右辺値参照で移譲する
C++11 では、一時変数から保存用の変数に std::unordered_multimap<> を移すようなときに、不必要なコピー処理を行わなくて済むようにするための右辺値参照という仕組みが規定されています。
それについては 右辺値参照とムーブコンストラクタの使い方 で詳しく紹介してありますが、std::unordered_map<> も右辺値参照を引数に取る代入演算子とムーブコンストラクタが用意されているので、簡単に委譲することができます。
std::unordered_multimap<std::string, CMyClass> newHash = std::move(oldHash);
このように、右辺を std::move 関数を使って明示的に右辺値参照とすることで、今回の例では oldHash に格納されている要素をそのまま newHash に移動させることができます。
このとき、右辺に指定した oldHash の内容は破壊されるので、これ以降は使えなくなります。
実際にこれを行ってみると、oldHash が持っている要素をひとつも破棄することなく、newHash に持たせる要素をひとつも新規生成することなく、std::unordered_multimap<> の値を oldHash から newHash へ移行することができました。
特に std::unordered_map<> でクラスを扱っている場合はコピーのコストが大きくなりがちなので、可能なところは積極的に使って行くのが良さそうです。
ちなみに、関数の戻り値で受け取ったクラスを変数に受けるときは、戻り値は自動的に右辺値参照として扱われるため、明示的に std::move 関数を呼び出さなくて大丈夫です。
[ もどる ]