C++ STLのmultiset（マルチセット）とは？重複を許す連想コンテナの使い方を解説

このチュートリアルでは、C++ STL（Standard Template Library）が提供する連想コンテナの一つである multiset について、実際のサンプルプログラムを通して詳しく解説します。

multiset とは

multiset は set と非常によく似た連想コンテナです。両者の最大の違いは、multiset は同じ値を持つ要素（重複値）を複数格納できるという点にあります。set では重複した値を挿入しても無視されますが、multiset ではそのまま保持されます。

また、multiset 内部の要素は常に自動的にソートされて管理されるため、検索や範囲操作を効率的に行うことができます。

multiset の主な特徴

• 重複した値を許容する
• 要素は常にソートされた状態で保持される（デフォルトは昇順）
• 比較関数オブジェクトを指定することで降順など独自の順序に変更可能
• lower_bound / upper_bound による効率的な範囲検索が可能

サンプルコード

#include <iostream>
#include <set>
#include <iterator>
using namespace std;

int main() {
    // 降順でソートする multiset を作成
    multiset<int, greater<int>> gquiz1;

    // 値を挿入（50 は意図的に重複させて挿入）
    gquiz1.insert(40);
    gquiz1.insert(30);
    gquiz1.insert(60);
    gquiz1.insert(20);
    gquiz1.insert(50);
    gquiz1.insert(50);
    gquiz1.insert(10);

    multiset<int, greater<int>>::iterator itr;

    cout << "\nThe multiset gquiz1 is : ";
    for (itr = gquiz1.begin(); itr != gquiz1.end(); ++itr) {
        cout << '\t' << *itr;
    }
    cout << endl;

    // gquiz1 の範囲から昇順の multiset を作成
    multiset<int> gquiz2(gquiz1.begin(), gquiz1.end());

    cout << "\nThe multiset gquiz2 after assign from gquiz1 is : ";
    for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) {
        cout << '\t' << *itr;
    }
    cout << endl;

    // 30 未満の要素をまとめて削除
    cout << "\ngquiz2 after removal of elements less than 30 : ";
    gquiz2.erase(gquiz2.begin(), gquiz2.find(30));
    for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) {
        cout << '\t' << *itr;
    }

    // 値 50 をすべて削除し、削除した個数を受け取る
    int num;
    num = gquiz2.erase(50);
    cout << "\ngquiz2.erase(50) : ";
    cout << num << " removed\t";
    for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) {
        cout << '\t' << *itr;
    }
    cout << endl;

    // lower_bound / upper_bound の動作確認
    cout << "gquiz1.lower_bound(40) : " << *gquiz1.lower_bound(40) << endl;
    cout << "gquiz1.upper_bound(40) : " << *gquiz1.upper_bound(40) << endl;
    cout << "gquiz2.lower_bound(40) : " << *gquiz2.lower_bound(40) << endl;
    cout << "gquiz2.upper_bound(40) : " << *gquiz2.upper_bound(40) << endl;

    return 0;
}

実行結果

The multiset gquiz1 is :      60      50      50      40      30      20      10

The multiset gquiz2 after assign from gquiz1 is :      10      20      30      40      50      50      60

gquiz2 after removal of elements less than 30 :      30      40      50      50      60
gquiz2.erase(50) : 2 removed      30      40      60
gquiz1.lower_bound(40) : 40
gquiz1.upper_bound(40) : 30
gquiz2.lower_bound(40) : 40
gquiz2.upper_bound(40) : 60

コードの解説

1. 降順の multiset を作成する

multiset<int, greater<int>> のように第2テンプレート引数に greater<int> を指定すると、要素が降順にソートされます。何も指定しない場合はデフォルトの less<int> が使われ、昇順になります。

2. 重複値の挿入

値 50 を2回 insert していますが、multiset ではどちらも有効な要素として格納されます。出力結果に「50」が2つ並んでいることで確認できます。

3. 範囲コンストラクタによるコピー

multiset<int> gquiz2(gquiz1.begin(), gquiz1.end()); のようにイテレータの範囲を渡すことで、既存の multiset から新しい multiset を生成できます。ここで gquiz2 はデフォルトの昇順でソートされる点に注意してください。

4. 要素の削除（erase）

erase(first, last) の形式では、指定した範囲の要素を一括削除できます。この例では find(30) の位置までの範囲、つまり 30 未満の要素を削除しています。
一方、erase(50) のように値を直接指定すると、一致するすべての要素が削除され、戻り値として削除した個数が返ります。50 は2つ存在したため「2 removed」と表示されています。

5. lower_bound と upper_bound

• lower_bound(x)：x 以上（降順の場合は x 以下）となる最初の要素へのイテレータを返す
• upper_bound(x)：x より大きい（降順の場合は x より小さい）最初の要素へのイテレータを返す

昇順の gquiz2 では upper_bound(40) が「60」を返しています。これは直前の処理で 50 がすべて削除されているため、40 より大きい最初の要素が 60 になるからです。

まとめ

multiset は「重複を許すソート済みセット」として、出現回数の管理や順序付きデータの保持など、さまざまな場面で活躍します。set との違いである重複の扱いと、erase・lower_bound・upper_bound の基本的な使い方をしっかり押さえておきましょう。