競プロなどでsetを使うことがしばしばあって、よく使うメンバ関数を忘れることが多いのでメモっておきます。(全部のメンバ関数を網羅しているわけではありません。)
setとは
setは平行2分器と言われる構造で、要素が木を使って比較演算子に従って並べられています。例えばint型では
set.cpp
#include<bits/stdc++.h>
using namespace std;
set<int> s = {3,1,2,6,5,4,6};
などと与えます。次の命令で出力すると
set.cpp
for( int x : s ) cout << x << " ";
cout << endl;
1 2 3 4 5 6
と出力されます。setにはvectorと違ってインデックスがなく、要素は昇順にソートされた状態で出力されます。
また、重複する要素は自動で削除されます。
insert
要素を追加するメンバ関数です。
set.cpp
s.insert(7);
s.insert(2);
再び出力すると
1 2 3 4 5 6 7
となり、重複していない7が追加されています。また、重複している2を追加してもsに変化はありません。
erase
入力した要素を削除します。
set.cpp
s.erase(7);
1 2 3 4 5 6
先ほど追加した7が消えています。
find
要素が存在するか確認します。存在するならその要素のイテレーター、存在しないならイテレーターs.end()を返します。findを使って得たイテレーターから対応する値を出力すると
set.cpp
//find
decltype(s)::iterator it = s.find(3);
int value;
if(it != s.end()){
value = *it;
cout << value << endl;
}else{
cout << "not found" << endl;
}
it = s.find(8);
if(it != s.end()){
value = *it;
cout << value << endl;
}else{
cout << "not found" << endl;
}
3
not found
となり、sの要素に存在する3はそれが出力され、存在しない8はs.end()が返されています。
lower_bound,upper_bound
vector型のようにlower_bound, upper_boundも使えます。
set.cpp
decltype(s)::iterator itl = lower_bound(s.begin(),s.end(),3);
if(itl != s.end()){
value = *itl;
cout << value << endl;
}else{
cout << "not found" << endl;
}
decltype(s)::iterator itu = upper_bound(s.begin(),s.end(),3);
if(itu != s.end()){
value = *itu;
cout << value << endl;
}else{
cout << "not found" << endl;
}
3
4
lower_boundではキーの値以上の要素で最小のもの、uppper_boundではキーの値より大きい要素で最小のものを出力します。