C++のsetとmultisetの違いとは?特徴と使い分けを実例付きで解説

C++には、データを効率的に格納・検索するための連想コンテナとして「set」と「multiset」が用意されています。どちらも標準テンプレートライブラリ(STL)に属するコンテナであり、要素への高速なアクセスや挿入を可能にするデータ構造です。

しかし、両者には重複要素の扱いをはじめとする重要な違いがあります。本記事では、setとmultisetの相違点を比較表で整理し、実際のコード例と実行結果を通じて、それぞれの動作の違いをわかりやすく解説します。

setとmultisetの主な違い

両者の最も大きな違いは重複値を許可するかどうかという点です。それ以外の基本的な性質(自動ソート、要素の変更不可など)は共通しています。

サンプルコードで確認するsetの動作

まずはsetの例です。15個の整数(重複あり)を挿入してみます。

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

int main() {
    int data[15] = {11, 55, 22, 66, 33, 22, 11, 44, 77, 88, 66, 99, 66, 23, 41};
    set<int> my_set;

    for (int i = 0; i < 15; i++) {
        my_set.insert(data[i]);
    }

    set<int>::iterator it;
    for (it = my_set.begin(); it != my_set.end(); it++) {
        cout << "Item: " << *it << endl;
    }
}

実行結果

Item: 11
Item: 22
Item: 23
Item: 33
Item: 41
Item: 44
Item: 55
Item: 66
Item: 77
Item: 88
Item: 99

入力データには「11」「22」「66」などの重複が含まれていましたが、出力を見ると各値が1回だけ表示され、昇順に並んでいることがわかります。これがsetの特徴です。重複要素は自動的に排除され、常に整列された状態が保たれます。

サンプルコードで確認するmultisetの動作

次に、まったく同じデータをmultisetに挿入してみます。

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

int main() {
    int data[15] = {11, 55, 22, 66, 33, 22, 11, 44, 77, 88, 66, 99, 66, 23, 41};
    multiset<int> my_set;

    for (int i = 0; i < 15; i++) {
        my_set.insert(data[i]);
    }

    multiset<int>::iterator it;
    for (it = my_set.begin(); it != my_set.end(); it++) {
        cout << "Item: " << *it << endl;
    }
}

実行結果

Item: 11
Item: 11
Item: 22
Item: 22
Item: 23
Item: 33
Item: 41
Item: 44
Item: 55
Item: 66
Item: 66
Item: 66
Item: 77
Item: 88
Item: 99

今度の出力では、「11」「22」「66」などの値が入力データに含まれていた回数だけ繰り返し表示されています。multisetは重複を許可しながら、setと同様に昇順ソートを維持するコンテナだからです。

まとめ:setとmultisetの使い分け

• set:重複のない一意な値の集合を管理したい場合に適しています。存在判定やユニークな要素の列挙に便利です。
• multiset:同じ値が複数回現れる可能性のあるデータを、ソート状態で管理したい場合に適しています。度数分布の管理などにも活用できます。

どちらも内部では平衡二分探索木(赤黒木)によって実装されており、挿入・削除・検索をO(log n)の計算量で行えるという利点があります。用途に応じて適切に使い分けることで、効率的なプログラムを書くことができます。