C++には、様々な機能をまとめた標準ライブラリ(STL:Standard Template Library)が用意されています。
その標準ライブラリの中で、競プロで使えるライブラリについてまとめます。なお、本文中では以下のコードなどは省略しています。
#include<bits/stdc++.h>
using namespace std;
abs
絶対値を返す。浮動小数点型でも使える。
cout << abs(-5) << endl; // => 5
double x = -1.8;
cout << abs(x) << endl; // => 1.8
max・min
2つのオブジェクトの大きい方・小さい方を返す。
int a = 10;
int b = 20;
cout << max(a, b) << endl; // => 20
cout << min(a, b) << endl; // => 10
swap
2種類のオブジェクトの値を交換する。
int a = 10;
int b = 20;
swap(a, b);
cout << a << endl; // => 20
cout << b << endl; // => 10
int a[5] = {1, 2, 3, 4, 5};
//0番目と4番目の要素を交換
swap(a[0], a[4]);
for(int i = 0; i < 5; i++){
cout << a[i] << " "; // => 5 2 3 4 1
}
vector
可変長配列。
vector<int> v = {1, 8, 4, 7, 9};
//1番目の要素に2を代入
v[1] = 2; // => {1, 2, 4, 7, 9}
//要素数
cout << v.size() << endl; // => 5
//末尾から要素を削除
v.pop_back(); // => {1, 2, 4, 7}
//末尾に要素を追加
v.push_back(5); // => {1, 2, 4, 7, 5}
//要素の挿入
v.insert(v.begin() + 2, 3); // => {1, 2, 3, 4, 7, 5}
//要素の削除
v.erase(v.begin() + 4); // => {1, 2, 3, 4, 5}
sort
指定された範囲の要素を並び替える。
int a[5] = {3, 1, 5, 2, 4};
sort(a, a + 5);
for(int i = 0; i < 5; i++){
cout << a[i] << " "; // => 1 2 3 4 5
}
vector<int> v = {4, 3, 1, 5, 2};
sort(v.begin(), v.end());
for(int i = 0; i < 5; i++){
cout << v[i] << " "; // => 1 2 3 4 5
}
reverse
範囲内の要素の並びを反転させる。
int a[5] = {1, 2, 3, 4, 5};
reverse(a, a + 5);
for(int i = 0; i < 5; i++){
cout << a[i] << " "; // => 5 4 3 2 1
}
vector<int> v = {1, 2, 3, 4, 5};
reverse(v.begin(), v.end());
for(int i = 0; i < 5; i++){
cout << v[i] << " "; // => 5 4 3 2 1
}
lower_bound
指定した値以上の値を持つ最初の要素の位置を検索する。戻り値はイテレータ。「*」をつけることで値を参照できる。
int a[7] = {1, 1, 2, 3, 5, 8, 13};
//値が6以上の最初の要素の位置
cout << lower_bound(a, a + 7, 6) - a << endl; // => 5
//値が6以上の最初の要素の値
cout << *lower_bound(a, a + 7, 6) << endl; // => 8
vector<int> v = {1, 1, 2, 3, 5, 8, 13};
//値が6以上の最初の要素の位置
cout << lower_bound(v.begin(), v.end(), 6) - v.begin() << endl; // => 5
//値が6以上の最初の要素の値
cout << *lower_bound(v.begin(), v.end(), 6) << endl; // => 8
next_permutation
要素を並び替え、元の順序を辞書順で次に大きい順列に置き換える。
int a[3] = {1, 2, 3};
next_permutation(a, a + 3);
for(int i= 0; i < 3; i++){
cout << a[i] << " "; // => 1 3 2
}
vector<int> v = {1, 3, 2};
next_permutation(v.begin(),v.end());
for(int i= 0; i < 3; i++){
cout << v[i] << " "; // => 2 1 3
}
next_permutationは、次の順列が存在する場合は「true」を返し、存在しない場合は「false」を返す。以下のようにすれば、順列をすべて列挙できる。
int a[3] = {1, 2, 3};
do {
for(int i= 0; i < 3; i++){
cout << a[i] << ' ';
}
cout << endl;
} while(next_permutation(a, a + 3));
/*
実行結果
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
*/
参考
厳選!C++ アルゴリズム実装に使える 25 の STL 機能【前編】 – Qiita