ハッシュ連想配列クラス unordered_map とは

std::unordered_map とは C++11 で標準に使用できるようになった便利な連想配列クラスでござるぞ。
「連想配列クラス」とは検索可能なキーと、キーに対応する値の組（ペア）を要素とするコンテナクラスで、 保持している要素から、キーを指定して値を高速に取り出せるクラスのことだ。

例えば、string 型の人名と int 型の年齢を組にした要素を保持しておくと、名前をキーにして年齢を高速に取得することができる。 名前から年齢への写像（mapping.）のようなものなので map というクラス名を持つ。 ※ タイトルのところにある画像のように地図（map）という意味ではない。

本来であれば、unordered_map は hash_map のようなクラス名になるべきであったが、そのような名前のライブラリが数種公開されていたので、 それらとの衝突を避けるために unordered_map という名前になった。

unordered_map とよく似たクラスとして、std::map というものもある。 map は 二分木 を使っているために、キーから要素を取り出す処理時間が O(log N) で、そこそこ高速である。
それに対し、unordered_map クラスは O(1) で、さらに高速である。これは、unordered_map が ハッシュテーブル で実装されているからだ。
ただし、unordered_map はその名前の通り、要素を順序付けできないという欠点があるので、 順序付けが必須の場合は map を使うことになる。

準備：インクルード

unordered_map は C++標準ライブラリに含まれており、「#include <unordered_map>」を記述することで利用可能になる。

名前空間は「std」なので、使用の度に「std::」を前置するか、または「using namespace std;」を記述しておく。

#include <unordered_map>       // ヘッダファイルインクルード
int main()
{
    std::unordered_map<std::string, int> mp;       // ローカル変数として、mp を生成
    .....
}

#include <unordered_map>       // ヘッダファイルインクルード
using namespace std;         //  名前空間指定
int main()
{
    unordered_map<string, int> mp;       // ローカル変数として、mp を生成
    .....
}

宣言・初期化

単純な宣言

std::unordered_map オブジェクトを生成するには「std::unordered_map<キー型, 値型> オブジェクト名;」 と記述する。
オブジェクト名とは、宣言する連想配列を識別するための名前のことだ。変数名と言ってもよい。 unordered_map はクラスなので、それを実体化したものはオブジェクトまたはインスタンスと呼ばれる。

unordered_map が vector や list 等の通常コンテナクラスと異なるのは、コンテナに入る要素の型を２つ指定するところだ。
最初の型はキーとなるものの型で、string や int 型などいろいろな型を指定できる。 ただし、どんな型でも指定できるかというとそうではなく、ノードのハッシュ値を計算可能でないといけない。
数値（整数、浮動小数点数）、ポインタ、std::string はハッシュ関数が予め定義されているので、そのまま使用することが出来る。

    std::unordered_map<double, int> mp;     // 浮動小数点数 → 整数の連想配列

vector 等はそのままではキーの型として指定できないが、テンプレートパラメータの3番目にハッシュ関数オブジェクトを指定してやれば大丈夫だ。

下記は、vector<int> 用のハッシュ関数オブジェクトの定義例だ。

class HashVI {  // ハッシュ関数オブジェクト
public:
    size_t operator()(const vector<int> &x) const {
        const int C = 997;      // 素数
        size_t t = 0;
        for (int i = 0; i != x.size(); ++i) {
            t = t * C + x[i];
        }
        return t;
    }
};

    std::unordered_map<vector<int>, int> mp1;        // ビルドエラー
    std::unordered_map<vector<int>, int, HashVI> mp2;        // ビルドOK

値型の方には特に条件は無い。どんな型・クラスでもたいてい使える。

下記は、string 型をキーとし、int 型を値とする連想配列 mp を宣言している例だ。

    std::unordered_map<std::string, int> mp;  //  string → int の連想配列 mp の宣言

このようにして宣言したオブジェクトの要素数は 0、つまり空だ。要素を追加する方法は次の章で説明する。

< > は何だ？と思う人もいるかもしれない。これはC++のテンプレートという機能を使うための記法だ。
テンプレートを完全に理解するのは難易度が高いので、深く理解しようとすると先に進めなくなる。 深入りはせず、現在のところはキーと値の型をこういう書き方で指定すると無条件で覚えてほしい。

コピーコンストラクタ

コピーコンストラクタとは、同じ型のオブジェクトを渡され、それと同じ内容のオブジェクトを生成するコンストラクタのことである。
「std::unordered_map<キー型, 値型> オブジェクト名(コピー元オブジェクト名);」と記述する。
当然ながら、コピー元オブジェクトと生成するオブジェクトは通常同じ型である必要がある。
※ 暗黙の型変換が可能な型であれば、コピー元オブジェクトとして指定可能ではある。

    std::unordered_map<std::string, int> org;
    org に要素を追加
    std::unordered_map<std::string, int> x(org);      // コピーコンストラクタ

上記のコードは org をコピーし、同じ値を持つ連想配列 x を生成する。

演習問題：

1. キー型 std::string, 値型 char の連想配列 mp を宣言しなさい。show

    std::unordered_map<std::string, char> mp;

2. キー型 int, 値型 double の連想配列 mp を宣言しなさい。show

    std::unordered_map<int, double> mp;

3. キー型 std::string, 値型 std::string の連想配列 mp を宣言しなさい。show

    std::unordered_map<std::string, std::string> mp;

4. キー型 std::vector<char>, 値型 int の連想配列 mp を宣言しなさい。show

class HashVC {  // ハッシュ関数オブジェクト
public:
    size_t operator()(const vector<char> &x) {
        const int C = 997;      // 素数
        size_t t = 0;
        for (int i = 0; i != x.size(); ++i) {
            t = t * C + x[i];
        }
        return t;
    }
};
    .....
    std::unordered_map<std::vector<char>, std::string, HashVC> mp;

値の設定、参照

キーに対応する値の設定

連想配列にキーに対する値を設定するには「mp[キー] = 値;」と記述する。

例えば、std::unordered_map<std::string, int> mp に対し、キー"abc" の値を 123 に設定するには、以下のように記述する。

    std::unordered_map<std::string, int> mp;    //  文字列 → 整数 のハッシュ連想配列
    mp["abc"] = 123;

この書き方は直感的にわかりやすく便利でしょ。

設定した値は何度でも上書きすることが出来る。

    mp["abc"] = 123;
    mp["abc"] = 456;
    mp["abc"] = 789;

上記の様に mp["abc"] の値を複数回設定した場合は、最後に設定した値が有効になる。

キーに対応する値を設定すると、unordered_map が持つハッシュテーブルにキーと値のペアが追加される。追加処理に要するコストは、O(1) である。

キーに対応する値の取得

右辺値として mp[キー] と記述することで、mp から キー を検索し、その値を取得することが出来る。
例えば、前節のように mp["abc"] に 123 が設定されているとき、mp["abc"] は 123 を返す。

値が設定されていないキーを指定した場合、値型のデフォルト値が返される。

    std::unordered_map<std::string, int> mp;
    mp["Lotus"] = 123;
    std::cout << mp["Lotus"] << "\n";       // mp["Lotus"] の値 123 が表示される
    std::cout << mp["IBM"] << "\n";        // mp["IBM"] は設定されていなかったので、0 が表示される

実は [] 演算子「operator[]()」が返す型は、右辺値であっても（非const な）値への参照である。したがって、連想配列が保持していないキーを使うと、 そのキーとデフォルト値のノードが作成されてしまうので、留意してほしい。

なので、const 型の連想配列に対しては [] 演算子を使うことは出来ない。

    std::unordered_map<std::string, int> mp;
    mp["Lotus"] = 123;
    const std::unordered_map<std::string, int> mp2(mp);      // const（変更不可）な mp2 を生成
    cout << mp2["Lotus"] << "\n";          //  右辺値なのにエラーとなる

上記の様に作った様な例ではなく、関数引数として const な連想配列を渡すことはよくある。そのような場合に [] 演算子は使用できないので注意だ。

連想配列が const の場合に値を参照したい場合は at(キー) メンバ関数を使う。この関数は const 型も定義されているので大丈夫だ。

    std::unordered_map<std::string, int> mp;
    mp["Lotus"] = 123;
    const std::unordered_map<std::string, int> mp2(mp);      // mp を元にして const（変更不可）な mp2 を生成
    cout << mp2.at("Lotus") << "\n";          //  123 が表示される

個人的には at() よりも [] 演算子の方が好きなので、なぜ [] 演算子が const 対応していないのか理解に苦しむ。 対応が技術的に難しいとは考えられないので、将来的には const 対応の [] 演算子を導入して欲しいものだ。

キーを探すコストは、要素数を N として O(1) である。

ノードが勝手に作成されないように、値が本当に設定されているかどうかを確認するには、次章で説明する検索機能を使用する。

全てのキー・値の取得

mp を unordered_map オブジェクトとすると、mp.begin() で最初の要素へのイテレータを、mp.end() で最後の要素の次へのイテレータを取得できる。
要素はキーと値のペア（std::pair）のことで、キー・値それぞれを itr->first, itr->second で取得できる。

下記は、連想配列の最初から最後までをイテレータを回し、要素の内容を表示する例だ。

    std::unordered_map<std::string, int> mp
    いろんな値を設定;
    for(auto itr = mp.begin(); itr != mp.end(); ++itr) {
        std::cout << "key = " << itr->first           // キーを表示
                        << ", val = " << itr->second << "\n";    // 値を表示
    }

map の場合、キーが昇順にソートされているので、上記を実行するとキー文字列が昇順に表示されるが、unordered_map の場合はキーの順序は不定だ。

ちなみに、イテレータを進めるのに要するコストは O(1) である。よって、最初から最後までイテレータを進めるのに要するコストは 要素数を N とすると、O(1) * N = O(N) となる。

演習問題：

1. キー、値ともに文字列型の連想配列 mp を宣言し、"aiueo" の値を "123" に、"kakikukeko" の値を "9876" に設定しなさい。 show

    std::unordered_map<std::string, std::string> mp;
    mp["aiueo"] = "123";
    mp["kakikukeko"] = "9876";

2. 文字列をキー、整数を値とする連想配列 mp を宣言し、"aiueo" の値を 1 に、"kakikukeko" の値を 2 に設定しなさい。show

    std::unordered_map<std::string, int> mp;
    mp["aiueo"] = 1;
    mp["kakikukeko"] = 2;

3. 上記 mp に対し、mp["aiueo"], mp["kakikukeko"], mp["sashisuseso"] の値を表示するコードを書きなさい。show

    std::cout << mp["aiueo"] << "\n";
    std::cout << mp["kakikukeko"] << "\n";
    std::cout << mp["sashisuseso"] << "\n";

4. 連想配列、値を引数にとり、連想配列に値が含まれるかどうかをチェックする関数 bool isContained(const std::unordered_map<std::string, int> &mp, int val) を定義しなさい。
   文字列をキー、整数を値とする連想配列 mp を宣言し、mp["aiueo"] = 1; mp["kakikukeko"] = 2; を実行後に、 isContained(mp, 0) は false を、isContained(mp, 1) は true を、isContained(mp, 2) は true を、isContained(mp, 3) は false を返すことを確認しなさい。 show

bool isContained(const std::unordered_map<std::string &mp, int>, int val)
{
    for(auto itr = mp.begin(); itr != mp.end(); ++itr) {
        if( itr->second == val )       // 値を発見した場合
            return true;
    }
    return false;      //  値が発見できなかった場合
}

5. キー、値ともに int 型の連想配列 mp を宣言し、キー・値をランダムに生成し100個のペアを mp に追加しなさい。 その後、mp に格納されている要素を begin() から end() まで表示し、キーが昇順に並んではいないことを確認しなさい。show

    std::unordered_map<int, int> mp;
    const int N = 100;
    for(int i = 0; i < N; ++i) {
        mp[rand()] = rand();
    }
    for (auto itr = mp.begin(); itr != mp.end(); ++itr) {
        std::cout << itr->first << ": " << itr->second << "\n";
    }

6. キー、値ともに int 型のハッシュ連想配列 mp を宣言し、キー・値をランダムに生成し1万個のペアを mp に追加するのに要する 時間を計測 しなさい。 追加する要素数を 10万個、100万個とした場合の処理時間も計測し、比較しなさい。show

#include <unordered_map>
#include <windows.h>
#pragma comment(lib, "winmm.lib")
void measure(int N)
{
    unordered_map<int, int> mp;
    DWORD start = timeGetTime();       // スタート時間
    for (int i = 0; i < N; ++i) {
        mp[rand()] = rand();
    }
    DWORD end = timeGetTime();    // 終了時間
    std::cout << "duration = " << (double)(end - start) / 1000 << "sec.\n";
}
int main()
{
    measure(10000);
    measure(100000);
    measure(1000000);
    return 0;
}

キーの検索

mp を unordered_map オブジェクトとすると、mp.find(キー) で、キーが mp に設定されているかどうかを調べることが出来る。
キーが設定されている場合は、キーと値のペアへのイテレータを返す。
キーが設定されていない場合は、end() へのイテレータを返す。

    std::unordered_map<std::string, int> mp
    いろんな値を設定;
    auto itr = mp.find("xyz");        // "xyz" が設定されているか？
    if( itr != mp.end() ) {
        設定されている場合の処理
    } else {
        設定されていない場合の処理
    }

キーと値のペアとは std::pair<キー型, 値型> のことである。なので、キーは itr->first, 値は itr->second で取得することが出来る。

    auto itr = mp.find("xyz");
    if( itr != mp.end() ) {
        cout << itr->first << "\n";             //  "xyz" が表示される
        cout << itr->second << "\n";         // mp["xyz"] の値が表示される
    }

itr が end() でない場合は、「itr->second = 値;」で、値を書き換えることも出来るぞ。

演習問題：

1. キー型：文字列、値型：int のマップを生成し、"abc" の値を 1 に、"xyz" の値を 9 に設定し、それぞれを検索し結果が正しいことを確認しなさい。 show

    std::unordered_map<std::string, int> mp;
    mp["abc"] = 1;
    mp["xyz"] = 9;
    auto itr = mp.find("abc");
    if( itr != mp.end() && itr->first == "abc" && itr->second == 1 )
        std::cout << "OK\n";
    else
        std::cout << "NG\n";
    itr = mp.find("xyz");
    if( itr != mp.end() && itr->first == "xyz" && itr->second == 9 )
        std::cout << "OK\n";
    else
        std::cout << "NG\n";

2. 上記マップに対し "aiueo" を検索し、結果が正しいことを確認しなさい。show

    itr = mp.find("aiueo");
    if( itr == mp.end() )
        std::cout << "OK\n";
    else
        std::cout << "NG\n";

3. 上記マップに対し、"xyz" を検索し、その値を 10 に書き換えなさい。show

    itr = mp.find("xyz");
    if( itr != mp.end() )
        itr->second = 10;

要素の削除

連想配列に設定された要素の削除は erase(キー) または erase(イテレータ) で行う。

mp から、キー："abc" の要素を削除したい場合は mp.erase("abc") とすればよい。直感的で簡単だ。
存在しないキーを指定した場合は、無視され何も起こらない。

予め、キーが存在しているかどうかをチェックし、存在している場合のみ削除したい場合は、 以下のように find() でキーが存在することを確認してから、erase(イテレータ) を使用する。

    auto itr = mp.find("abc");
    if( itr != mp.end() )         // キーの要素が存在している場合
        mp.erase(itr);

実はイテレータには end() を指定しても何も問題は起こらない。なので、単に mp.erase(mp.find("abc")); と書いてもいいのだが、 そう書くくらいなら mp.erase("abc") と書いた方が素直で好感が持てる。

演習問題：

1. キー型：文字列、値型：int の unordered_map を生成し、"abc" の値を 1 に、"xyz" の値を 9 に設定したのち、erase(キー) により "abc" の要素を削除し、 それが正しく削除されたことを確認しなさい。show

    std::unordered_map<std::string, int> mp;
    mp["abc"] = 1;
    mp["xyz"] = 9;
    mp.erase("abc");
    for(auto itr = mp.begin(); itr != mp.end(); ++itr) {
        cout << "mp[" << itr->first << "] = " << itr->second << "\n";
    }

2. キー型：文字列、値型：int の unordered_map を生成し、"abc" の値を 1 に、"xyz" の値を 9 に設定したのち、erase(イテレータ) により "abc" の要素を削除し、 それが正しく削除されたことを確認しなさい。show

    std::unordered_map<std::string, int> mp;
    mp["abc"] = 1;
    mp["xyz"] = 9;
    auto itr = mp.find("abc");
    mp.erase(itr);
    for(auto itr = mp.begin(); itr != mp.end(); ++itr) {
        cout << "mp[" << itr->first << "] = " << itr->second << "\n";
    }

その他のメンバ関数

オブジェクトの状態を取得

• empty()
• size()

「bool empty()」は連想配列が空かどうかを判定する関数。
次に出てくる size() を使って、size() == 0 と判定するのと同等だ。 が、コンテナクラスによっては size() 計算よりも empty() の方が高速な場合がある。 なので、コンテナクラスに対しては empty() を使うことが推奨されている。

「size_t size()」は、要素数を返す関数。
通常配列だと「sizeof(data)/sizeof(data[0])」のように記述しないと、要素数を取得できないが、 unordered_map では「mp.size()」と簡潔かつ分かりやすく書ける。

※ size_t はサイズを表す型で、符号なし整数の組み込み型である。ちなみに、sizeof() も size_t 型を返す。

オブジェクトの状態を変更

• clear()

「clear()」は連想配列を空にする関数。
サイズを0にする。vector とは違い、要素を delete し、メモリが解放される。

演習問題：

1. std::unordered_map<std::string, int> mp; に対して、empty(), size() をコールし、それぞれの値を表示するコードを書きなさい。 show

    std::unordered_map<std::string, int> mp;
    std::cout << mp.empty() << "\n";
    std::cout << mp.size() << "\n";

2. 上記 mp に対し、mp["abc"] = 123; mp["xyz"] = 987; を実行後に empty(), size() をコールし、それぞれの値を表示するコードを書きなさい。 show

    mp["abc"] = 123;
    mp["xyz"] = 987;
    std::cout << mp.empty() << "\n";
    std::cout << mp.size() << "\n";

3. 上記実行後に mp.clear() を実行し、empty(), size() をコールし、それぞれの値を表示するコードを書きなさい。 show

    mp.clear();
    std::cout << mp.empty() << "\n";
    std::cout << mp.size() << "\n";

map との違い

std::unordered_map と std::map の違いについてまとめておく

	unordered_map	map
サポート	C++11	C++
データ構造	ハッシュテーブル	二分木（通常は赤黒木）
登録・削除・検索時間	O(1)	O(log N)
キー型の制約	hash() が定義済みであること。 または、ハッシュ関数オブジェクトを渡す	operator<() が定義済みであること。 または、自分で定義する
長短所	◎ 高速 △ キーが順序付けされない	◎ キーが順序づけされる △ unordered_map ほどは高速でない

まとめ・参考

本稿で説明したのは、std::unordered_map の基本的な部分のみである。説明していないメソッドもたくさんある。
それらについては以下のサイトなどで勉強してほしい。

• http://www.cplusplus.com/reference/unordered_map/unordered_map/

総合演習問題の問題募集中です。

総合演習問題

---

　

　

著者開発アプリ

数々のおもてなし機能で、さくさく解ける数独アプリ 「SakuSaku Sudoku」 for Android/Windows

最近更新したページ

人気のページ

関連ページ

• C++ マップクラス std::map 入門
• C++ 動的配列クラス std::vector 入門
• C++ 双方向リストクラス std::list 入門
• C++ 文字列クラス std::string 入門
• C++ 乱数 std::random 入門
• C/C++ 処理時間計測 入門
• C/C++ static 修飾子 入門
• JavaScript 配列入門