C++の基礎 - 連想コンテナ

概要

std::setは、ユニークな要素を格納する連想コンテナの一種であり、要素自身がキーとなる。
連想コンテナは、特にそれらキーによる要素アクセスが効率的になるよう設計されたコンテナである。
(要素への相対位置または絶対位置によるアクセスが効率的であるシーケンシャルコンテナとは異なる)

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

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

• ユニークな要素の値

  互いに等しい2つの要素がstd::setに格納されることはない。
  複数の等しい値を許す同様の連想コンテナは、std::multisetを参照すること。

• 要素の値はキーそのものである。

  キーを使用して要素にアクセスする。

  キーとは異なる値へマップする同様の連想コンテナ (連想配列) は、std::mapを参照すること。

• 要素は常に狭義の弱順序に従う。

std::setは、双方向イテレータをサポートする。

値の許可

以下の例では、最初に許可された値のリストをstd::setとして定義している。
このデータ構造を使用する理由は、要素の検索が非常に効率的であるためである。 (検索の時間複雑度は、O(log n))

その後、任意の値がこの連想コンテナに含まれているかどうかを確認するため、findメソッドを使用している。
値が含まれていない場合は、50を代入している。

 #include <set>
 
 // 許可された値のセットを定義
 const std::set<int> allowedValues = {10, 20, 30, 40, 45, 50, 55, 60, 70};
 
 // 任意のint型の変数
 int hoge = 100;
 
 // 任意のint型の変数の値において、許可された値のセットに含まれていない場合は50を代入
 if (allowedValues.find(hoge) == allowedValues.end()) {
    hoge = 50;
 }