最終更新日時: 2025年07月12日 02時16分44秒 (JST)
Koichi Murase が更新

履歴 編集

class template
<set>

# std::set

    namespace std {
      template <class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
      class set;

      namespace pmr {
        template <class Key, class Compare = less<Key>>
          using set = std::set<Key, Compare,
                               polymorphic_allocator<Key>>;  // C++17から
      }
    }

## 概要

`set` はユニークな要素を格納する連想コンテナの一種であり、要素自身がキーとなる、集合を表すクラスである。

連想コンテナは特にそれらキーによる要素アクセスが効率的になるよう設計されたコンテナである（要素への相対位置または絶対位置によるアクセスが効率的であるシーケンシャルコンテナとは異なる）。

内部的には、`set` 内の要素は、コンテナの構築時に設定された狭義の弱順序基準に従って小さいものから大きいものへとソートされる。

`set` は一般的に、二分木として実装される。従って、連想コンテナである `set` の主な特性は以下の通りである。

- ユニークな要素の値：互いに等しい二つの要素が `set` に格納されることは無い。複数の等しい値を許す同様の連想コンテナは `multiset` を参照のこと。
- 要素の値はキーそのものである。キーを使って要素にアクセスするがキーとは異なる値へマップする同様の連想コンテナは `map` を参照のこと。
- 要素は常に狭義の弱順序に従う。

このコンテナクラスは、双方向イテレータをサポートする。

## テンプレートパラメータ

- `Key`: キーの型。このコンテナに格納されれる要素の型。`set` に格納される要素はそれぞれはキーでもある。
- `Compare`: 比較クラス。このクラスは 2 つの引数（同じ型であり、コンテナの要素型でもある）をとり `bool` 値を返す。狭義の弱順序において `a` が `b` よりも前の場所に位置づけられる場合に `true` である。これはクラスが関数呼び出しオブジェクトを実装したクラスであっても良いし関数ポインタであっても良い（例は コンストラクタ を参照）。これは、`operator<()` を適用( `a < b` )したときと同じ値を返す `less<Key>` がデフォルトである。
- `Allocator`: ストレージアロケーションモデルを決定づける、アロケータオブジェクトの型である。デフォルトでは、`Key` への `allocator` クラステンプレート（これは値に依存しないシンプルなメモリ確保モデルを定義する）が使われる。

## メンバ関数

### 構築・破棄

名前 | 説明 | 対応バージョン
--- | --- | ---
`(constructor)` | コンストラクタ |
`(destructor)` | デストラクタ |
`operator=` | 代入演算子 |
`get_allocator` | アロケータオブジェクトを取得する |

### イテレータ

名前 | 説明 | 対応バージョン
--- | --- | ---
`begin` | 先頭を指すイテレータを取得する |
`cbegin` | 先頭を指す読み取り専用イテレータを取得する | C++11
`end` | 末尾の次を指すイテレータを取得する |
`cend` | 末尾の次を指す読み取り専用イテレータを取得する | C++11
`rbegin` | 末尾を指す逆イテレータを取得する |
`crbegin` | 末尾を指す読み取り専用逆イテレータを取得する | C++11
`rend` | 先頭の前を指す逆イテレータを取得する |
`crend` | 先頭の前を指す読み取り専用逆イテレータを取得する | C++11

### 領域

名前 | 説明 | 対応バージョン
--- | --- | ---
`empty` | コンテナが空であるかどうかを調べる |
`size` | 要素数を取得する |
`max_size` | 格納可能な最大の要素数を取得する |

### コンテナの変更

名前 | 説明 | 対応バージョン
--- | --- | ---
`clear` | 全ての要素を削除する |
`insert` | 要素を挿入する |
`insert_range` | Rangeの要素を挿入する | C++23
`emplace` | 要素を直接構築する | C++11
`emplace_hint` | ヒントを使って要素を直接構築する | C++11
`erase` | 要素を削除する |
`swap` | コンテンツを交換する |
`extract` | ノードハンドルを取得する | C++17
`merge` | 他のオブジェクトの要素をマージする | C++17

### 要素アクセス

名前 | 説明 | 対応バージョン
--- | --- | ---
`count` | 指定したキーにマッチする要素の数を返す |
`find` | 指定したキーで要素を探す |
`contains` | 指定したキーの要素が含まれているかを判定する | C++20
`equal_range` | 指定したキーにマッチする要素範囲を返す |
`lower_bound` | 与えられた値より小さくない最初の要素へのイテレータを返す |
`upper_bound` | 特定の値よりも大きい最初の要素へのイテレータを返す |

### オブザーバー

名前 | 説明 | 対応バージョン
--- | --- | ---
`key_comp` | キーを比較した結果を返す |
`value_comp` | 値を比較した結果を返す |

## メンバ型

名前 | 説明 | 対応バージョン
--- | --- | ---
`key_type` | キーの型。テンプレートパラメータ `Key`。 |
`value_type` | 要素の型。テンプレートパラメータ `Key`。 |
`key_compare` | キーの大小関係を判定する二項述語の型。テンプレートパラメータ `Compare`。 |
`value_compare` | 要素の大小関係を判定する二項述語の型。テンプレートパラメータ `Compare`。 |
`allocator_type` | アロケータの型。テンプレートパラメータ `Allocator`。 |
`reference` | 要素`value_type`への参照型。`value_type&`。 |
`const_reference` | 要素`value_type`への`const`参照型。`const value_type&`。 |
`iterator` | "読み取り専用"双方向イテレータ。 `const_iterator` と同じ型か否かは実装依存である。 従って、ODR（One Definition Rule）に違反しないようにするため、関数のパラメータ型には常に `const_iterator` を使用したほうが良いだろう。 |
`const_iterator` | 読み取り専用双方向イテレータ。 |
`size_type` | 要素数を表す符号なし整数型。`difference_type` で表現可能な非負整数（0以上の整数）を表すことが可能。(通常は `size_t`) |
`difference_type` | 同一のコンテナを指す `iterator` の差を表す符号付き整数型(通常は `ptrdiff_t`) `std::iterator_traits<iterator>::difference_type`、および、`std::iterator_traits<const_iterator>::difference_type` と同じ。 |
`pointer` | 要素 `value_type`へのポインタ。 C++03 : `typename Allocator::pointer`。 C++11以降 : `typename allocator_traits<Allocator>::pointer`。 |
`const_pointer` | 要素 `value_type`への`const`ポインタ。 C++03 : `typename Allocator::const_pointer`。 C++11以降 : `typename allocator_traits<Allocator>::const_pointer`。 |
`reverse_iterator` | 逆順双方向イテレータ。`std::reverse_iterator<iterator>`。 |
`const_reverse_iterator` | 読み取り専用逆順双方向イテレータ。`std::reverse_iterator<const_iterator>`。 |
`node_type` | `node_handle`クラステンプレートの特殊化。 | C++17
`insert_return_type` | ノードを挿入した結果を記述するために使用されるクラス型。以下に示す`insert-return-type`テンプレートの特殊化である。ただし、これは説明用のクラスであり、実装定義である。 | C++17

    template <class Iterator, class NodeType>
    struct insert-return-type {
      Iterator position;
      bool inserted;
      NodeType node;
    };

## 非メンバ関数

### 比較演算子

名前 | 説明 | 対応バージョン
--- | --- | ---
`operator==` | 左辺と右辺が等しいかの判定を行う |
`operator!=` | 左辺と右辺が等しくないかの判定を行う |
`operator<=>` | 三方比較を行う | C++20
`operator<` | 左辺が右辺より小さいかの判定を行う |
`operator<=` | 左辺が右辺より小さいか等しいかの判定を行う |
`operator>` | 左辺が右辺より大きいかの判定を行う |
`operator>=` | 左辺が右辺より大きいか等しいかの判定を行う |

### 入れ替え

名前 | 説明 | 対応バージョン
--- | --- | ---
`swap` | 2つの`set`オブジェクトを入れ替える |

### 要素削除

名前 | 説明 | 対応バージョン
--- | --- | ---
`erase_if` | 指定した条件に合致する要素とその分の領域を、コンテナから削除する | C++20

## 推論補助

名前 | 説明 | 対応バージョン
--- | --- | ---
`(deduction_guide)` | クラステンプレートの推論補助 | C++17

## 例

    #include <iostream>
    #include <set>

    int main()
    {
      // intをキーとして扱う集合
      std::set<int> s;

      // 挿入
      s.insert(3);
      s.insert(1);
      s.insert(4);

      // 検索 : キー(int)を指定し、対応する値を得る
      decltype(s)::iterator it = s.find(1);
      if (it != s.end()) {
        // 発見した
        int value = *it;
        std::cout << value << std::endl;
      }
      else {
        std::cout << "not found" << std::endl;
      }
    }

### 出力

    1