C++ STL入門：setとunordered_setの違いを徹底解説

本記事では、C++ STLにおける set と unordered_set の概要をわかりやすく解説し、両者の違いについても詳しく学んでいきます。

setとは？

set（セット）は、Key型の一意なオブジェクトをソート済みの状態で格納する連想コンテナです。各要素は一度しか出現できず、重複した値は許されません。ユーザーは任意の順序で要素を挿入してsetを作成できますが、setは常にソートされた形でデータを返します。つまり、setにはデータを並べ替えるための仕組みが内部に組み込まれており、その処理はユーザーから抽象化されています。

setを使うべき主なケースは以下の通りです。

• ソート済みのデータが必要な場合
• 重複値が不要で、一意なデータのみを扱いたい場合
• ハッシュテーブルではなく二分探索木（Binary Search Tree）を利用したい場合
• 検索時間が気にならない場合。検索の計算量はO(log n)です。

入力：

set = {2, 1, 5, 6, 9, 3, 2}

出力：

1, 2, 3, 5, 6, 9

ポイント： 値はランダムな順序で挿入されますが、setによって自動的にソートされ、さらに重複した値は削除されます。

サンプルコード

#include <iostream>
#include <set>
using namespace std;
int main(){
    // 配列の作成
    int arr[] = {2, 1, 5, 6, 9, 3, 2};
    int size = sizeof(arr)/ sizeof(arr[0]);
    // setの宣言
    set<int> SET;
    // insert() を使って配列からsetへ要素を挿入
    for(int i = 0; i<size; i++){
        SET.insert(arr[i]);
    }
    set<int>::iterator it;
    cout<<"set内の値: ";
    for(it = SET.begin(); it != SET.end(); it++){
        cout <<*it<<" ";
    }
}

実行結果

上記コードの出力は以下の通りです。

set内の値: 1 2 3 5 6 9

unordered_setとは？

unordered_setは、挿入された順序に関係なく、データを順不同の状態で格納する連想コンテナです。こちらも各要素は一度しか出現できず、重複した値は許されません。ユーザーは任意の順序で要素を挿入してunordered_setを作成できますが、返されるデータの順序は保証されません（つまり、順不同の形式で返されます）。

unordered_setを使うべき主なケースは以下の通りです。

• ソートされたデータが不要で、順不同の形式でデータを扱ってよい場合
• 重複値が不要で、一意なデータのみを扱いたい場合
• 二分探索木ではなくハッシュテーブルを利用したい場合
• より高速な検索が必要な場合。平均計算量はO(1)、最悪の場合はO(n)です。

入力：

set = {2, 1, 5, 6, 9, 3, 2}

出力：

3, 9, 6, 5, 2

サンプルコード

#include <iostream>
#include <unordered_set>
using namespace std;
int main(){
    int arr[] = { 2, 1, 5, 6, 9, 3, 2 };
    int size = sizeof(arr) / sizeof(arr[0]);
    unordered_set<int> U_SET;
    // insert() を使って配列からunordered_setへ要素を挿入
    for(int i = 0; i < size; i++){
        U_SET.insert(arr[i]);
    }
    unordered_set<int>::iterator it;
    cout << "unordered_set内の値: ";
    for(it = U_SET.begin(); it != U_SET.end(); it++){
        cout << *it << " ";
    }
}

実行結果

上記コードの出力は以下の通りです。

unordered_set内の値: 3 6 5 9 2 1

setとunordered_setの比較まとめ

最後に、両者の違いを表形式で整理しておきます。用途に応じて適切なコンテナを選択しましょう。