STL標準ライブラリ
実践編はこちら
#include <bits/stdc++.h>
これをincludeすることで全部使えるようになります．
string
文字列型いろいろ便利
#include <bits/stdc++.h>
using namespace std
int main(){
string s, t;
cin >> s;
cout << s << endl;
s = s + t; //連結
s == t; //比較
s.length(); //長さ
s[i] //i番目の文字を参照
s.substr(i, k); //i番目以降k文字を抽出して得られる文字列
s.find(t); //sの中に文字列tがあればその先頭のアドレスを返す．なければs.nopsを返却
s.replace(i, k, t); //i番目以降k文字を文字列tで置換する．tを空文字列にすれば削除の動作
s.insert(i, t); //i番目の文字の前に文字列tを挿入
}
vector
可変配列．動的に記憶域を確保できる．
#include <bits/stdc++.h>
using namespace std
int main(){
vector<int> a(5);
a.size(); //aの大きさ
a[i]; //i番目の要素にアクセス
a.front(); //先頭を参照
a.back(); //末尾を参照
a.push_back(); //末尾に要素を追加
a.pop_back(); //末尾の要素を削除
}
list
双方向リスト 片方向は forward_list
#include <bits/stdc++.h>
using namespace std
int main(){
list<int> li;
list<int>::iterater p;
list<int>::reverse_iterater r;
li.push_front(); //先頭に挿入
li.front(); //先頭の要素を参照
li.pop_front(); //先頭の要素を削除
li.push_back(); //末尾に挿入
li.back(); //末尾の要素を参照
li.pop_back(); //末尾の要素を削除
li.begin(); //最初の要素を指すイテレーター
li.end(); //末尾の次の要素を指すイテレーター
li.rbegin(); //逆順にした時の最初の要素を指すイテレーター
li.rend(); //逆順にした時の末尾の次の要素を指すイテレーター
li.insert(p, x); //pのさす要素の直前にｘを挿入
li.erase(p); //pの指す要素を削除
li.erase(p, q); //pの指す要素からqの指す要素まで削除
li.clear(); //リストの全要素を削除
*p; //イテレーターの指す要素
p++; //走査方向に向かって次の要素を指すイテレーター
p--; //走査方向に向かって前の要素を指すイテレーター
for (p=li.begin(); p!=li.end(); p++) { *p = ...} //前から走査
for (r=li.rbegin(); r!=li.rend(); r++) { *r = ...} //後ろから走査
}
deque
stackとqueueの両方の働きを持つ
#include <bits/stdc++.h>
using namespace std
int main(){
deque<int> d;
d.push_front(); //先頭に挿入
d.front(); //先頭の要素を参照
d.pop_front(); //先頭の要素を削除
d.push_back(); //末尾に挿入
d.back(); //末尾の要素を参照
d.pop_back(); //末尾の要素を削除
}
priority_queue
ヒープ
priority_queue<int> que; //最大値から出てくるヒープ
priority_queue< int, vector<int>, greater<int> > que; //最小値から出てくるヒープ
que.push(); //要素の追加
que.top(); //先頭をみる
que.pop(); //先頭を削除
set
平衡二分探索木を用いた集合 重複を許す場合はmultisetを使う
set<int> s;
multiset<int> ms;
s.insert(); //要素の追加
s.erase(); //要素の削除
s.find(); //発見したらその要素へのイテレータを返す
s.count(); //要素の数を返す
s.empty(); //空ならtrue
s.size(); //要素数を返却
s.clear(); //空にする
unordered_set
ハッシュテーブルで管理される集合，基本こっちを使う．重複を許す場合にはunordered_multisetを使う
使い方は同じ
unordered_set<int> s;
unordered_multiset<int> ms;
s.insert(); //要素の追加
s.erase(); //要素の削除
s.find(); //発見したらその要素へのイテレータを返す
s.count(); //要素の数を返す
s.empty(); //空ならtrue
s.size(); //要素数を返却
s.clear(); //空にする
map
連想配列， multimap, unordered_map, unordered_multimapもあるよ
任意のキーでアクセスできる
アクセス時間はO(log n)
#include <bits/stdc++.h>
using namespace std
int main(){
map<string, int> m; //キーがstring型，要素がint型
m["apple"] = 10; //要素にアクセス
m.find(10); //要素へのイテレーターを返す．なければm.end()を返却
m.erase(p); //イテレーターの指す要素を削除
map<string,int>::iterator p; //イテレーターを用いた走査
for (p=semester.begin(); p!=semester.end(); p++) {
cout << p->first << ": " << p->second << std::endl; //firstがキー，secondが値
}
}
この表便利, 覚える
| 型 | 1. ランダム アクセスの 時間 | 2. 挿入・削除の 時間 | 3. 検索の時間 | 4. メモリ量 |
|---|---|---|---|---|
vector |
O(1) | O(1)（末尾） O(n)（他） | O(n) | 0～ST |
deque |
O(1) | O(1)（先頭か末尾） O(n)（他） | O(n) | 2*ST/512*SP |
list |
O(n) | O(1) | O(n) | 2*SP |
forward_list |
O(n) | O(1) | O(n) | SP |
unordered_set unordered_multiset
|
不可能 | O(1) | O(1) | 2*SP |
set multiset
|
不可能 | O(log n) | O(log n) | 3*SP |
unordered_map unordered_multimap
|
O(1) | O(1) | O(n) | 2*SP |
map multimap
|
O(log n) | O(log n) | O(n) | 3*SP |
pair
値をペアで保存
pair<int int> p;
p.first; //1つ目の要素にアクセス
p.second; //２つ目の要素にアクセス
その他
sort
STLのソートは簡単に書けて超高速．O(n log n)
sort(a.begin(), a.end(),); //昇順ソート
sort(a.begin(), a.end(), greater<int>()); //降順ソート
swap
swap(a, b); //値を交換する
min, max
min(a, b); //小さい方
max(a, b); //大きい方
二分探索
binary_search(vc.begin(), vc.end(), x); //trueかfalseを返す
lower_bound(vc.begin(), vc.end(), x); //x以上の値が初めて現れる位置のイテレータを返す
upper_bound(vc.begin(), vc.end(), x); //xより大きい値が初めて現れる位置のイテレータを返す
equal_range(vc.begin(), vc.end(), x); //上記２カ所のイテレータのペアを返す
長いのはtypedef
typedef unsigned long ul;
typedef pair<ul, ul> P;
関数マクロも便利
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
int main() {
REP(i, 10)
cout << i << '\n';
}
参考文献
[1]: https://gist.github.com/rigibun/7905920 "競プロ on cpp"
[2]: https://qiita.com/h_hiro_/items/a83a8fd2391d4a3f0e1c "[C++] STLの型の使い分け"