# 競プロでよく使うライブラリ(C++)
この記事は [茨大 Advent Calendar 2020](https://adventar.org/calendars/5043) 4日目の記事です．
皆様はじめまして．4日目担当です．
中の人は競プロerなので，競プロでよくお世話になっているライブラリ(C++)について書きます．
説明の都合上，AtCoderやAOJの問題のネタバレを含みますのでご注意ください．
## vector
可変長配列です．競プロでほぼ毎回のように使っています．もちろん普通の配列としても使えますが，グラフを隣接リスト形式で持ちたいときなどで特に力を発揮します．
vectorを使いたいときは，ヘッダ`<vector>`をインクルードする必要があります．
| コード | すること | 説明 |
| ----------------------- | ---------- | -------------------------------------------------------------------------------------------------------------------- |
| `vector<T> hoge;` | 配列の宣言 | `T`型の配列を宣言する．例えば`vector<int> hoge;`とすると，int型の配列を宣言できる． |
| `vector<T> hoge(n);` | 同上 | `T`型の配列（要素数n）を宣言する． |
| `vector<T> hoge(n, p);` | 同上 | `T`型の配列（要素数n）を宣言し，pで初期化する． |
| `hoge[i]` | 要素の参照 | i番目の要素を参照する．何かしらの処理を施すこともできる． |
| `hoge.size()` | 要素数を知る | hogeの要素数が返ってくる． |
| `hoge.push_back(p);` | 要素の追加 | 配列の末尾にpを追加する．例えばhoge = {2, 7, 1}のときに`hoge.push_back(8);`を実行すると，hoge = {2, 7, 1, 8}となる． |
| `hoge.pop_back();` |要素の削除 | 配列の末尾にある要素を削除する．例えばhoge = {2, 7, 1, 8}のときに`hoge.pop_back();`を実行すると，hoge = {2, 7, 1}となる． |
まずは1次元配列の使用例を示します．以下のコードは[ITP1_6_A - Reversing Numbers](https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/6/ITP1_6_A)の解答例です．この問題は，数列を受け取り，それを逆順で出力するというものです．
```
#include <iostream>
#include <vector>
using namespace std;
int main(){
int n;
// 数列の要素数はn
cin >> n;
// int型，要素数nの配列を宣言
vector<int> a(n);
// データを読み込む
for(int i = 0; i < n; i++) cin >> a[i];
// データを出力する
for(int i = n-1; i >= 0; i--){
cout << a[i];
if(i == 0) cout << endl;
else cout << " ";
}
return 0;
}
```
以下のコードは[ALDS1_11_A - Graph](https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/11/ALDS1_11_A) の解答例です．この問題は，隣接リスト形式の有向グラフを受け取り，隣接行列表現に変換して出力するというものです．
```
#include <iostream>
#include <vector>
using namespace std;
int main(){
// グラフはn頂点
int n;
cin >> n;
// G[i]は頂点iを始点とする辺の情報（終点となる頂点の番号）の配列
vector<vector<int>> G(n);
for(int i = 0; i < n; i++){
// 頂点u (1 <= u <= n) を始点とする辺がk本ある
int u, k;
cin >> u >> k;
// 頂点番号を0から数えるように変換
u--;
for(int j = 0; j < k; j++){
int v;
// 頂点uから頂点vへの辺がある
cin >> v;
// 頂点番号を0から数えるように変換
v--;
// 配列の末尾にデータを追加する
G[u].push_back(v);
}
}
// 隣接行列表現に変換
vector<vector<int>> matrix(n, vector<int>(n, 0));
for(int i = 0; i < n; i++){
// 頂点iを始点とする辺の本数はG[i].size()でわかる
for(int j = 0; j < G[i].size(); j++){
matrix[i][G[i][j]] = 1;
}
}
// 結果を出力
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cout << matrix[i][j];
if(j != n-1) cout << " ";
else cout << endl;
}
}
return 0;
}
```
2次元配列（配列の配列）を作るときは`vector<vector<T>> hoge;`のようにします．
## sort
配列のデータを昇順に並び替えるときに使います．ソートを自前で実装するのは大変なので，ライブラリにやらせましょう．
sortを使いたいときは，ヘッダ`<algorithm>`をインクルードする必要があります．
以下のコードは，n個の整数値を配列に格納してからソートし，ソートした結果を出力するプログラムです．
```
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
// n個の整数値を入力
int n;
cin >> n;
vector<int> data(n);// 例えば {3, 2, 1, 7}
for(int i = 0; i < n; i++) cin >> data[i];
// ソートはライブラリ任せ
sort(data.begin(), data.end());// {1, 2, 3, 7}
// 結果を空白区切りで出力
for(int i = 0; i < n; i++) cout << data[i] << " ";
return 0;
}
```
`vector<T> hoge`の要素をソートするときは，sort関数を次の形式で呼び出します．
`sort(hoge.begin(), hoge.end());`
要素を降順にソートしたいときは，次の形式を用います．`T`は要素の型（例えば`int`）です．
`sort(hoge.begin(), hoge.end(), greater<T>());`
sort関数の呼び出し方について詳しく説明しようとすると「イテレータ」の知識が必要になりますが，上記の形式を覚えておけば（競プロでは）大丈夫です．
演算子オーバーロードを使えば，独自に定義した構造体などもsort関数でソートできるようになります．
## queue
キュー（待ち行列）はFIFO（先入れ先出し）のデータ構造です．先に入れたものが先に取り出されます．例えばラーメン屋の待ち行列は先に並んだ人が先に入店できる（取り出される）のでFIFOですね．
C++ではキューがライブラリ(queue)として用意されているので，キューそのものを自分で実装しなくてもFIFOで何かしらのデータを管理できます．
グリッドや普通のグラフに対して幅優先探索を行うときにはqueueの出番です．幅優先探索ができるようになると様々な問題を解けるようになります．緑コーダー以上を目指すなら，queueと幅優先探索をセットで履修しましょう．
queueを使いたいときは，ヘッダ`<queue>`をインクルードする必要があります．
| コード | すること | 説明 |
| --------------- | ------------ | ------------------------------------------------------ |
| `queue<T> Q;` | キューの宣言 | `T`型の要素を格納するキューを宣言する． |
| `Q.push(hoge);` | 要素の追加 | `hoge`をキューに追加する． |
| `Q.front();` | 要素の参照 | キューの先頭にある要素を参照する．ただし削除はしない． |
| `Q.pop();` | 要素の削除 | キューの先頭にある要素を削除する（取り出す）． |
| `Q.size();` | 要素数を知る | キューに入っている要素の個数が返ってくる． |
以下のコードは[ALDS1_11_C - Breadth First Search](https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/11/ALDS1_11_C) の解答例です．この問題は，辺の重みがすべて同一の有向グラフについて，ある1つの頂点から他の頂点への最短距離を求めるというものです．やることはまさに幅優先探索です．
```
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main(){
// グラフはn頂点
int n;
cin >> n;
// G[i]は頂点iを始点とする辺の情報（終点となる頂点の番号）の配列
// d[i] == -1 の場合は未訪問
vector<vector<int>> G(n);
for(int i = 0; i < n; i++){
// 頂点u (1 <= u <= n) を始点とする辺がk本ある
int u, k;
cin >> u >> k;
// 頂点番号を0から数えるように変換
u--;
for(int j = 0; j < k; j++){
int v;
// 頂点uから頂点vへの辺がある
cin >> v;
// 頂点番号を0から数えるように変換
v--;
// 配列の末尾にデータを追加する
G[u].push_back(v);
}
}
// 頂点1からの最短距離を記録する配列 d[i-1]は頂点iへの最短距離
vector<int> d(n, -1);
// 頂点1から頂点1への最短距離は0
d[0] = 0;
// 訪問予定の頂点を管理するキュー
queue<int> Q;
// 頂点1をキューに入れて探索開始
Q.push(0);
// キューに要素が残っている間は探索を継続
while(Q.size()){
// キューの先頭から要素を取り出す
int u = Q.front();
// キューの先頭の要素を削除
Q.pop();
// 隣接する頂点のうち未訪問のものに訪問する
for(int i = 0; i < G[u].size(); i++){
if(d[G[u][i]] == -1){
d[G[u][i]] = d[u]+1;
Q.push(G[u][i]);
}
}
}
// 結果を出力
for(int i = 0; i < n; i++) cout << i+1 << " " << d[i] << endl;
return 0;
}
```
幅優先探索について知りたい場合は，[BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜 - Qiita](https://qiita.com/drken/items/996d80bcae64649a6580) などをお読みいただければと思います．
## map
連想配列（整数以外の要素を添字にできる配列）です．C++のmapは一般に二分木として実装されており，mapで管理している要素の数を$n$とすると要素の追加・削除・検索（参照）がすべて$O(\log n)$で行えます．イテレータをうまく使えばキー（添字）が最小（もしくは最大）の要素を確認するなどの操作も行えるので，大変有用なデータ構造です．
mapを使いたい場合は，ヘッダ`<map>`をインクルードする必要があります．
| コード | すること | 説明 |
| ------------------------- | -------------- | ------------------------------------------------------------------------------------------------------------------------------------------------- |
| `map<KTYPE, VTYPE> hoge;` | 連想配列の宣言 | キーの型が`KTYPE`,キーに紐づく要素の型が`VTYPE`の連想配列を宣言する． |
| `hoge.count(key)` | 要素の存在確認 | `key`に紐付いたデータが存在するかを確認する．戻り値が1ならデータが存在し，0なら存在しない．[^map_count_footnote] |
| `hoge[key] = value;` | 要素の追加 | `key`に`value`が紐付いたデータを追加する． |
| `hoge.at(key)` | 要素の参照 | `key`をキーとするデータを参照する．対応する要素が存在しない場合は，`out_of_range`例外が投げられる． |
| `hoge[key]` | 要素の参照 | `key`をキーとするデータを参照する．対応する要素が存在しない場合は，`VTYPE`のデフォルト値（int型なら0）が`key`をキーとするデータとして追加される． |
| `hoge.erase(key);` | 要素の削除 | `key`をキーとするデータを削除する． |
| `hoge.size()` |要素数を知る | 連想配列に入っているキーの個数が返ってくる． |
以下のコードは[AtCoder Beginner Contest 180 C - Cream puff](https://atcoder.jp/contests/abc180/tasks/abc180_c)の解答例です．「$n$の約数をすべて見つけ，小さい順に出力せよ」という問題ですが，見つけた約数の管理にmapを使っています．
```
#include <iostream>
#include <map>
using namespace std;
int main(){
// nの約数を見つける問題
// n <= 10の12乗なのでlong long int（64bit整数）を使用
long long int n;
cin >> n;
// mapのキーはnの約数 値は適当な要素でよい（この問題の場合）
map<long long int, int> ans;
// 1から√nまでの整数で試し割り
// これですべての約数を見つけられる
for(long long int i = 1; i*i <= n; i++){
if(n % i == 0){
// nがiで割り切れたならば iはnの約数
// この問題の場合，キーに紐づく値は何でも良い
ans[i] = 1;
// iがnの約数ならば n/i もnの約数
ans[n/i] = 1;
}
}
// 範囲for文でmapの要素をすべて取り出す
// キーの値の小さい順で要素が取り出される
for(auto p: ans){
// キーの値はp.firstを参照すると分かる
cout << p.first << endl;
}
return 0;
}
```
mapで管理している要素をすべて出力したいときには，範囲for文を使います．取り出される順番はキーの値の小さい順です．mapで管理している要素をすべて取り出すときに使う範囲for文は，だいたい以下のような感じになるかと思われます．`auto`を使うと，変数の型の指定が楽です．
```
// pはキーと値の組1つを格納する変数 hogeは要素を詰め込んだmap
for(auto p: hoge){
// キーの値はp.firstを参照すると分かる
// キーに紐づく値はp.secondを参照すると分かる
auto key = p.first;
auto value = p.second;
// ここには何か処理を書く
}
```
また，イテレータをうまく使えばキーの値が最小もしくは最大の要素を確認することもできます．要素を詰め込んだmapを`hoge`とすると，確認できる要素とそれを確認するためのコードは次の通りです．していることは要素の参照なので，計算量はどれも$O(\log n)$です．
| コード | 確認できる要素 |
| --------------------- | -------------- |
| `hoge.begin()->first` | キーの最小値 |
| `hoge.begin()->second` | 最小のキーに紐づく値 |
| `hoge.rbegin()->first` | キーの最大値 |
| `hoge.rbegin()->second` | 最大のキーに紐づく値 |
以下のコードが使用例となります．
```
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main(){
// 整数をキー，文字列をキーに紐づく値とするmap
map<int, string> hoge;
// mapにキーと値の組を登録
hoge[1800] = "ABC182";
hoge[900] = "ABC169";
hoge[1500] = "HHKB2020";
hoge[1200] = "ABC172";
// keyの最小値とそれに紐づく値（文字列）を出力
cout << hoge.begin()->first << " " << hoge.begin()->second << endl;
// keyの最大値とそれに紐づく値（文字列）を出力
cout << hoge.rbegin()->first << " " << hoge.rbegin()->second << endl;
return 0;
}
```
上記のコードを実行すると，次のような出力を得られます．
```
900 ABC169
1800 ABC182
```
[^map_count_footnote]:実際には`key`をキーとする要素の個数が返ってくるが，mapの場合は1つのキーに対して1つの値しか紐付けられない．よってmapの場合は戻り値が1または0のみとなる．
## 参考資料
* vector - cpprefjp C++日本語リファレンス : https://cpprefjp.github.io/reference/vector/vector.html
* sort - cpprefjp C++日本語リファレンス : https://cpprefjp.github.io/reference/algorithm/sort.html
* queue - cpprefjp C++日本語リファレンス : https://cpprefjp.github.io/reference/queue/queue.html
* map - cpprefjp C++日本語リファレンス : https://cpprefjp.github.io/reference/map/map.html
* FIFO - Wikipedia : https://ja.wikipedia.org/wiki/FIFO
* AA - 3.03.STLのコンテナ : https://atcoder.jp/contests/APG4b/tasks/APG4b_aa
* レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 - Qiita : https://qiita.com/e869120/items/eb50fdaece12be418faa
Sign in with Wallet
Connect another wallet