競プロで使えるかもしれないC++標準機能
この記事はあくあたん工房アドベントカレンダー12月15日の記事です．
12月14日の記事は けんけんヾ(๑╹◡╹)ﾉ” さんの Android JetpackのNavigationコンポーネントにChrome Custom Tabsを追加する でした．
はじめに
今年4月にAtCoderで競プロを始めてどハマりして以来，定期的にcpprefjpを読むようになった帰宅志願者です．cpprefjpを読んでいると競プロに使えそうなC++の標準機能に出会うのですが，あまり知られていないように思われるものがいくつか存在します．そこでこの記事ではそういった「知られざる便利(かもしれない)機能」を紹介したいと思います．なお僕はC++の規格自体に精通しているわけではないので，紹介内容は必ずしも正確ではないかもしれません．ご了承ください．なおこの記事では using namespace std を用いることを前提とします．
pair や tuple から値を取り出す
C++14の場合
tie()を使うとこんな風に書けます．
auto p = make_pair(111, "aaa"); int x; string y; tie(x, y) = p; // x = 111, s = "aaa" auto t = make_tuple("ABC", 123, 'D'); string a; int n; char c; tie(a, n, c) = t; // a = "ABC", b = 123, c = 'D' auto s = make_tuple(1.23, 4.56, 7.89); double = d, e; // 要らない値の位置には標準で用意されている // ignoreというプレースホルダを指定すると無視できる tie(d, ignore, e) = s; // d = 1.23, e = 7.89
C++17の場合
構造化束縛を使いましょう．
auto p = make_pair(111, "aaa"); auto [ x, y ] = p; // x = 111, y = "aaa" auto t = make_tuple("ABC", 123, 'D'); auto [ a, n, c ] = t; // a = "ABC", b = 123, c = 'D' auto s = make_tuple(1.23, 4.56, 7.89); // 要らない値は無視出来ない auto [ d, unused, e ] = s; // d = 1.23, unused = 4.56, e = 7.89 map<string, int> m; // ここにmへの挿入処理 for (const auto& [ key, value ] : m) { // このように範囲for文でも使える }
変数の型を取得する
正確には式の型ですが decltype で取得出来ます．
vector<vector<pair<int, int>>> g; // のような変数があったとして decltype(g) h; // とすると(実際にこんな使い方をするかは別として) // hをvector<vector<pair<int, int>>>型の変数として宣言できる． // 実際の使い方としては vector<pair<int, int>> v; auto f = [&](auto a, auto, b) -> decltype(v[0]) { // みたいにラムダ式で明示的に返り値の型を指定する // 必要があるときとかは使える…かもしれない };
二乗和の平方根
std::hypot() という関数がありまして，
double x1, y1; double x2, y2; double dist = hypot(x1 - x2, y1 - y2); // sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2)) と同じ結果が得られる
みたいに二点間の距離の計算が簡潔に書けるのではないかと．
同じ文字で一定の長さの文字列を作る
stringのコンストラクタには，第一引数に文字数，第二引数に文字を取って文字を文字数回繰り返した文字列を生成するものがあります．
string a(1, 'A'), b(2, 'B'), c(3, 'C'); // a = "A", b = "BB", c = "CCC"
配列の各要素に添字番号を代入する
iota()を使うと配列の各要素に添字番号を代入することが出来ます．
vector<int> v(10); iota(begin(v), end(v), 0); // a[0] = 0, a[1] = 1, ... , a[9] = 9
僕はUnionFind木を構造体で持つときにコンストラクタで配列を初期化するときに使ってます．
オブジェクトを構築しつつコレクションへの挿入する
emplace 系の関数を使うと簡潔に書けます．
vector<pair<int, int>> v; // emplace 系の関数を使わない書き方 v.push_back(make_pair(12, 34)); // emplace 系の関数を使った書き方 v.emplace_back(12, 34);
vector 以外にも queue や stack などのコレクションには emplace 系の関数が生えているので詳しく調べてみるといいかもしれません．
累積和を取る
partial_sum() という関数があります．
vector<int> a; // ここに初期化処理 partial_sum(begin(a), end(a), begin(a)); // aの中身は元の配列の累積和になる．
この関数はデフォルトでは累積和の計算をしますが，bit_xor() や gcd() と組み合わせることが出来ます．
vector<int> a; vector<int> res1, res2, res3; // ここに初期化処理 partial_sum(begin(a), end(a), begin(res2), bit_xor<>()); // 累積xor partial_sum(begin(a), end(a), begin(res3), gcd<int, int>); // 累積gcd (C++17)
条件を満たす隣接要素を検索する
adjacent_find() を使います．
vector<int> v; // ここに初期化処理 auto itr1 = adjacent_find(begin(v), end(v)); // 最初の等しい隣接要素の最初のイテレータが入る auto itr2 = adjacent_find(begin(v), end(v), not_equal_to<>()); // 最初の異なる隣接要素の最初のイテレータが入る
この関数ぶっちゃけ使わない
n個の要素から最大・最小となる値を得る
n個の要素が「配列」の場合
max_element() という関数が便利です．
vector<int> v; // ここに初期化処理 auto itr = max_element(begin(v), end(v)); // イテレータが返ってくる
n個の要素が「変数」だったり「定数」だったりする場合
max() に initializer_list を突っ込みましょう．
int a = 25, b = 51, c = 19; int m = max({ a, b, c, 38 }); // m = 51
条件によって操作する変数を変える
三項演算子は左辺値に対しても使えます．左辺値がなんのことかわからなくてもまあ例を見てみてください．
int a = 100, b = 1; bool flag = false; (flag ? a : b) = 25; // a = 100, b = 25
僕は二分探索法で使ってます．
int64_t ok = 0, ng = 1e9 + 1; while (abs(ng-ok) > 1) { bool flag = false; // なんらかの処理 (flag ? ok : ng) = n; }
代入処理以外にも使えます．
// 入力された数が奇数ならaへ，偶数ならbへ突っ込む vector<int> a, b; for (int i = 0; i < 10; i++) { int tmp; cin >> tmp; (tmp % 2 ? a : b).push_back(tmp); }
立っているbitの数を数える
bitset を使うと楽チンです．
int b = 31415926; int c = bitset<32>(b).count();
複数の同じ型の変数に対して同一の処理を施す
範囲for文は initializer_list に対しても使えることを利用します．
vector<int> a, b; for (auto& e : { a, b }) { // なんらかの処理 }
おわりに
C++の標準機能は上手く使うことでプログラムから余計な複雑さを取り除いてくれるので，アルゴリズムを考えることに集中できるようになります．これは僕のような初心者にとっては非常に大きな利点になるのではないでしょうか．
以上で紹介を終わりますが，まだここに書かれていないもので僕が使っているものが他にもあれば追加しようと思います．最後までお読み頂きありがとうございました．
