競プロ向けSTL標準ライブラリ

# STL標準ライブラリ

実践編は[こちら](https://qiita.com/kawa-Kotaro/items/e551c94ff7dbbfcaebeb)


`#include <bits/stdc++.h>`

これをincludeすることで全部使えるようになります．



## string

文字列型いろいろ便利

```c++
#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

可変配列．動的に記憶域を確保できる．

```c++
#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`

```c++
#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`の両方の働きを持つ

```c++
#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

ヒープ

```C++
priority_queue<int>  que;  //最大値から出てくるヒープ

priority_queue< int, vector<int>, greater<int> > que; //最小値から出てくるヒープ 

que.push();	//要素の追加
que.top();	//先頭をみる
que.pop();	//先頭を削除
```



## set

平衡二分探索木を用いた集合　重複を許す場合は`multiset`を使う

```c++
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`を使う

使い方は同じ

```c++
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)

```c++
#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が値
	}
}
```






[この表](https://qiita.com/h_hiro_/items/a83a8fd2391d4a3f0e1c)便利, 覚える

| 型                                   | 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

値をペアで保存

```c++
pair<int int> p;
p.first;	//1つ目の要素にアクセス
p.second;	//２つ目の要素にアクセス
```



## その他

**sort**

STLのソートは簡単に書けて超高速．**O(n log n)**

```C++
sort(a.begin(), a.end(),);	//昇順ソート
sort(a.begin(), a.end(), greater<int>());	//降順ソート
```



**swap**

```c++
swap(a, b);	//値を交換する
```



**min, max**

```c++
min(a, b);	//小さい方
max(a, b);	//大きい方
```



**二分探索**

```c++
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`

```c++
typedef unsigned long ul;
typedef pair<ul, ul> P;
```



関数マクロも便利

```c++
#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の型の使い分け"