セットは連想コンテナの一種であり、各要素は要素の値によって識別されるため、一意である必要があります。値は特定の並べ替え順序、つまり昇順または降順で保存されます。
の std::set クラスは C++ 標準テンプレート ライブラリ (STL) の一部であり、 ヘッダファイル。
構文：
Javaでリストを並べ替える
std::set set_name;>
データ・タイプ： Set は、値に応じて任意のデータ型を取ることができます。 int、char、float など。
例：
set val; // defining an empty set set val = {6, 10, 5, 1}; // defining a set with values> プログラム：
C++
// C++ Program to Demonstrate> // the basic working of STL> #include> #include> int> main()> {> >std::set<>char>>a;>> >a.insert(>'G'>);> >a.insert(>'F'>);> >a.insert(>'G'>);> >for> (>auto>& str : a) {> >std::cout << str <<>' '>;> >}> >std::cout <<>'
'>;> >return> 0;> }> |
>
米国の州
>出力
F G>
時間計算量: O(N) // N はセットのサイズです。
補助スペース: の上）
F と G だけを出力したのは、set が複数の同じ値を取らず、一意の値のみを受け入れるためです。使用できます マルチセット 複数の同じ値を保存したい場合。
降順でソートされたセット
デフォルトでは、std::set は昇順にソートされます。ただし、次の構文を使用して並べ替え順序を変更するオプションがあります。
std::set set_name;>
例：
C++
// C++ program to demonstrate the creation of descending> // order set container> #include> #include> using> namespace> std;> int> main()> {> >set<>int>, greater<>int>>> s1;>> >s1.insert(10);> >s1.insert(5);> >s1.insert(12);> >s1.insert(4);> >for> (>auto> i : s1) {> >cout << i <<>' '>;> >}> >return> 0;> }> |
>
>出力
12 10 5 4>
時間計算量: O(N) // N はセットのサイズです。
補助スペース: の上）
注記： セットにカスタム順序の並べ替えを与えるために、greater の代わりに任意のコンパレータを使用できます。
プロパティ
- 保存順序 – セットには要素が格納されます。 並べ替えられた 注文。
- 価値観の特徴 – セット内のすべての要素には、 固有の値 。
- 自然を大切にする – 要素をセットに追加すると、要素の値を変更することはできません。ただし、その要素の変更された値を削除してから追加することは可能です。したがって、値は は 不変 。
- 検索テクニック – セットは次のとおりです 二分探索木 実装。
- 順番を並べる – セット内の値は次のとおりです。 インデックスなし 。
注記： 要素をソートされていない（ランダムな）順序で保存するには、 unowned_set() に使える。
Javaでオーバーライドする方法
Set に関連するいくつかの基本関数
- 始める（） – セット内の最初の要素に反復子を返します。
- 終わり（） – セット内の最後の要素に続く理論上の要素への反復子を返します。
- サイズ（） – セット内の要素の数を返します。
- max_size() – セットが保持できる要素の最大数を返します。
- 空の（） – セットが空かどうかを返します。
セットに対してさまざまな操作を実行する場合の時間計算量は次のとおりです。
- 要素の挿入 – O(log N)
- 要素の削除 – O(log N)
CPP
// C++ program to demonstrate various functions of> // STL> #include> #include> #include> using> namespace> std;> int> main()> {> >// empty set container> >set<>int>, greater<>int>>> s1;>> >// insert elements in random order> >s1.insert(40);> >s1.insert(30);> >s1.insert(60);> >s1.insert(20);> >s1.insert(50);> >// only one 50 will be added to the set> >s1.insert(50);> >s1.insert(10);> >// printing set s1> >set<>int>, greater<>int>>>::反復子 itr;>> >cout <<>'
The set s1 is :
'>;> >for> (itr = s1.begin(); itr != s1.end(); itr++) {> >cout << *itr <<>' '>;> >}> >cout << endl;> >// assigning the elements from s1 to s2> >set<>int>>s2(s1.begin(), s1.end());>>' >cout <<>'
The set s2 after assign from s1 is :
'>;> >for> (itr = s2.begin(); itr != s2.end(); itr++) {> >cout << *itr <<>' '>;> >}> >cout << endl;> >// remove all elements up to 30 in s2> >cout <<>'
s2 after removal of elements less than 30 '> >':
'>;> >s2.erase(s2.begin(), s2.find(30));> >for> (itr = s2.begin(); itr != s2.end(); itr++) {> >cout << *itr <<>' '>;> >}> >// remove element with value 50 in s2> >int> num;> >num = s2.erase(50);> >cout <<>'
s2.erase(50) : '>;> >cout << num <<>' removed
'>;> >for> (itr = s2.begin(); itr != s2.end(); itr++) {> >cout << *itr <<>' '>;> >}> >cout << endl;> >// lower bound and upper bound for set s1> >cout <<>'s1.lower_bound(40) : '> ><< *s1.lower_bound(40) << endl;> >cout <<>'s1.upper_bound(40) : '> ><< *s1.upper_bound(40) << endl;> >// lower bound and upper bound for set s2> >cout <<>'s2.lower_bound(40) : '> ><< *s2.lower_bound(40) << endl;> >cout <<>'s2.upper_bound(40) : '> ><< *s2.upper_bound(40) << endl;> >return> 0;> }> |
>
>
npmクリアキャッシュ出力
The set s1 is : 60 50 40 30 20 10 The set s2 after assign from s1 is : 10 20 30 40 50 60 s2 after removal of elements less than 30 : 30 40 50 60 s2.erase(50) : 1 removed 30 40 60 s1.lower_bound(40) : 40 s1.upper_bound(40) : 30 s2.lower_bound(40) : 40 s2.upper_bound(40) : 60>
C++ STL の Set の別の関数
| 関数 | 説明 |
|---|---|
| 始める（） | セット内の最初の要素への反復子を返します。 |
| 終わり（） | セット内の最後の要素に続く理論上の要素への反復子を返します。 |
| rbegin() | コンテナ内の最後の要素を指す逆反復子を返します。 |
| 与える（） | セットコンテナ内の最初の要素の直前の理論上の要素を指す逆反復子を返します。 |
| crbegin() | コンテナ内の最後の要素を指す定数反復子を返します。 |
| クレンド() | コンテナ内の最初の要素の直前の位置を指す定数反復子を返します。 |
| cbegin() | コンテナ内の最初の要素を指す定数反復子を返します。 |
| いくつか() | コンテナ内の最後の要素の後の位置を指す定数反復子を返します。 |
| サイズ（） | セット内の要素の数を返します。 |
| max_size() | セットが保持できる要素の最大数を返します。 |
| 空の（） | セットが空かどうかを返します。 |
| 挿入(const g) | 新しい要素「g」をセットに追加します。 |
| イテレータ挿入 (イテレータの位置、const g) | イテレータが指す位置に新しい要素「g」を追加します。 |
| 消去(イテレータの位置) | イテレータが指す位置にある要素を削除します。 |
| 消去(const g) | 値「g」をセットから削除します。 |
| クリア（） | セットからすべての要素を削除します。 |
| key_comp() / value_comp() | セット内の要素の順序を決定するオブジェクトを返します (デフォルトでは「<」)。 |
| find(const g) | セット内の要素「g」が見つかった場合はその反復子を返し、それ以外の場合はその反復子を最後まで返します。 |
| カウント(定数) | 要素「g」がセット内に存在するかどうかに基づいて 1 または 0 を返します。 |
| lower_bound(const g) | 「g」と同等であるか、セット内の要素「g」の前に絶対に置かれない最初の要素への反復子を返します。 |
| upper_bound(const g) | セット内の要素「g」の後に続く最初の要素への反復子を返します。 |
| 等しい範囲() | この関数はペアの反復子を返します。 (key_comp)。このペアは、k と同等のキーを持つコンテナ内のすべての要素を含む範囲を指します。 |
| 埋め込む() | この関数は、挿入される要素が一意であり、セット内にまだ存在しない場合にのみ、新しい要素をセット コンテナに挿入するために使用されます。 |
| emplace_hint() | 挿入が行われた位置を指すイテレータを返します。パラメータで渡された要素がすでに存在する場合、既存の要素が存在する位置を指すイテレータを返します。 |
| スワップ（） | この関数は 2 つのセットの内容を交換するために使用されますが、セットはサイズが異なっていても同じタイプである必要があります。 |
| 演算子= | 「=」は、セットを別のセットにコピー (または移動) する C++ STL の演算子で、set::operator= は対応する演算子関数です。 |
| get_allocator() | セットに関連付けられたアロケーター オブジェクトのコピーを返します。 |
セットと順序なしセットの違い
| セット | 順序なしセット |
|---|---|
| Set は要素をソート順に格納します | Unordered Set は要素をソートされていない順序で保存します |
| 固有要素のみを設定して保存/取得する | 順序なしセットは一意の値のみを保存/取得します |
| セットは実装に二分探索木を使用します | 順序なしセットは実装にハッシュ テーブルを使用します |
| 開始反復子と終了反復子を指定することで複数の要素を消去できます | イテレータの位置が指定されている要素を消去できます |
| セット名を設定します。 | unowned_set UnownedSet_Name; |
詳細については、記事を参照してください。 セットと順序なしセット 。