多重連想配列クラス std::multimap とは

std::multimap とは C++ で標準に使用できる便利な連想配列クラスでござるぞ。
「連想配列クラス」とは検索可能なキーと、キーに対応する値の組（ペア）を要素とするコンテナクラスで、 保持している要素から、キーを指定して値を高速に取り出せるクラスのことだ。
同じ連想配列クラスの std::map は、各キーに対する値はひとつだけだが、 この multimap は各キーに対する値を複数持つことができる。そういう意味で「多重連想配列」と呼ばれる。

データ構造

std::multimap のデータ構造の例を下図に示す。

これはデータ構造の一例であり、あなたの環境の実際のデータ構造とは少し違うかもしれない。

重要なことは、以下の３点である。

• 各ノードにはキーと値のペアが入っていて、左右の子供ノードへのポインタを持つ
• 左の子供のキー ≦ キー ≦ 右の子供のキー という条件が成立している
• ノードの深さは概ね同じで、ツリーはバランスしている

上記のおかげで、キーに一致するノードをルートから 二分探索 することが可能になるので、探索速度が O(Log N) と高速になるのだ。
※「二分探索」と聞くと恐れる人もいるかもしれないが、二分探索自体は multimap クラスが自動でやってくれるので、何も難しいことはないぞ。

重複を許さない map との大きな違いは、「左の子供のキー ≦ キー ≦ 右の子供のキー」という点だ。map では同じ値のキーは許されないので、 「左の子供のキー ＜ キー ＜ 右の子供のキー」となる。
multimap においては、ひとつのキーに対して複数の値がある場合は、その数だけ同じキーを持つノードが作られる。

準備：インクルード

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

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

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

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

宣言・初期化

単純な宣言

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

multimap が vector や list 等の通常コンテナクラスと異なるのは、コンテナに入る要素の型を２つ指定するところだ。
最初の型はキーとなるものの型で、string や int 型などいろいろな型を指定できる。 ただし、どんな型でも指定できるかというとそうではなく、ノードをキー順に並べるために、キーオブジェクトの順序が計算可能であるという条件がある。
具体的には bool operator<() が定義されていないとキーの型には指定できない。
例えば、vector はそのままではキーの型として指定できないが、vector の派生クラスを定義し、bool operator<() を定義してやれば大丈夫だ。

class KeyVectorInt : public std::vector<int>
{
    bool operator<(const KeyVectorInt &rhs)
    {
        return size() < rhs.size();   //  これは単なる例で、実際のコードとしては不適
    }
};

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

値型の方には特に条件は無い。

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

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

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

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

コピーコンストラクタ

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

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

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

演習問題：

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

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

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

    std::multimap<int, double> mp;

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

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

要素の追加

insert(キー・値のペア) : イテレータ

多重連想配列にキーと値の組を追加するには「mp.insert(std::pair<キー型, 値型>(キー, 値));」と記述する。
要素は キー と 値 のペア（組）なので std::pair を使う。

map の時は m[キー] = 値; と記述できたが、多重連想配列の場合は operator[](キー) が定義されておらず、insert() を使うしかない。正直、ちょっと面倒だ。

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

    std::multimap<std::string, int> mp;    //  文字列 → 整数 の連想配列
    mp.insert(std::pair<std::string, int>("abc", 123));

pair を型付きで書くのは面倒なので、以下のように make_pair を使うと、型の指定が不要になるので、もっと楽に記述できるぞ。

    std::multimap<std::string, int> mp;    //  文字列 → 整数 の連想配列
    mp.insert(std::make_pair("abc", 123));

同じキーを持つ要素を再度追加すると、その分だけ要素が追加される。

    mp.insert(std::make_pair("abc", 123));
    mp.insert(std::make_pair("abc", 987));
    mp.insert(std::make_pair("abc", 123));

上記の様に キー "abc" の要素を複数追加した場合は、キー、値のペアが全く同じであっても、３つの要素がすべて追加される。
map だと、最後に書き込んだペアだけが有効になる。そこが、map と multimap の違いだ。

要素を追加すると、multimap が持つツリーにキーと値のペアが追加される。追加処理に要するコストは、要素数を N として、O(Log N) である。 これはN個のデータを全て追加するコストが N * O(Log N) = O(N * Log N) であることを意味する。 通常、一連の操作で許される処理時間は O(N * Log N) までなので、充分高速な処理速度ということだ。

演習問題

1. キー、値ともに文字列型の連想配列 mp を宣言し、("aiueo", "123"), ("aiueo", "abc"), ("kakikukeko", "9876") のキー・値ペアを追加し、mp の中身をデバッガで確認しなさい。 show

    std::multimap<std::string, std::string> mp;    //  文字列 → 文字列 の連想配列
    mp.insert(make_pair("aiueo", "123"));
    mp.insert(make_pair("aiueo", "abc"));
    mp.insert(make_pair("kakikukeko", "9876"));

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

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

3. キー、値ともに int 型の連想配列 mp を宣言し、キー・値をランダムに生成し1万個のペアを mp に追加するのに要する時間を計測しなさい。 追加する要素数を 10万個、100万個とした場合の処理時間も計測・比較し、ひとつのペアを連想配列に追加するコストが O(log N) であることを確認しなさい。 show

#include <chrono>
void measure(int N)
{
    std::cout << N << ":";
    const int RAND_UPPER = 10000;       // 乱数値上限
    multimap<int, int> mp;
    auto start = std::chrono::system_clock::now();      // 計測スタート時刻を保存
    for (int i = 0; i < N; ++i) {
        mp.insert(make_pair(rand() % RAND_UPPER, rand() % RAND_UPPER));       // [0, 9999]
    }
    auto end = std::chrono::system_clock::now();       // 計測終了時刻を保存
    auto dur = end - start;        // 要した時間を計算
    // 要した時間をミリ秒（1/1000秒）に変換して表示
    std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(dur).count() << " milli sec \n";
}
int main()
{
    measure(10000);
    measure(100000);
    measure(1000000);
}

要素の検索

キーに対応する値を取得したい場合は、以下の検索関数を使用する。

• find(キー) : イテレータ
• lower_bound(キー) : イテレータ
• upper_bound(キー) : イテレータ
• equal_range(キー) : pair<イテレータ, イテレータ>

検索関数はどれもキー・値ペアを指すイテレータを返す。返ってきたイテレータから、キー、値を取り出したいときは itr->first, itr->second と記述する。

find(キー) : イテレータ

find(キー) は、キーを検索し発見できた場合は、キー・値ペアを指すイテレータを返す。キーを持つ要素が無かった場合は オブジェクト.end() を返す。

    std::multimap<std::string, int> mp;    //  文字列 → 整数 の連想配列
    mp.insert(std::make_pair("abc", 123));
    auto itr = mp.find("abc");    // キー："abc" を検索
    if( itr != mp.end() ) {      // 見つかった場合
        cout << itr->first << " " << itr->second << "\n";    //  キー、値を表示
    }
    itr = mp.find("xyz");    // キー："xyz" を検索
    if( itr == mp.end() ) {      // 見つからなかった場合
        cout << "not found.\n";
    }

lower_bound(キー) : イテレータ

lower_bound(キー) は、指定されたキー以上のキーを持つ最初のイテレータを返す。それが無い場合は オブジェクト.end() を返す。
例えば、キーとして 1, 3, 3, 5 のノードがある場合、lower_bound(3) を実行すると、最初の3以上の値は2番め3なので、それへのイテレータを返す。
lower_bound(2) を実行した場合も、最初の2以上の値は2番め3なので、それへのイテレータを返す。
lower_bound(6) を実行した場合、6以上の値は無いので、オブジェクト.end() を返す。

    std::multimap<std::string, int> mp;    //  文字列 → 整数 の連想配列
    mp.insert(std::make_pair("abc", 123));
    mp.insert(std::make_pair("d", 456));
    mp.insert(std::make_pair("xy", 789));
    auto itr = lower_bound("abc");    //  ("abc" -> 123) ペアを指すイテレータが返ってくる
    itr = lower_bound("a");       // "abc" ノードへのイテレータが返ってくる
    itr = lower_bound("zzz");    // mp.end() が返ってくる

upper_bound(キー) : イテレータ

upper_bound(キー) は、指定されたキーよりも大きいキーを持つ最初のイテレータを返す。それが無い場合は オブジェクト.end() を返す。
例えば、キーとして 1, 3, 3, 5 のノードがある場合、upper_bound(3) を実行すると、最初の3より大きい値は最後5なので、それへのイテレータを返す。
upper_bound(2) を実行した場合、最初の2より大きい値は2番め3なので、それへのイテレータを返す。
upper_bound(5) を実行した場合、5より大きい値は無いので、オブジェクト.end() を返す。

    std::multimap<std::string, int> mp;    //  文字列 → 整数 の連想配列
    mp.insert(std::make_pair("abc", 123));
    mp.insert(std::make_pair("d", 456));
    mp.insert(std::make_pair("xy", 789));
    auto itr = upper_bound("abc");    //  "d" ノードへのイテレータが返ってくる
    itr = upper_bound("a");       // "abc" ノードへのイテレータが返ってくる
    itr = upper_bound("xy");    // mp.end() が返ってくる

equal_range(キー) : pair<イテレータ, イテレータ>

次章で説明する erase(first, last) 関数などに範囲を渡す場合、lower_bound(キー), upper_bound(キー) を使って範囲を取得するが、 equal_range(キー) を使えば、関数を2回コールせず1回で済む。

    std::multimap<std::string, int> mp;    //  文字列 → 整数 の連想配列
    mp に要素を追加
    auto r = mp.equal_range("xyz");     //  xyz の範囲を取得
    mp.erase(r.first, r.second);              // first, second に範囲が入っている

演習問題

1. キー型：文字列、値型：int の多重マップを生成し、("abc" -> 777), ("abc" -> 1), ("xyz" -> 123), ("abc" -> 999) のペアを挿入し、 "abc", "xyz" それぞれを検索し結果が正しいことを確認しなさい。show

    std::multimap<std::string, int> mp;    //  文字列 → 整数 の連想配列
    mp.insert(std::make_pair("abc", 777));
    mp.insert(std::make_pair("abc", 1));
    mp.insert(std::make_pair("xyz", 123));
    mp.insert(std::make_pair("abc", 999));
    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 == 123 )
        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;

4. 上記多重マップに対し、lower_bound(), upper_bound() を使って "abc" を検索し、キー・値のペアを全て表示しなさい。 show

    auto itr = mp.lower_bound("abc");
    auto last = mp.upper_bound("abc");
    while (itr != last) {
        cout << itr->first << " -> " << itr->second << "\n";
        ++itr;
    }

要素の削除

• erase(キー) : size_t
• erase(イテレータ) : イテレータ
• erase(first, last) : イテレータ

erase(キー) : size_t

erase(キー) で、指定キーの要素を全て削除し、削除したノード数を返す。

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

erase() 内部で、キーのノードを探す手間が必要なので、erase(キー) の処理時間は O(log N) である。

erase(イテレータ) : イテレータ

erase(イテレータ) で、イテレータの指すノードを削除することが出来る。 find() などで、ノード位置を探し、その結果を使って要素を削除できる。

    std::multimap<std::string, int> mp;    //  文字列 → 整数 の連想配列
    mp に要素を追加
    auto itr = mp.find("xyz");
    if( itr != mp.end() ) {
        mp.erase(itr);
    }

erase(イテレータ) の処理時間は O(1) である。

erase(first, last) : イテレータ

erase(first, last) で、イテレータ [first, last) の範囲のノードを削除することが出来る。
削除範囲を示すイテレータは lower_bound(), upper_bound() などで取得する。

指定キーを持つノードを全て削除したい場合は、以下のように記述する。

    std::multimap<std::string, int> mp;    //  文字列 → 整数 の連想配列
    mp に要素を追加
    auto first = mp.lower_bound("xxx");
    auto last = mp.upper_bound("yyy");
    mp.erase(first, last);   //  "xxx" ～ "yyy" の範囲を全削除（"yyy" も削除される）

演習問題

1. キー型：文字列、値型：int の多重マップを生成し、("abc" -> 777), ("abc" -> 1), ("xyz" -> 123), ("abc" -> 999) のペアを挿入し、 erase(キー) を使って、("xyz" -> 123) を削除するコードを書き、動作確認しなさい。show

    std::multimap<std::string, int> mp;    //  文字列 → 整数 の連想配列
    mp.insert(std::make_pair("abc", 777));
    mp.insert(std::make_pair("abc", 1));
    mp.insert(std::make_pair("xyz", 123));
    mp.insert(std::make_pair("abc", 999));
    mp.erase("xyz");

2. キー型：文字列、値型：int の多重マップを生成し、("abc" -> 777), ("abc" -> 1), ("xyz" -> 123), ("abc" -> 999) のペアを挿入し、 検索を行って ("abc" -> 999) だけを削除するコードを書き、動作確認しなさい。show

    std::multimap<std::string, int> mp;    //  文字列 → 整数 の連想配列
    mp.insert(std::make_pair("abc", 777));
    mp.insert(std::make_pair("abc", 1));
    mp.insert(std::make_pair("xyz", 123));
    mp.insert(std::make_pair("abc", 999));
    auto ptr = mp.lower_bound("abc");
    auto last = mp.upper_bound("abc");
    while (ptr != last) {
        if (ptr->second == 999)
            ptr = mp.erase(ptr);
        else
            ++ptr;
    }

その他のメンバ関数

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

• empty() : bool
• size() : size_t

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

    std::multimap<std::string, int> mp;
    if( mp.empty() )
        std::cout << "empty.\n";
    else
        std::cout << "not empty.\n";
    mp.insert(std::make_pair("abc", 123));
    if( mp.empty() )
        std::cout << "empty.\n";
    else
        std::cout << "not empty.\n";

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

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

    std::multimap<std::string, int> mp;
    std::cout << mp.size() << "\n";      // 空なので 0 が表示される
    mp.insert(std::make_pair("abc", 123));
    mp.insert(std::make_pair("xy", 99));
    std::cout << mp.size() << "\n";      // 2 が表示される

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

• clear() : void
• swap(std::multimap &) : void

「clear()」は多重マップを空にする関数。
サイズを0にする。vector とは違い、要素を delete し、メモリが解放される。

    std::multimap<std::string, int> mp;
    std::cout << mp.size() << "\n";      // 空なので 0 が表示される
    mp.insert(std::make_pair("abc", 123));
    mp.insert(std::make_pair("xy", 99));
    std::cout << mp.size() << "\n";      // 2 が表示される
    mp.clear();
    std::cout << mp.size() << "\n";      // 空なので 0 が表示される

x.swap(y) は、集合 x と y の中身を交換する関数だ。

    std::multimap<std::string, int> x, y;
    x, y に要素を適当に追加
    x.swap(y);     // x, y の中身を入れ替え

演習問題

1. empty() の動作確認を行うプログラムを書き、実行してみなさい。show

    std::multimap<std::string, int> mp;
    if( mp.empty() ) {
        std::cout << "OK\n";
    } else {
        std::cout << "NG\n";
    }
    mp.insert(std::make_pair("hoge", 123));
    if( !mp.empty() ) {
        std::cout << "OK\n";
    } else {
        std::cout << "NG\n";
    }

2. size() の動作確認を行うプログラムを書き、実行してみなさい。show

    std::multimap<std::string, int> mp;
    if( st.size() == 0 ) {
        std::cout << "OK\n";
    } else {
        std::cout << "NG\n";
    }
    mp.insert(std::make_pair("hoge", 123));
    mp.insert(std::make_pair("abc", 987));
    mp.insert(std::make_pair("xyzzz", 31415));
    if( mp.size() == 3) {
        std::cout << "OK\n";
    } else {
        std::cout << "NG\n";
    }
    mp.insert(std::make_pair("abc", 457));
    mp.insert(std::make_pair("abc", 654));
    mp.insert(std::make_pair("zzz", 31415));
    if( mp.size() == 6) {
        std::cout << "OK\n";
    } else {
        std::cout << "NG\n";
    }

3. clear() の動作確認を行うプログラムを書き、実行してみなさい。show

    std::multimap<std::string, int> mp;
    mp.insert(std::make_pair("hoge", 123));
    mp.insert(std::make_pair("abc", 987));
    mp.insert(std::make_pair("xyzzz", 31415));
    mp.clear();
    if( mp.empty() && mp.size() == 0 ) {
        std::cout << "OK\n";
    } else {
        std::cout << "NG\n";
    }

4. swap() の動作確認を行うプログラムを書き、実行してみなさい。show

    std::multimap<std::string, int> mp1, mp2;
    mp2.insert(std::make_pair("hoge", 123));
    mp2.insert(std::make_pair("abc", 987));
    mp2.insert(std::make_pair("xyzzz", 31415));
    mp1.swap(mp2);
    if( !mp1.empty() && mp1.size() == 3 &&
        mp2.empty() && mp2.size() == 0)
    {
        std::cout << "OK\n";
    } else {
        std::cout << "NG\n";
    }

まとめ・参考

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

総合演習問題

---

　

最近更新したページ

人気のページ

関連ページ

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