C++ std::multiset とは

C++ の std::multiset とは順序付けされたデータを複数保持することができる順序付多重集合のコンテナクラスだぞ。
データを順不同に順序付多重集合に追加すると、その値をキーにし自動的にソートして内部に格納してくれるぞ。
つまり、要素が常にソートされた状態の配列のようなものだ。
内部的にはツリーを使用するので、ix 番目の要素を高速に取り出すことは出来ないけどね。
set とは違い、重複するデータを保持することができるぞ。これを「多重」と呼ぶ。

multiset はデータの追加・削除・検索の処理速度が O(log N) と高速だ。
vector に入っているデータを単純に検索すると処理速度は O(N) だが、あらかじめ O(N * log N) の時間をかけてデータをソートし、 lower_bound 等の二分探索を行うと O(log N) となる。
なので、データが動的に追加されないような場合は、vector を用いた方がメモリ効率がよく、速度差も無い。
しかし、ランダム・アクセスが必要なくて、データ追加が動的に何度も行われ、平行して検索するような場合は vector よりも multiset を用いた方がいいぞ。

データ構造

std::multiset のデータ構造の例を下図に示す。通常は赤黒木が用いられる。

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

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

• 各ノードには値が入っていて、左右の子供ノードへのポインタを持つ
• 左の子供の値 ≦ 値 ≦ 右の子供の値 という条件が成立している（multiset は重複を許すので「＜」でなく「≦」）
• ノードの深さは概ね同じで、ツリーはバランスしている

準備：インクルード

multiset は C++標準のライブラリであり、「#include <set>」を記述することで利用可能になる。
※ multiset ではなく set であることに注意

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

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

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

宣言・初期化

単純な宣言

std::multiset オブジェクトを生成するには「std::multiset<型> オブジェクト名;」 と記述する。
オブジェクト名とは、宣言する順序付多重集合を識別するための名前のことだ。変数名と言ってもよい。 multiset はクラスなので、それを実体化したものはオブジェクトまたはインスタンスと呼ばれる。
下記は、int 型の順序付多重集合 st を宣言している例だ。

    std::multiset<int> st;  //  int 型の順序付多重集合 st の宣言

型はたいてい何でも指定可能なのだが、multiset は順序付多重集合なので、大小比較が可能であることが必須である。つまり operator<() が定義済みでないといけない。 int などのPODや string はデフォルトで大小比較可能であるが、vector や自分で定義した型は大小比較が出来ないかもしれない。
そのような型を順序付多重集合に格納するには、operator<() を自分で定義するといいぞ。

struct Person {
    stringm_name;
    int    m_height;
};
// 比較演算子の定義
bool operator<(const Person &lhs, const Person &rhs)
{
    return lhs.m_name < rhs.m_name;
}
std::multiset<Person> st;       // 比較演算子を定義しておけばOK

データを指定して初期化

C++11 以上であれば初期化リストを利用して、要素の初期化が可能。

    std::multiset<int> st{3, 1, 4};

上記の様に記述すると、3, 1, 4 が要素として格納される。multiset は順序付多重集合なので、格納されるときに自動的にソートされ、内部では {1, 3, 4} の順序となる。

    std::multiset<int> st{3, 1, 4, 1};

multiset は重複を許す順序付多重集合なので、上記のように重複データがある場合は、重複データは削除されず、{1, 1, 3, 4} が格納される。
ちなみに、重複を許さない順序付多重集合 set であれば {1, 3, 4} が格納される。

コピーコンストラクタ

コピーコンストラクタとは、同じ型のオブジェクトを渡され、それと同じ内容のオブジェクトを生成するコンストラクタのことである。
「std::multiset<型> オブジェクト名(コピー元オブジェクト名);」と記述する。
当然ながら、コピー元オブジェクトと生成するオブジェクトは通常同じ型である。

    std::multiset<int> org{3, 1, 4, 1};
    std::multiset<int> x(org);      // コピーコンストラクタ

上記のコードは org をコピーするので {1, 1, 3, 4} という値をもつ動的配列 x を生成する。

演習問題：

1. int 型の順序付多重集合を {3, 1, 4, 1} で初期化するコードを書き、ビルド、デバッガで実行し、中身を確認しなさい。 show

    std::multiset<int> st{3, 1, 4, 1};

2. コピーコンストラクタの例をビルドし、デバッガで実行して正しくコピーされていることを確認しなさい。
3. struct Person { string m_name; int m_height; }; を順序付多重集合に格納できるよう、名前のみで順序を決める比較関数を定義しなさい。 show

struct Person { string m_name; int m_height; };
bool operator<(const Person &lhs, const Person &rhs)
{
    return lhs.m_name < rhs.m_name;
}
std::multiset<Preson> st;

まとめ

• std::multiset<型> 変数名; で、型の順序付多重集合を生成できるぞ
• 型は < 演算子が定義されていないとだめだぞ
• std::multiset<型> 変数名{値, 値, ... 値}; で、順序付多重集合を初期化できるぞ
• std::multiset<型> x(org); で、順序付多重集合をコピーできるぞ

値の参照

multiset の内部構造は配列ではなく、二分木になっているので、[] 演算子（operator[](size_t)）で、指定番目の要素を取り出すことは出来ない。
したがって、イテレータ を使って各要素にアクセスする必要がある。

イテレータとは抽象化されたポインタのことだ。begin() で最初の要素への、end() で最後の要素の次へのイテレータを取得することが出来る。

    std::multiset<int> st{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    auto itr = st.begin();       // 最初の要素へのイテレータを取得
    std::cout << *itr << "\n";      // イテレータの指す先のデータを表示

イテレータの型は std::multiset<型>::iterator であるが、タイプが大変なので、通常は上記のように auto を使用する。
multiset のイテレータはランダム・アクセス不可で、前後にのみ移動出来る。
ix 番目の要素に無理やりアクセスしたい場合は、begin() で取ってきたイテレータを ix 回インクリメントする。

    auto itr = st.begin();
    for(int i = 0; i < ix; ++i)
        ++itr;

*itr で、イテレータの指す先の要素の値を取得できる。

全ての要素を表示するときは、以下のように記述する。イテレータのお決まりの書き方だ。

    std::multiset<int> st{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    for(auto itr = st.begin(); itr != st.end(); ++itr) {
        std::cout << *itr << "\n";      // イテレータの指す先のデータを表示
    }

通常、非const なイテレータは *itr = 値; で、イテレータが指す先の要素の値を上書きすることができるが、 VC++ では 非const なイテレータでも中身の上書きは不可のようだ。

    std::multiset<int> st{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    std::multiset<int>::iterator itr = st.begin();       // 最初の要素へのイテレータを取得
    *itr = 123;    //  コンパイルエラーとなる

演習問題：

1. int 型、順序付多重集合を、{8, 4, 1, 4} で初期化し、最初の要素を表示してみなさい。show

    std::multiset<int> st{8, 4, 1, 4};
    auto itr = st.begin();
    std::cout << *itr << "\n";

2. int 型、順序付多重集合を、{8, 4, 1, 4} で初期化し、最後の要素を表示してみなさい。show

    std::multiset<int> st{8, 4, 1, 4};
    auto itr = st.end();
    --itr;
    std::cout << *itr << "\n";

3. int 型、順序付多重集合を、{8, 4, 1, 4} で初期化し、最初から最後まで、全ての要素を表示してみなさい。 show

    std::multiset<int> st{8, 4, 1, 4};
    for(auto itr = st.begin(); itr != st.end(); ++itr {
        std::cout << *itr << "\n";
    }

まとめ

• 順序付多重集合要素の値を参照するときは、イテレータを作り、それ経由で参照する
• イテレータ経由で値を書き換えることはできない

データの追加

• insert(値) : iterator

insert(値) : iterator

順序付多重集合にデータを追加するときは insert(値) を使用する。
値は、ソートされた位置に挿入される。
なので、最初・最後に挿入する push_front(値)・push_back(値) は無い。挿入する位置を指定するのは無意味だからだ。

    std::multiset<int> st{3, 1, 4};
    st.insert(2);   //  値 2 を追加

multiset は重複を許すので、既に格納されているデータと同じものを追加することも出来る。

    std::multiset<int> st{3, 1, 4};
    st.insert(3);   //  重複してても、値 3 が追加される

insert(値) は挿入された要素へのイテレータを返す。set と違い、要素は必ず挿入されるので、挿入されたかどうかの情報は返ってこない。

データ追加の処理速度は O(log N) である。

演習問題：

1. int 型の順序付多重集合 st を作り、そこに [0, 10000) の範囲のランダムな要素を1万回格納しなさい。 デバッガで１万個の要素が格納されていることを確認しなさい。show

    const int N = 10000;
    const int RAND_UPPER = 10000;       // 乱数値上限
    multiset<int> st;
    for (int i = 0; i < N; ++i) {
        st.insert(rand() % RAND_UPPER);       // [0, 9999]
    }

2. 上記の処理速度を計測しなさい。同じことを10万回、100万回行った場合の処理速度も計測してみなさい。show

#include <iostream>
#include <set>
#include <chrono>
void measure(int N)
{
    std::cout << N << ":";
    const int RAND_UPPER = 10000;       // 乱数値上限
    multiset<int> st;
    auto start = std::chrono::system_clock::now();      // 計測スタート時刻を保存
    for (int i = 0; i < N; ++i) {
        st.insert(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);
    return 0;
}

まとめ

• insert(値) で指定値を順序付多重集合に追加できるぞ
• 上記は pair<iterator, bool> を返す。２番めの値は、実際に値を追加したかどうかだ
• multiset は重複を許すので、同じ値を何個も追加することが出来るぞ

データの削除

1. erase(値) : size_t
2. erase(イテレータ) : iterator
3. erase(first, last) : iterator

erase(値) : size_t

erase(値) で値が格納されていれば、それを全て削除する。リターン値として削除したデータの個数を返す。 格納されていない値を指定した場合は 0 を返す。

    std::multiset<int> st{3, 1, 4, 3};
    auto c = st.erase(3);      //  3 を削除、2 が返ってくる
    c = st.erase(3);      // 再度 3 を削除、既に削除済みなので 0 が返ってくる

削除処理に要する時間は O(log N) である。

erase(イテレータ) : iterator

引数にイテレータを指定することも出来る。リターン値として、削除した要素の次の要素へのイテレータを返す。

以下は、偶数の要素を全て削除する例。

    multiset<int> st{1, 2, 3, 4, 5, 6};
    for(auto itr = st.begin(); itr != st.end();) {
        if( *itr % 2 == 0 )      // 偶数ならば
            itr = st.erase(itr);       //  削除
        else
            ++itr;
    }

イテレータを指定した場合は、削除処理に要する時間は O(1) である。

erase(first, last) : iterator

削除範囲を指定することも出来る。erase(first, last) を実行すると [first, last) の範囲を削除する。first, last はイテレータだ。

次章に出てくる lower_bound(), upper_bound() を使うと、ある値からある値までの要素を一度に削除することも出来る。

演習問題：

1. int 型の順序付多重集合を {3, 1, 4, 5, 3, 4} で初期化し、要素 3 を削除するコードを書き、動作確認しなさい。show

    std::multiset<int> st{3, 1, 4, 5, 3, 4};
    st.erase(3);

2. int 型の順序付多重集合を {1, 3, 4, 1} で初期化し、最初の要素だけを削除するコードを書き、動作確認しなさい。show

    std::multiset<int> st{1, 3, 4, 1};
    st.erase(st.begin());

まとめ

• erase(値) で、順序付多重集合に格納されている値を削除できるぞ
• erase(イテレータ) で、イテレータが指す要素を削除できるぞ

データの検索

1. find(値) : iterator
2. lower_bound(値) : iterator
3. upper_bound(値) : iterator
4. count(値) : size_t

find(値) : iterator

find(値) は、引数で指定された値を検索し、それへのイテレータを返す。
値が順序付多重集合に含まれない場合は end() を返す。

    multiset<int> st{3, 1, 4, 1, 5};
    auto itr = st.find(4);       //  4 を検索、4 へのイテレータが返ってくる
    auto itr2 = st.find(9);      // 9 を検索、end() が返ってくる

処理時間は O(log N) である。

lower_bound(値) : iterator

lower_bound(値) は、引数で指定された値を検索し、値以上の最初の要素へのイテレータを返す。
値以上の要素が順序付多重集合に含まれない場合は end() を返す。

{1, 2, 2, 3} に対して、lower_bound(2) をコールすると、最初の 2 へのイテレータが返ってくる。
{1, 2, 2, 4} に対して、lower_bound(3) をコールすると、4 へのイテレータが返ってくる。

    multiset<int> st{1, 2, 2, 4, 5, 8};
    auto itr = st.lower_bound(2);   // 2以上の最初の要素へのイテレータを返す
    auto itr2 = st.lower_bound(3);     // 3以上の最初の要素；4 へのイテレータを返す

処理時間は O(log N) である。

upper_bound(値) : iterator

upper_bound(値) は、引数で指定された値を検索し、指定値より大きい最初の要素へのイテレータを返す。
指定値より大きい要素が順序付多重集合に含まれない場合は end() を返す。

{1, 2, 2, 3} に対して、upper_bound(2) をコールすると、3 へのイテレータが返ってくる。
{1, 2, 2, 4} に対して、upper_bound(3) をコールすると、4 へのイテレータが返ってくる。

処理時間は O(log N) である。

    multiset<int> st{1, 2, 2, 4, 5, 8};
    auto itr = st.upper_bound(2);   // 2より大きい最初の要素； 4へのイテレータを返す
    auto itr2 = st.upper_bound(3);     // 3 より大きい最初の要素；4 へのイテレータを返す

count(値) : size_t

count(値) は、順序付多重集合に含まれる指定値の数を返す。
処理時間は O(log N) である。

    multiset<int> st{1, 2, 2, 4, 4, 8};
    st.count(4);       // 4 の個数；2 を返す
    st.count(5);       // 5 の個数；0 を返す

演習問題：

1. int 型の順序付多重集合を {3, 1, 4, 5} で初期化し、要素 4 を検索するコードを書き、正しく検索されていることを確認しなさい。 show

    std::multiset<int> st{3, 1, 4, 5};
    auto itr = st.find(4);
    if( itr != st.end() && *itr == 4 ) {
        std::cout << "OK\n";
    } else {
        std::cout << "NG\n";
    }

2. int 型の順序付多重集合を {3, 1, 4, 5} で初期化し、要素 9 を検索するコードを書き、検索結果が正しいことを確認しなさい。 show

    std::multiset<int> st{3, 1, 4, 5};
    auto itr = st.find(9);
    if( itr == st.end() ) {
        std::cout << "OK\n";
    } else {
        std::cout << "NG\n";
    }

3. int 型の順序付多重集合を {3, 1, 4, 3} で初期化し、検索により、最初の要素3を削除するコードを書き、動作確認しなさい。 show

    std::multiset<int> st{3, 1, 4, 3};
    auto itr = st.lower_bound(3);       // 最初の要素3の位置
    if( itr != st.end() )      //  要素3が無い場合 lower_bound() は end() を返す
        st.erase(itr);

4. int 型の順序付多重集合を {3, 1, 4, 5, 3, 6} で初期化し、要素 3, 4, 5 を一度に削除するコードを書き、動作確認しなさい。 show

    std::multiset<int> st{3, 1, 4, 5, 3, 6};
    auto first = st.lower_bound(3);    //  削除先頭位置
    auto last = st.upper_bound(5);    //  削除末尾位置
    st.erase(first, last);

5. int 型の順序付多重集合を {3, 1, 4, 5, 4} で初期化し、値が 4 の要素数を表示するコードを書き、動作確認しなさい show

    std::multiset<int> st{3, 1, 4, 5, 4};
    cout << "count(4) = " << st.count(4) << "\n";

6. int 型の順序付多重集合を {3, 1, 4, 5} で初期化し、値が 7 の要素数を表示するコードを書き、動作確認しなさい show

    std::multiset<int> st{3, 1, 4, 5};
    cout << "count(7) = " << st.count(7) << "\n";

まとめ

• find(値) で値を検索できるぞ。
• lower_bound（値）、upper_bound(値) で値の範囲を取得できるぞ
• count(値) は順序付多重集合に含まれる指定値の個数を返すぞ

その他のメンバ関数

順序付多重集合の状態を取得

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

empty() : bool

empty() は順序付多重集合が空かどうかを返すメンバ関数だ。

    std::multiset<int> st;
    if( st.empty() ) {
        cout << "empty.\n";
    } else {
        cout << "Not empty.\n";
    }
    st.insert(5);     //  5 を追加
    if( st.empty() ) {
        cout << "empty.\n";
    } else {
        cout << "Not empty.\n";
    }

size() : size_t

size() は順序付多重集合に格納されている要素の数を返す。

下記コードを実行すると、3 と 5 が表示される。

    std::multiset<int> st{3, 1, 4};
    cout << st.size() << "\n";
    std::multiset<int> st2{3, 1, 4, 1, 5};
    cout << st2.size() << "\n";

multiset の状態を変更

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

clear() : void

clear() は要素を全て削除し、順序付多重集合を空にします。

    std::multiset<int> st{3, 1, 4};      // 要素数3の順序付多重集合を生成
    cout << st.size() << "\n";      // 要素数を表示
    st.clear();      // 要素を全て削除
    cout << st.size() << "\n";      // 要素数を表示

swap(std::multiset&) : void

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

    std::multiset<int> x{3, 1, 4, 1, 5}
    std::multiset<int> y{9, 8};
    x.swap(y);     // x, y の中身を入れ替え

イテレータ

• begin() : iterator
• end() : iterator

begin() : iterator, end() : iterator

begin() は最初の要素への、end() は最後の要素の次へのイテレータを返す。

既に何度も出てきているが、下記は全ての要素を表示するコードである。

    std::multiset<int> st{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    for(auto itr = st.begin(); itr != st.end(); ++itr) {
        std::cout << *itr << "\n";      // イテレータの指す先のデータを表示
    }

演習問題：

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

    std::multiset<int> st;
    if( st.empty() ) {
        std::cout << "OK\n";
    } else {
        std::cout << "NG\n";
    }
    std::multiset<int> st2{ 3, 1, 4};
    if( !st2.empty() ) {
        std::cout << "OK\n";
    } else {
        std::cout << "NG\n";
    }

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

    std::multiset<int> st;
    if( st.size() == 0 ) {
        std::cout << "OK\n";
    } else {
        std::cout << "NG\n";
    }
    std::multiset<int> st2{ 3, 1, 4};
    if( st2.size() == 3) {
        std::cout << "OK\n";
    } else {
        std::cout << "NG\n";
    }
    std::multiset<int> st3{ 3, 1, 4, 3, 1, 4};
    if( st3.size() == 6) {
        std::cout << "OK\n";
    } else {
        std::cout << "NG\n";
    }

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

    std::multiset<int> st{3, 1, 4};
    st.clear();
    if( st.empty() && st.size() == 0 ) {
        std::cout << "OK\n";
    } else {
        std::cout << "NG\n";
    }

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

    std::multiset<int> st1, st2{3, 1, 4};
    st1.swap(st2);
    if( !st1.empty() && st1.size() == 3 &&
        st2.empty() && st2.size() == 0)
    {
        std::cout << "OK\n";
    } else {
        std::cout << "NG\n";
    }

まとめ：

• empty() : bool で多重集合が空かどうか判定可能だぞ
• size() : size_t で、多重集合に含まれる要素数を取得できるぞ
• clear() で、多重集合に含まれる要素を全て削除し、多重集合を空にすることが出来るぞ
• x.swap(y) で、x と y の中身を交換出来るぞ
• begin()、end() で最初、最後の次へのイテレータを取得出来るぞ
• multiset::iterator はイテレータが指す先の値を取れるだけで、書き換えは出来ないぞ

まとめ・参考

順序付多重集合 std::multiset は格納された要素を自動的にソートしてくれるコンテナクラスだぞ。
std::set と違い、要素の重複が可能だぞ。
ランダム・アクセスは出来ないが、値をキーにした検索は O(log N) と高速だ。
要素の追加・削除も O(log N) と高速だ。

要素の追加を頻繁に行い、ランダム・アクセスが必要でなければ std::multiset はお薦めだ。
そうでなければ、std::vector を使い、要素をソートしておくという選択肢もあるぞ。

本稿では std::multiset のすべての機能・詳細を解説していない。詳しくは以下のサイトなどで勉強して欲しい。
参照：http://www.cplusplus.com/reference/multiset/multiset/

総合演習問題

1. 多重集合を {3, 1, 2, 2, 2} で初期化し、多重集合に含まれる要素2を全て表示しなさい（tana氏出題）。 show

    multiset<int> st{3, 1, 2, 2, 2};
    auto first = st.lower_bound(2);
    auto last = st.upper_bound(2);
    while( first != last ) {
        cout << *first++ << "\n";
    }

2. 名前、身長、体重をメンバ変数に持つ構造体 strcut Person { string m_name; double m_height; double m_weight; }; があるとき、 名前をキーにした Person を要素にもつ多重集合を宣言し、{"human-1", 170, 65}, {"human-2", 180, 70},

---

　

最近更新したページ

人気のページ

関連ページ

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