【C++】set・multiset・unordered_set・unordered_multisetの違いを徹底解説

C++には、要素のコレクションを管理するための連想コンテナとして「set」「multiset」「unordered_set」「unordered_multiset」の4種類が用意されています。これらは一見似ていますが、「並び順」「重複の可否」「内部実装」の点で大きく異なります。

この記事では、それぞれの特徴を実際のサンプルコードと出力結果をもとに詳しく解説し、最後に比較表で整理します。

set の特徴

set は最も基本的な集合コンテナで、以下のような性質を持ちます。

• データをソートされた順序(デフォルトは昇順)で格納する
• 重複する値は格納できない(挿入時に自動的に除外される)
• 要素の挿入・削除は可能だが、既存の値を直接書き換えることはできない
• begin イテレータと end イテレータを指定して、範囲をまとめて削除できる
• イテレータを使って先頭から末尾まで走査できる
• 内部的には平衡二分探索木(赤黒木)で実装されており、主要な操作は O(log n)

サンプルコード

#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つにまとめられ、昇順に出力されているのがわかります。

multiset の特徴

multiset は set とほぼ同じですが、次の点が異なります。

• データをソートされた順序で格納する
• 重複したデータの格納を許可する
• begin / end イテレータによる範囲削除が可能

サンプルコード

#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

今度は重複した値がそのまま保持され、すべて昇順に並んで出力されます。

unordered_set の特徴

unordered_set は名前の通り「順序を持たない」集合コンテナです。

• 要素の並び順は不定(ハッシュ値に依存する)
• 重複データは破棄される
• 内部的にはハッシュテーブルで実装されており、平均 O(1) で高速な検索が可能
• erase で削除できるのは、イテレータが現在指している1つの要素のみ

サンプルコード

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

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

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

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

出力結果

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

重複は除去されますが、出力順序は挿入順でもソート順でもなく、ハッシュテーブルの内部構造に依存します。なお、この順序は処理系や実行環境によって変わる可能性があります。

unordered_multiset の特徴

unordered_multiset は unordered_set に重複許可を加えたコンテナです。

• 要素の並び順は不定
• 重複データを許可する
• 内部的にはハッシュテーブルで実装されている
• erase で削除できるのは、イテレータが指す1つの要素のみ

サンプルコード

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

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

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

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

出力結果

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

重複が保持され、かつ順序は不定であることが確認できます。出力は挿入順と一致して見えますが、これはあくまでハッシュ関数の結果によるもので、保証された動作ではありません。

4つのコンテナの比較まとめ

使い分けのポイント

• 常にソートされた状態で要素を扱いたい → set / multiset
• 重複を許したい → multiset / unordered_multiset
• 検索速度を最優先したい → unordered_set / unordered_multiset
• 順序付きで範囲取得(lower_bound など)を行いたい → set 系が有利

このように、4つのコンテナは「ソートの有無 × 重複の可否」の組み合わせで使い分けます。要件に応じて適切なコンテナを選択することが、パフォーマンスと可読性の両面で重要です。