std::setについてシンプルに
まずは何はともあれ基礎から。std::setは値を挿入すると共にソートされる機能を持っている。
データ構造は赤黒木。探索、挿入、削除ともにO(log n)。
ランダムアクセスを行うことはできないので参照したい場合はインクリメントなどを用いる必要がある。
#include <iostream> #include <set> using namespace std; int main() { set<int> S; S.insert(5);//挿入 S.insert(1); S.insert(3); cout << *S.begin() << endl; //1 cout << *++S.begin() << endl;//3 cout << *S.rbegin() << endl; //5 cout << *S.begin() << endl; //1 イテレータはインクリメント後は元に戻る。 for (auto itr = s.begin(); itr != s.end(); itr++) { cout << *itr << endl; } }
まだたくさん記事まとめてかけるほど筆が早くないので今回はここまで。
次回はどんな問題の時setを用いるのかとか書きたい
2018/5/20追記 おすすめ問題 C - Write and Erase
ちなみにfind()をして見つからないときはイテレーターend()を返すよ!
追記(2019/5/25) setはpair型も認識できる F - 種類数 α