えびちゃんの日記

えびちゃん(競プロ)の日記です。

競プロ C++ イディオム FAQ

今までいろんな人に何回も説明した内容は、これからも何回も説明することになりそうなので、記事としてまとめておいてみます。 自分としてもこの記事へのリンクを貼ればよい上、読んだ人が(辞書で隣の単語もまとめて覚えるみたいな感じで)別のことも知れたらよさそうだと思ったので。

「これはこう書けるよ」系の紹介をするのではなく、「このおまじないがわかりません」系の解説をしたいと思っています。

わからないことがあれば、#助けて競プロer のタグでツイートするか、PROCON-QA で質問するといいと思います。 よく見る質問については追記しようと思います。直接えびちゃんにリプライしてくれてもいいです。


以下では std:: をつけて表記しますが、using namespace std; などをしている人は、(ここで紹介されたイディオムを書く際に)省略して構いません。 たとえば、std::cincin と書けます。

↑これはわざわざ明記しなくてもいい気もしたんですが、std:: を見たことすらない状態で using namespace std; をおまじないとして使っている人にとっては非自明かもしれないと思ったので。

説明が必要そうな用語については、一番下のセクションでカバーできるように努力します。

「この文はどういう意味ですか」系

std::cin.tie(nullptr)

標準入力からの読み取りをする std::cin は標準出力へ書き込みをする std::cout に結びつけられて (tie) います。 この状態では、std::cin から読み込みをするたびに std::cout が flush されます。 flush は比較的重い処理なので、入力のたびにそうした重い処理をさせるのを防ぐための文です。

tie の引数は結びつけられる出力ストリームへのポインタです。 nullptr を渡すことで、どのストリームも結びつけられていない状態にできます。 何かしらの理由でデフォルトの状態に戻したい場合は std::cin.tie(&std::cout) をするとよいです。

std::cin.tie(0) でも std::cin.tie(nullptr) と同じ動作をしますが、ポインタを渡しているように見えやすい後者の方を推します。

en.cppreference.com

flush の説明は下に書くとして、tie(nullptr) な状態だと次のような感じになります。

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << "整数を入力してね\n";
  int n;
  std::cin >> n;
  std::cout << n << '\n';
}

std::cin の入力待ちの際に「入力してね」のメッセージが出力されないため、困ってしまいます。 なんですが、競プロの文脈ではこうしたメッセージを出力する必要はないですから、tie させておく理由はないでしょう。

std::ios_base::sync_with_stdio(false)

C の <cstdio> での入出力(典型的には scanf/printf など)と C++<iostream> での入出力(典型的には std::cin/std::cout)がありますね。

C++ の入出力と C の入出力が混在してもこわれないように同期が取られているんですが、これを呼ぶことで各々を独立に扱うようになります。 C++ 側の入出力クラスが、勝手にバッファしたりできるので高速になったりすると思います。

en.cppreference.com

while (std::cin >> n, n)

AOJ でよく見ますね。複数のテストケースを一回の実行で処理する場合のイディオムです。

この , はカンマ演算子と呼ばれるもので、a, b は「a の後に b を処理して、b を返す」ものです。 標準入力から整数を読み、それが 0 でない限りループする、という文です。整数を bool に変換すると 0 のとき false、それ以外のとき true になります。

ところで、えびちゃん的には、複数のテストケースはループよりも関数で処理した方がバグらせにくいと思っています。 初期化忘れや変数名の衝突を防げたり、多重ループの途中で処理を終えたら return 0; で抜けられる(余計なフラグ変数などを増やすことによるバグを防げる)などがメリットです。

int testcase_ends() {
  if (入力終わり) return 1;
  処理をがんばる
  return 0;
}

int main() {
  while (!testcase_ends()) {}
}

返り値については、単一テストケースの場合の main と揃えています。

while (std::cin >> n)

std::cin >> n が真である限りループする」なんですが、std::cin >> n の真偽がおまじないだと思います。

std::cin >> n >> m という書き方ができることをイメージするとわかりやすいと思うんですが、std::cin >> nn を読んだ後の std::cin 自身を返します。 よって、上のループは次のループと同じです。

while (std::cin >> n, std::cin)

そこで、bool(std::cin) が何かなんですが、読み込みに失敗していたら false になります。 失敗というのは「入力の末尾に達した」とか「整数を読みたいのに整数でないものを読んだ」とかです。

en.cppreference.com

すなわち、入力に失敗するまでループを継続します。

std::cout << std::fixed << std::setprecision(16)

デフォルトでは浮動小数点数は 6 桁くらいしか表示してくれないので、誤差に厳しい問題では望み通りの値が出力されません。 そこで、std::setprecision で所望の桁数を指定することでそれを解決しています。

std::fixed固定小数点数として表示するもので、0.0000000011e-09 のように出力されるのを防ぎます。

en.cppreference.com

while (scanf("%d", &n) != EOF)

動作自体は while (std::cin >> n) に似ています。

scanf にも返り値があり、読み込みをした個数を返します。 ただし、1 個も読めずに入力の終端に到達した場合は EOF を返します。

(注)%d で読み込む場合、入力が "a" の場合は 0 が返りますが、"" の場合は EOF が返ります。

よって、(入力の形式が想定通りという仮定の下で)整数の入力がある限り処理を続けることになります。

while (~scanf("%d", &n))

EOF の値は処理系定義で、負の値であることしか定められていませんが、-1 であることが多いです。 さらに、負数は 2 の補数表現を用いて表す処理系が多い(そのうち処理系定義ではなく規格でそうなりますが)ので、ビット反転の演算子 ~ を用いることで、上の != EOF を短く書けるというものです。

(個人的には)あまりすきな書き方ではないです。

#define _GLIBCXX_DEBUG

デバッグ機能を有効にします。GCC で使えます。 std::vector で配列外参照をした場合、普通は未定義動作(実行時エラーとは限らない)なのですが、これをしていると実行時エラーになってくれます。 std::vector 以外の STL の各コンテナにおける多くの未定義動作を実行時エラーにしてくれて、バグの存在を知りやすくなります。

「これはどうしてだめなんですか」系

std::cout << std::endl

まず、<< std::endl を「改行する(だけ)」として認識されているのがよくなさそうです。

改行した後に flush を行います。なので重くて、TLE したりします。

#define int long long

A translation unit shall not #define or #undef names lexically identical to keywords

と規格に書かれているからです。未定義動作でも動けばいいと思っている派閥の人は好きにしたらいいと思います。 GCC では許されているらしいです。ソース

デバッグしてほしい」と他人にコードを見せる際は行わない方が無難です。 これをしていない人にとっては読みにくいことが多いので。

std::set に対する std::lower_bound

\(O(\log(n))\) 時間で行えないからです。\(O(n)\) 時間になります。

過去に詳しめの記事を書きました。

rsk0315.hatenablog.com

std::multiset に対する .erase(x).count(x)

過去に詳しめの記事を書きました。

rsk0315.hatenablog.com

ループ中での std::ios_base::sync_with_stdio(false)

入出力をしてからこれを読んだ場合、(処理系定義ですが)バッファが破棄されたりすることがあるので、こわれる場合がありそうです。

while (std::cin >> n) が手元でうまくいかない

うまくいっています。

前述の通り、これは「失敗するまで入力を行う」ので、入力を失敗させてやる必要があります。 具体的には、入力終端 (EOF; end of file) を送ってあげる必要があります。

方法は簡単には二つあります。

入力をファイルにしてしまって、そこから読み込む方法です。

$ ./a.out < sample.in

Windows のシェルだとできないかも?

あるいは、EOF をキー入力で伝える方法です。 「Ctrl+Z を押して Enter」か「Ctrl+D」でできると思います。シェルによります。

#define _GLIBCXX_DEBUG

そもそもデバッグ用の機能であることを意識しましょう。

std::vectoroperator [] などでは、境界チェックを行うので定数倍が重くなります。 一方で、std::lower_bound など、前提条件のチェック(二分探索が可能か?)に線形時間かかるものは、全体のオーダーも悪化しうるので、注意が必要です。

sort の比較関数にメンバ関数を渡す

蟻本にある接尾辞配列をクラスの形で実装しようとする人がほぼ陥るやつです。

渡せないことになっているからです(なんで?)。

static のついたメンバ関数であれば渡せますが、そうした関数はインスタンスに関係なく呼び出せる必要があります。 すなわち、メンバ変数(今回の例における rank など)は参照できません。

よって、今回の例においてメンバ関数を用いるのは適当ではなさそうです。 ラムダ式を用いて rank をキャプチャしてしまうのが楽でしょう。

std::sort(sa.begin(), sa.end(), [&](auto i, auto j) {
  // rank などを用いた比較を書く
});

「なんでこう書く必要があるんですか」系

重複を取り除くやつ

a から重複を取り除くときのイディオムとして、次のものがあります。

std::sort(a.begin(), a.end());
a.erase(std::unique(a.begin(), a.end()), a.end());

std::unique は、「連続する値について、重複していたら先頭以外を取り除く」ことをします。 ここで言う「取り除く」というのは、後ろの方に追いやることを意味します。

なので、たとえば "abcbbcaaabb""abcbcabxxxx" になります。 xxxx の部分は未規定な値になります*1

std::vector 以外にも使えます、念のため。)

予めソートしておくことで、すべての重複を除いて "abcxxxxxxxx" にできます。

std::unique を呼ぶだけで "abc" にしてほしい」と言いたげな人がたくさんいると思うんですが、それは無理というものです。 std::unique に渡す引数はコンテナではなくイテレータなので、関数側からコンテナ自体の大きさを変えることができないためです。

さて、std::unique の返り値は、上の説明の x の開始位置を指すイテレータです。 そこで、その位置からコンテナの末尾までを消すことで、所望の結果を得ます。

std::next_permutation の前の std::sort について

a の全順列についての処理をするイディオムとして、次のようなものがあります。

std::sort(a.begin(), a.end());
do {
  a についての処理
} while (std::next_permutation(a.begin(), a.end()));

next の部分に注意して読みましょう。 この関数は、与えられた範囲について、辞書順で次に大きい順列にして、true を返します。 辞書順で一番大きいものを渡した場合は、辞書順で最も小さい順列にして false を返します。

なので、辞書順で一番小さいところの、sorted なものから始めることで全順列を生成できます。

en.cppreference.com

知られてなさそうなんですが std::prev_permutation もあります。

rep マクロを使っている人にとっては、sort するよりは 2 回繰り返す方がタイプ数が短そうですね。

rep(2) do {
  がんばる
} while (std::next_permutation(a.begin(), a.end()));

最大値を求める場合はそれでいいですが、数え上げの場合はこわれるのでおすすめしません。

「この用語はどういう意味ですか」系

flush

標準出力に何かしらを書き出す処理をしたとしても、その時点で実際に出力が行われるとは限りません。

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cout << "one\n";
  時間のかかる処理
  std::cout << "two\n";
}

onetwo が同時に出力されたりすると思います。

バッファリング (buffering) とか呼ばれていて、出力内容をためておいて必要になったらまとめて流す (flush) ようになっています。 flush は重めの処理です。読むといいかも

'\n' の代わりに std::endl を流すと同時でなく出力されたりすると思います。

競プロの文脈では(インタラクティブでない限り)、最終的に全部出力されていればよくて、この時点でどうだったとかは関係ないので、std::endl を使う理由はあまりないでしょう。


とりあえずおわり。

何かあれば追記します。

*1:アクセスするの自体は許されています。