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 クラステンプレート（これは値に依存しないシンプルなメモリ確保モデルを定義する）が使われる。

メンバ関数

構築・破棄

イテレータ

領域

コンテナの変更

要素アクセス

オブザーバー

メンバ型

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

非メンバ関数

比較演算子

入れ替え

要素削除

推論補助

例

#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