追記(2020-10-25): コーディングスタイルについてを 競技プログラミングにおける個人的 C++ コーディングスタイル (2020) - うさぎ小屋 として書き直しました。好みについての主張は 5 年も建てば多くが変化するためです。こちらも併せて読んでください。

コーディングスタイル的な話。 基本はC++に関して特に競プロ特有のものを中心に列挙した。

一言でまとめると「きれいなコードはバグがでにくい」である。 好き嫌いはあるだろうが、以下を守って損をすることはほぼないはず。

体裁を整える

コードが見にくいとバグを見落とすので:

  • indentはちゃんと整える
  • spaceとtabは混在させない
  • 演算子等の間には適当にspaceを入れる

同様の理由でeditorはsyntax highlightがあるものを使う。

テストケースで確認する

サンプルケース等による確認が、コマンド一発でなされるようにする。コンパイル成功毎に実行する。 考えている際に紙に書いた例等は全てテストケースとして追加しておく。

簡単にやるには、以下のようにファイルに保存し、

  • test/sample-1.in
  • test/sample-1.out
  • test/sample-2.in
  • test/sample-2.out
  • test/sample-3.in
  • test/sample-3.out
  • test/your-case-1.in
  • test/your-case-1.out
  • test/your-case-2.in
  • test/your-case-2.out

以下のように叩くとよい。

$ for f in test/*.in ; do ; diff <(cat $f | ./a.out) ${f%.in}.out ; done

ちゃんとやるにはツールを入れる。 いくつか選択肢はあるが、拙作のkmyk/online-judge-toolsをおすすめしておく。

  • Topcoderの場合は適当なpluginを入れる
  • 入力ケースの生成器と愚直解や部分点解を用いてテストケースを大量生成し比較すると、バグの再現例の発見が容易
  • 十分なテストケースがある場合のoff-by-one error等であれば、テストが通るまで適当にコードを弄るだけで勝手に解決してくれる

repeatマクロを使う

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)

の類。必須。

便利というより、普通のforがあまりにも危険。

for (int i = 0; i < n; ++ i) { ... }

という最も基本的な形でさえiが3回出現し、これを全て揃えなければ即バグになる。 また、REPで導入されたloop counterはloopの内部で変更しないと約束しておくと、通常のforが現れたときに何かloop counterや終了条件が特殊だと分かりやすくなるという副次効果もある。

文字数の削減は特に目的ではないので、私はREPではなくrepeatとして以下のように定義して使っている。

#define repeat(i,n) for (int i = 0; (i) < (n); ++ (i))

同様の理由でrange-based forで書けるならそちらを使うべき。

競プロ以外ではboost::irangeを使うべき。 ちなみにこの手のfor文をwrapするマクロはC言語だと良く使われていて、(整数の上を動くものはないとはいえ)例えばLinux Kernelのコードをdefine.*for_eachでgrepすると$700$以上見付かる。

allマクロは使うならいい感じに

ALLとかWHOLEとかの名の、<algorithm>の関数にいい感じにコンテナを渡すマクロに関して。 使用するなら以下のようにするとよい。

#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)

int acc = whole(accumulate, xs, 0ll);のように使う。 sort(a.begin(), b.end());のようなミスは怖いので、積極的に使う価値はある。 変数名にwholeを使っているのは衝突しなさそうな名前であるため、decltype((x))は参照で受けてかつC++11でも動くものであるためである。

一方で、以下のようなものはよくない。

#define ALL(a) (a).begin(), (a).end()

これはコンテナaが2回別々に評価されてしまう。 たとえばsort(ALL(field[y++]))のようなことをするとバグになる。 これはコーディングの傾向にもよるが、こちらのマクロであれば総合的に見てわざわざ使うほどではないように感じる。

もちろん競プロ以外ならboostのrange algorithmsを使うべき。

std::vectorを使う

可変長の変数の列が必要なときはstd::vectorを使う。

    int n; cin >> n;
    vector<int> a(n); repeat (i,n) cin >> a[i];

領域は過不足なく確保する。 これはなんらかの間違いで使用されるはずのない領域を使用していた際、-D_GLIBCXX_DEBUG等による検査や単にsegmentation faultなどの形で発覚することを期待している。

vector<int>a(n);とするとちょうどn個分領域が確保されて、以降push_back等で領域が足りなくなれば、現時点の倍の量を再確保する。

以下のように必要な個数+3ぐらいを確保している人は多いが、これだとそのような場合にも落ちてくれない。

int n;
int a[100003];

stackを食い潰すことがなくなるので、global変数にする必要がなくなるという利点もある。 静的領域であってもとても大きい場合は問題が発生し、結局heap領域に取る必要はある。

なお、例えばint a[1003][1003];がvector<vector<int> > a(h, vector<int>(w));になってしまうので文字数は増えるが、これには目を潰ること。適切に関数やtypedefを置いてもよい。

変数のscopeは出来る限り小さく

一般に言われていることである。 これを守った場合必然的に、global変数は実質禁止になる。 再帰関数が必要なときにもglobal変数は使わず、lambda式を使って解決する。

特に問題になるのが入力が複数データセットからなる問題。 ICPCやGCJでは全てこの問題形式である。 毎回の初期化に漏れがあるとバグになる。 なお、メモ化再帰のメモを関数内静的変数で取るのも同様に危険なので注意すること。

また、余裕があるなら{ } でscopeを適切に切って使い終えた変数は削除していくようにするべき。

変数が未初期化のままの距離を最小に

未初期化の変数は危険であり、この距離を最小化するのも必要である。 変数は必ず宣言した行で初期化するようにすると安全。 例えば以下のようになる。

int main() {
    int n; cin >> n;
    int x, y; cin >> x >> y;
    ...
}

assertを使う

バグが埋まっているなら即座にそう検出されるようにするべき。 正しさが保証されているコメントとしても使う。

例えば割り算をする際必ず割り切れることが分かっているなら、以下のように書く。

    assert (acc % n == 0);
    int ans = acc / n;

assert側が間違っていて他は正しいのに提出した先で引っかかって落ちたという事故の可能性はあるが、利益の方が大きいので書くべき。 もちろん提出先では無視されるようにしてもよい。

再利用性の高いコードを書く

関数名をきっちり付けコメントを多めに書いておくとよい。 単純にコードが読みやすくなるのでバグも出にくくなる。

また、そのようにして解いたコードを貯めておくと次似た問題に当たったときに再利用ができる。

using namespace std は使う

競プロに限れば避ける理由は特にないと思う。

ただしstd::leftとかstd::distanceと名前衝突させないようには注意すること。

コンパイラに頼る

諸々のオプションはとても便利。私は以下のそれぞれを適当にaliasして使っている。

$ clang++ -std=c++14 -Wall -g -fsanitize=undefined -D_GLIBCXX_DEBUG
$ clang++ -std=c++14 -Wall -O2
  • -Wallは警告を多めに出す
    • 最適化の有無に関わらず付ける
    • 警告を無視してはいけない。ちゃんと潰そう
  • -gはdebug用の付加情報を載せる
  • -fsanitize=undefinedは未定義動作の検出
    • 整数のoverflowが発生したときとかを教えてくれる
  • -D_GLIBCXX_DEBUGはC++のSTLのあたりのdebug用機能の有効化
    • vectorの範囲外アクセスとかを教えてくれる

警告は全て対応すること。

その他コーディングに関する事

まとめて簡単に:

  • 名前は適切に付ける
    • 長ければよいというものでもない
    • 競プロなら、適当に関数を切れば全て1文字変数でも十分だったりする
      • Haskellの命名文化や数学の記号の置き方に近い
  • if文やfor文のbrace{ }は省略しない
    • 単一の文で改行を挟まない場合は除く
  • std::pairとかで何でもやるのは避け、構造体を定義する
    • 読みやすさはバグのでにくさに繋がる
  • && || !でなくand or notの代替表現を使う
    • 特に!は1文字で目立たないので避けたい
    • 優先順位等の差は一切ないので全て置き換える
  • コメントは適宜付ける
    • 例えばint l, r;を宣言したら、後ろに // [l, r)とか書いておく
    • 例えばint i;が$1$-basedなら、後ろに // 1-basedとか書いておく
    • 空行を入れたくなったら、空行を入れる位置にひとこと書いておく
  • cin coutは遅い場合があるのに注意
    • 始めから全てprintf scanfで書くのが競プロにおいては安全かもしれない
  • ちゃんと標準error出力使う
    • pipeに流せないし、消し忘れるとWA

適切な言語を選択する

計算量に余裕なある問題の場合、C++ではなく別の言語を選択すべきことも多い。 基本はC++でサブウェポンとしてPython(or Ruby)を使い、その他も状況に応じて使っていくべき。

  • C++
    • 実装が重い場合、型等があるため読みにくくなりにくい
    • 配列の扱いが非常に上手い
    • 定数倍が軽い。全力を出せば愚直解を押し通せることも
  • Python
    • 実装が軽い場合、行数が短く読みやすい
    • 多倍長整数
      • overflowの心配がなくなる
    • numpyやscipyが使える場合も

競技プログラミングでコーディングの際気を付けていること

更新履歴:

  • Sat Sep 26 14:30:50 JST 2015
    • 反応を見ていくつか追記
    • 書き忘れてたの追記
  • Wed Jun 15 00:53:20 JST 2016
    • allマクロはありな気がしてきたので書いた
    • compiler optionの話をしてなかったのに気付いたので、した
    • ついでに適当に微調整
  • Mon Oct 24 11:33:19 JST 2016
    • paradigm_9さんからwhole macroの変数yの衝突しそうという指摘を貰ったので修正。感謝
    • ついでにいくらか修正
  • Mon May 15 17:59:45 JST 2017
    • 全面修正
    • 無駄な文章を積極的に削除
  • Mon May 15 22:32:36 JST 2017
    • 書き忘れ追記
  • Sun Oct 25 07:59:33 JST 2020
    • コーディングスタイルの記事への誘導を追加