C++の標準テンプレートライブラリ (STL) において、std::set は非常に強力で柔軟なデータ構造の1つです。データを自動的にソートして保持し、重複を許さないという特性は、効率的なアルゴリズムを構築する上で欠かせません。

本記事では、C++プログラミングにおける std::set の基本的な使い方から、近年導入された便利な新機能、さらには実務で役立つ応用テクニックまでを詳しく解説します。

目次 [ close ]
  1. std::set の基礎知識と特徴
    1. std::set の主な特性
  2. 基本的な操作方法
    1. 要素の宣言と初期化
    2. 要素の挿入と削除
  3. 要素の検索と存在確認
    1. find メソッドと count メソッド
    2. モダンC++ (C++20以降) の新機能：contains
  4. カスタム比較関数の定義
    1. 降順ソートの例
    2. 構造体やクラスを要素にする場合
  5. 最新の活用テクニック
    1. ノードの抽出と転送 (extract / merge)
    2. 異種型検索 (Heterogeneous Lookup)
  6. パフォーマンス上の注意点と使い分け
    1. unordered_set との比較
    2. vector との比較
  7. まとめ

std::set の基礎知識と特徴

std::set は、連想コンテナの一種であり、要素そのものがキーとなる特別な構造を持っています。

内部的には通常「赤黒木」などの 自己均衡二分探索木 で実装されており、これにより効率的な操作が可能になっています。

std::set の主な特性

std::set を利用する上で、まず理解しておくべき特徴は以下の3点です。

  1. 重複を許さない：同じ値を持つ要素を複数保持することはできません。
  2. 常にソートされた状態を維持：挿入された要素は、デフォルトでは昇順 (小さい順) に並びます。
  3. 対数時間の計算量：検索、挿入、削除の各操作が O(log N) の時間計算量で行われます。

これらの特性により、大量のデータから特定の要素を素早く見つけ出したり、常にデータの順序を管理したりする必要がある場合に最適です。

一方で、要素の追加ごとにメモリ割り当てが発生するため、連続したメモリ領域を利用する std::vector と比較すると、メモリ使用量やキャッシュ効率の面でデメリットがあることも覚えておく必要があります。

基本的な操作方法

まずは、std::set を使うための基本的な手順を見ていきましょう。

使用するには、ヘッダファイル #include <set> をインクルードする必要があります。

要素の宣言と初期化

std::set の宣言は非常に簡単です。

初期化リストを使用することで、あらかじめ値を設定することも可能です。

C++
#include <iostream>
#include <set>
#include <string>

int main() {
    // 空のセットを宣言
    std::set<int> mySet;

    // 初期化リストを使用した宣言
    std::set<std::string> fruits = {"apple", "banana", "cherry"};

    // 範囲ベースforループによる出力
    for (const auto& fruit : fruits) {
        std::cout << fruit << " ";
    }
    std::cout << std::endl;

    return 0;
}
実行結果
apple banana cherry

要素の挿入と削除

要素の追加には insert() を、削除には erase() を使用します。

C++
#include <iostream>
#include <set>

int main() {
    std::set<int> numbers;

    // 要素の挿入
    numbers.insert(10);
    numbers.insert(5);
    numbers.insert(20);
    // 重複する要素を挿入しようとしても無視される
    numbers.insert(10);

    std::cout << "サイズ: " << numbers.size() << std::endl; // 重複はカウントされない

    // 要素の削除
    numbers.erase(5);

    for (int n : numbers) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}
実行結果
サイズ: 3
10 20

insert() メソッドは、挿入に成功したかどうかを示すイテレータとブール値のペアを返します。

これを利用することで、「既に値が存在していたか」を確認しながら処理を進めることができます。

要素の検索と存在確認

std::set の真骨頂は、その高速な検索性能にあります。

find メソッドと count メソッド

従来、要素の存在を確認するためには find() または count() が使われてきました。

メソッド説明
find(val)要素を指すイテレータを返す。見つからない場合は end() を返す。
count(val)指定した値の個数を返す。set では常に 0 または 1 となる。
C++
#include <iostream>
#include <set>

int main() {
    std::set<int> s = {1, 3, 5, 7};

    // find を使った検索
    auto it = s.find(3);
    if (it != s.end()) {
        std::cout << "3は見つかりました" << std::endl;
    }

    // count を使った存在確認
    if (s.count(10) == 0) {
        std::cout << "10は見つかりませんでした" << std::endl;
    }

    return 0;
}

モダンC++ (C++20以降) の新機能：contains

C++20 からは、より直感的に存在確認ができる contains() メソッド が追加されました。

これにより、コードの可読性が大幅に向上しています。

C++
if (s.contains(5)) {
    std::cout << "5が存在します" << std::endl;
}

今後はこの contains メソッドの使用が推奨されます。

戻り値が bool 型であるため、条件式で非常に扱いやすいのがメリットです。

カスタム比較関数の定義

デフォルトでは昇順にソートされますが、テンプレート引数を指定することで 独自のソート条件を設定することが可能です。

降順ソートの例

std::greater<T> を指定することで、降順のセットを作成できます。

C++
#include <iostream>
#include <set>
#include <functional>

int main() {
    // 降順にソートされるセット
    std::set<int, std::greater<int>> descSet = {10, 50, 20, 40};

    for (int n : descSet) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}
実行結果
50 40 20 10

構造体やクラスを要素にする場合

自作の構造体を要素にする場合、比較演算子 (operator<) をオーバーロードするか、比較用の関数オブジェクトを定義する必要があります。 これを怠ると、コンパイルエラーが発生します。

C++
struct Player {
    int id;
    std::string name;

    // 比較演算子の定義 (ID順に並べる)
    bool operator<(const Player& other) const {
        return id < other.id;
    }
};

std::set<Player> players;

最新の活用テクニック

C++17 以降、std::set には効率的なノード操作や検索のための機能が追加されています。

ノードの抽出と転送 (extract / merge)

C++17 から導入された ノードハンドル を使用すると、要素のコピーコストを発生させずに、あるセットから別のセットへ要素を移動させたり、要素の値を書き換えたりすることができます。

C++
#include <iostream>
#include <set>

int main() {
    std::set<int> setA = {1, 2, 3};
    std::set<int> setB = {10, 20};

    // setA から 2 を抽出
    auto node = setA.extract(2);
    
    // 値を書き換える (通常、setの要素は直接書き換えられないが、ノードなら可能)
    node.value() = 15;

    // setB へ挿入
    setB.insert(std::move(node));

    for (int n : setB) std::cout << n << " "; // 10 15 20
    return 0;
}

このように extract() を利用することで、キーの変更を伴う更新操作を最小限のオーバーヘッドで実現できます。

異種型検索 (Heterogeneous Lookup)

通常、std::set<a href="std::string">std::string</a> に対して文字列リテラルで検索を行うと、一時的な std::string オブジェクトが生成されてしまいます。

C++14 以降、比較オブジェクトに std::less<void> (または透明な比較子) を使用することで、この一時オブジェクトの生成を抑制できる機能が導入されました。

C++
std::set<std::string, std::less<>> fastSearchSet;
fastSearchSet.insert("hello");

// std::string オブジェクトを作らずに検索が可能
if (fastSearchSet.contains("hello")) { ... }

大規模なアプリケーションにおいて、文字列検索の負荷を軽減するために非常に有効な手法です。

パフォーマンス上の注意点と使い分け

std::set は万能ではありません。

用途によっては他のコンテナの方が適している場合があります。

unordered_set との比較

ハッシュテーブルベースの std::unordered_set との使い分けは、C++エンジニアにとって重要な判断基準です。

  • std::set：
    • 常に要素がソートされている必要がある。
    • 範囲検索 (lower_boundなど) を行いたい。
    • 計算量が安定している (O(log N))。
  • std::unordered_set：
    • 順序は問わない。
    • 検索速度を最優先したい (平均 O(1))。

vector との比較

要素数が非常に少ない場合や、一度構築した後に変更しない場合は、std::vector をソートして保持し、std::binary_search を使用するほうが、メモリの連続性によるキャッシュ効率の向上により高速になるケースがあります。

項目std::setstd::vector (ソート済み)
検索計算量O(log N)O(log N)
挿入計算量O(log N)O(N)
メモリ構造ノード分散型連続配列型
キャッシュ効率低い高い

頻繁に挿入と検索を繰り返す場合は std::set、構築後に検索のみを行う場合は std::vector を検討しましょう。

まとめ

std::set は、データの重複を排除しつつ自動的にソートを行う、非常に利便性の高いコンテナです。

本記事では、基本的な insert や erase、find といった操作から、C++20 の contains、C++17 のノード操作といった最新のテクニックまでを解説しました。

計算量が O(log N) であるという数学的な保証と、常に順序が整っているという性質は、多くのアルゴリズム実装において強力な武器となります。

しかし、モダンな C++ 開発においては、単に便利だからという理由で std::set を選ぶのではなく、キャッシュ効率やハッシュテーブル (unordered_set) との比較を行い、要件に応じた最適なコンテナを選択することが求められます。

この記事で紹介した知識を活かし、より効率的で堅牢な C++ プログラムの構築を目指してください。