競プロでも使える C++ の便利機能
はじめに
C++14, 17, 20 と規格が改定されていくにつれ、色々便利な機能が追加されています。
そのうちのいくつかは競プロであっても有用なのですが、特に最近始めた人のコードを読んでいるとほとんど使われておらずもったいないと感じることが多いです。
そこで今回は今すぐにでも使えそうな*1機能を紹介したいと思います。
ただし、それぞれの機能について深く掘り下げはしません。
一応、規格が策定された順で書いてあります。
ジャッジによっては古いコンパイラしか使えなかったりするためです。
例えば AtCoder はまだ C++14 しか使えませんね。すぐ上がりそうですが。
Codeforces は C++17 が使えます。頻繁にアップデートしている印象があります。
ライブラリを自作で整備する人に有用な機能もたくさんあるのですが、少数派だと思ったのでこの記事には書きません。あしからず。
C++11 ~
range-based for
とりわけ vector などのコンテナをイテレートするのに便利です。
要素の中身だけではなく、インデックスも欲しい場合は通常の for によるループを書くことになるでしょう。
vector<int> v = {1, 2, 3}; // index もほしい場合 for(int i = 0; i < (int)v.size(); ++i) { cout << "i: " << i << " => " << v[i] << endl; } // range-based for for(auto const x : v) { cout << x << endl; }
ラムダ式
その場でちょっとした関数を生成できる機能です。競プロにおける用途は、例えば
- 外に関数を切り分ける程でもないが、分けておくと見やすいとき(二分探索の check 関数など)、
- キャプチャによりローカル変数を参照できるような関数が欲しい時(サボりたいとき便利
- 一部ライブラリの一般化のため
などがあるでしょう。
// 二分探索 auto check = [&] (int x) { ... }; int lb = 0, ub = inf; while(ub - lb > 1) { const int mid = (ub - lb) >> 1; (check(mid) ? lb : ub) = mid; } // 再帰関数(サボり) // グローバル変数は嫌だがローカル変数をたくさん使いたいときに楽 vector<vector<int>> g; // graph function<void(int, int)> dfs = [&] (int v, int p) { // [&] で参照キャプチャ for(auto to : g[v]) { if(to == p) continue; dfs(to, v); } }; dfs(0, -1);
再帰の例は function を使っているので定数倍遅いことに注意が必要です。
オーバーヘッドが気になる人は
C++のラムダで再帰する - koturnの日記
こういう記事を参考にすると良いでしょう。
自分はその場でちゃちゃっと書いちゃいたい人なので、function を使う場面が多いです。
emplace_* メソッド
vector などのコンテナに primitive 型以外を持たせる場合に使えたりします。
よくあるケースは pair だと思います。
queue<pair<int, int>> que; vector<pair<int, int>> v; // 二行は同じ意味と考えて良い(本当は違います) que.push(make_pair(0, 0)); que.emplace(0, 0); v.push_back(make_pair(0, 0)); v.emplace_back(0, 0);
using alias
typedef の上位互換です。template と一緒に使えるので便利です。
using ll = long long; // typedef long long ll; と同じ // template にも使える template <typename T> using matrix = vector<vector<T>>;
std::next, std::prev
イテレータを1つ進める、戻す機能。
std::set と一緒に使うことが多い気がします。advance で似たことはできますけどね。
set<int> s = {1, 2, 3}; auto it = begin(s); cout << *it << endl; // 1 it = std::next(it); cout << *it << endl; // 2 it = std::prev(it); cout << *it << endl; // 1
乱数ライブラリ random
メルセンヌ・ツイスタといった疑似乱数生成器が使えます。
uniform_int_distribution などと合わせて使えば、指定された範囲での一様乱数を得られたりします。
いっぱいあるんでここで調べてください(書くのがめんどくさくなりました)
random - cpprefjp C++日本語リファレンス
std::min/max + initializer_list
min, max に3つ以上の引数を入れたい場面があるかもしれませんが、initializer_list と合わせて使えば楽にかけます。
int a = 1, b = 2, c = -1; cout << max(a, max(b, c)) << endl; // つらい cout << max({a, b, c}) << endl; // よさ
C++14 ~
C++14 は C++11 に比べて大きな変化はないですが、細かいところが修正されています。
2進数リテラル
int b1 = 0b11; // => 3 int b2 = 0b0110; // => 6
桁区切り
1e9 など、0が連続して見にくいときに便利かも。
int inf = 1'000'000'000; // 1e9
generic lambda
lambda 式の引数に auto が使えます。
// 書くの面倒 auto f1 = [] (std::vector<int> v) { ... }; // 楽 auto f2 = [] (auto v) { ... };
本当は型省略のためだけにあるわけじゃない(実質 template と同じなので…)のですが、まあいいでしょう。
variable templates
変数定義時に template を使えます。inf とか pi とかの定数に対して使うと便利かも。
template <typename T> constexpr T INF = numeric_limits<T>::max() / 2; cout << INF<int> << " " << INF<long long> << endl;
C++17 ~
構造化束縛 (structured bindings)
pair、tuple、あるいは構造体などから各要素を取り出す機能。
auto p = make_pair(0, 1); auto t = make_tuple(1, 2, 3); auto [fst, snd] = p; // fst == 0, snd == 1 auto [fst, snd, trd] = t; // fst == 1, ...
map を range-based for で回してうんたら~とか、queue に頂点と距離持たせてうんたら~みたいなときに便利でしょうね。
std::gcd, lcm
なんか追加されてました。O(logn) だと思います。
引数に int を渡すと int のまま計算されるので、long long が欲しい場合は注意が必要です(そういう意味では自作の lcm のほうがいいかもね)。
int n = numeric_limits<int>::max(); int m = n - 1; cout << lcm(n, m) << endl; // overflow cout << lcm((ll)n, m) << endl; // ok
C++20 ~
書くの飽きた(は?)。まあ 20 はまだ先だし、そのうち書きますね。
気が向いたときにちょっとずつ追記していきます。
Range
Range という概念があるんですけど、例えば以下のようなコードが書けます。
// for(int i = 0; i < n; ++i); と同等 for(int i : iota(0, n)); // for(int i = n - 1; i >= 0; --i); と同等 for(int i : iota(0, n) | reverse);
これで REP マクロともおさらば…と言いたいところですが、タイプ数が多いのでおさらばしないひとも多そうですね。
でも range を使わない for ループよりははるかに良くなってると思います。
range view には iota, `reverse` の他にも filter, take, transform などが入る予定です。
終わりに
競プロであってもきれいなコードのほうがいいに決まってるので、使える機能はジャカジャカ使っていきましょう!
なお、この記事はかなり勢いで書いたため、推敲や誤字チェックなどは一切していません。
間違いを見つけたり、なにか気がついたことがあれば教えてください。
*1:というか、僕がよく使うやつ