えびちゃんの日記

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

競プロで踏みがちな C++ の罠

定型文

この記事は Competitive Programming (1) Advent Calendar 2019 の 17 日目の記事です. adventar.org

まえがき

えー,未定義動作という言葉を知っていますか?

必要に応じて 昔の記事 を読むといいかもしれません.

C++ を書く上でよく「環境依存」という言葉を聞くかと思いますが,これは C++ 用語ではなく,俗語です. それが使われる文脈での適切な用語は「処理系定義」「未規定」「未定義」などです(状況に応じてどれかが選ばれます).

基本的に,未定義な動作になるコードを書いた場合,どうなるかがわからなくてつらいんですが,今回はそういう話には触れない予定です.

競技プログラミングの上では,(特にコンテスト中なら)未定義であってもジャッジでうまく動いて AC すれば丸く収まるためです. (もちろん,次に同じようなコードを書いてうまく動く保証はないので,未定義なコードを書くのに慣れるべきではないです.)

今回は,ハマると原因に気づきにくいようなものに焦点を当てていきたいです. 未定義動作が原因であるものだけでなく,仕様の勘違いなどが原因のものにも触れます*1

中級者以上でもハマりそうなものを挙げます.

未定義動作

いつもの.

コンパイラちゃんがすきにしちゃっていい最適化の話を見たい人は上のリンクを踏んでください.

一つ注意点として,たまに「いついつの規格までは未定義だったが,いついつ以降は定められた」のようなものがあります. コンパイラは「未定義ならば何をしてもいい」ので,新しい規格に対応しているコンパイラは,(おそらくコンパイラの実装を楽にするためなどの理由で)古い規格のオプションをつけても新しい規格で定められた挙動になることがあります.

「未定義だからおかしい挙動を示すはず」と思う癖はなくしていきましょう.さすがに聞き飽きられたかもしれないですけど.

配列外参照

配列外参照などで想定外の場所が書き変わる*2と,アルゴリズムが想定通りに動かなくなって無限ループになったりすることはありえます. TLE であってもとりあえず配列外参照などを疑うのは無駄ではないでしょう.

配列外参照が RE になると思っていた人は 昔の記事 も読むとよいかもです.

こわれたイテレータ

えー,イテレータというのを知らない競プロ er もいそう.

begin() とか end() とかをしたときに返ってくるやつです. 知らなかった人は APG4b などを見てみましょう.

atcoder.jp

betrue12.hateblo.jp

コンテナに特定の操作をすると,それまで取得していたイテレータや参照がこわれることがあって,こわれたものを使うとこわれます.

たとえば,vector は可変長配列として使えますが,次のような罠があります.

std::vector<int> v{10, 20, 30};
auto xxx = v.begin() + 2;  // 30
auto it = v.erase(v.begin()+1);  // v == {10, 30}

このような操作の後,*xxx は未定義動作になってしまいます. vector では,erase() した場所以降のイテレータはこわれてしまいます.

std::vector<int> v{10, 20, 30};
auto xxx = v.begin();
for (int i = 0; i < 20; ++i) v.push_back(i);

また,このような操作の後も,*xxx が未定義になることがあります. vector では,size() の他に capacity() と呼ばれる大きさがあります.

push_back() などの,大きさが変わる操作の結果,capacity() < size() になると,領域が再確保されます.その結果,それ以前に作っていたイテレータはこわれてしまいます.

n まで必要になるときは,あらかじめ reserve(n) をしておくと,こうしたことを防ぐことができます.

こわれる詳しい条件は ここ とか 英語版 とかに書かれています.

もう一つ例を挙げてみます.

std::set<int> s{10, 41, 50};
for (auto x: s) {
  if (x % 2 == 1) s.erase(x);
}
std::set<int> s{10, 41, 51};
for (auto it = s.begin(); it != s.end();) {
  auto x = *it;
  if (x % 2 == 1) {
    it = s.erase(it);
  } else {
    ++it;
  }
}

range-based for は内部的にはイテレータを使っているので,今指しているイテレータがだめになるとだめになっちゃいます.

for (auto x: s) {
  auto it = s.upper_bound(x);
  if (it != s.end()) s.erase(it);
}

とかは大丈夫そうな気がするような.

また別の例も出します.

std::vector<int> v{1, 2, 3, 4};
v.push_back(v[0]);

v.push_back の引数の型は int const& なんですが,上で述べた capacity() < size() になるとき,参照 v[0] がこわれちゃいます.そのため,こわれちゃうことがあります.

解決策としては,v.reserve(/* 十分大きい要素数 */) をするとか,v.push_back(int(v[0])) にするとか,とかとかです.

比較関数

比較関数はちゃんと「比較」をしましょう. a < b かつ b < a が真になるとこわれます.

RE になったり TLE になったり WA になったりなんでもありえます.

std::sort(v.begin(), v.end(), [](auto, auto) { return true; });

最適化オプションを変えると別の挙動になったりして楽しいです.

ラムダの引数を auto にできたり,使わない引数名を省略できるのは覚えておくとうれしいかも?

struct neko {
  bool foo;
  int x;
  bool operator <(neko const& other) const {
    if (foo) return true;
    return x < other.x;
  }
};

footrue であるような対 x, y が存在する場合,x < yかつ y < x になって,こわれてしまいます.自作クラスを作る場合は注意しましょう.

両方が false になる場合は問題ありません. a = b = 1 について !(a < b) && !(b < a)true ですね.

このように,STL の関数に渡すものには要件が課されていたりしますが,それを満たさないものを渡すと未定義動作になっちゃいます.

これを未定義としない場合,要件を満たしていないことを処理系ががんばって検出するなどの手間がかかってしまうはずですね.実行速度の無駄な低下につながりかねません.

プログラムの書き手であるところの我々が責任を持つ必要があります.

評価の順序

en.cppreference.com

たくさんあって覚えられません. ここで言っていることは,「ある処理はある処理の後に行われることが規定されています」とか,「ある処理とある処理の間にはそういった順序は定められていません」ということです.

たとえば,x = 0; y = 0; と書いた場合,y = 0x = 0 より後に行われることが規定されています. 一方,x = f() * g() + h(); などと書いた場合,f, g, h のどれが最初に呼び出されるかなどは未規定です.演算子の優先順序と呼び出し順は別の話であることに注意してください.

次のようなのは(C++17 未満では)こわれますが,度々これを書く人を見かけます.

map<int, int> m;
m[x] = m.size();

map では,(これはおそらく知っているでしょうが)[x]x が存在していない場合,新しく要素が追加されます. その結果,m[x] を評価する前の m.size() と後の m.size() では値が変わりえます.

仕様の勘違い

未定義ではないですが,バグや計算量の嘘見積もりに関連するものです.

std::lower_bound

定数時間でランダムアクセスができないイテレータをこれに渡すと線形時間かかっちゃいます.

rsk0315.hatenablog.com

std::multiset

multiset で,複数個入っているうちの一つを消そうとすることを考えます. 間違ったやり方をすると全部消えちゃいます.

rsk0315.hatenablog.com

整数の大きさ

Codeforces の環境は longsize_t が 32-bit なので,64-bit だと思っているとこわれます.

これは「環境依存」のうち処理系定義と呼ばれるものです. 処理系定義は,コンパイラのマニュアルなどに記載があることが保証されています.未規定はそうではありません.

補足:例えば,STL のクラスの private メンバ変数の名前などは未規定です.記載する意味がほぼないですからね.

コンパイル時定数

int n;
scanf("%d", &n);
std::bitset<n> a;

<> の中はコンパイル時に決まってなきゃなのでこれはできません.

std::string

コンストラク

std::string(c, n) とかいう気づきにくいやつ.

大きさが先にくるのは std::vector と同じです.

std::valarray とかいうやつは逆なんですけど,どうして...?

計算量

また,文字を付け加えていくことを考えます.

std::string s;
for (int i = 0; i < n; ++i) {
  s = s + 'a';  // (1)
  s += 'a';  // (2)
  s += std::move(s + 'a');  // (3)
  s += std::move(s) + 'a';  // (4)
}

(2) と (4) は速くて,(1) と (3) は遅いです.

文字列がコピーされちゃうんですね.string のこれらに関する計算量規定は規格書中に見当たらないんですけど...

アクセス

std::string s(n); に対して s[n] でアクセスしても未定義にはなりません,0 が返ってきます.助かりますね.

0 以外でこれを書き換えると未定義です.

スペース区切りの入力

次のような入力をもらうことを考えます.

hoge fuga piyo
std::string s;
std::cin >> s;

これでは hoge しかもらえません.getline などを調べてみましょう.

符号なし整数

v.size() で返ってくるのは size_t 型です. これは,コンテナの大きさを表すのに十分大きい符号なし整数型の別名です. unsigned long などです.

符号なし整数と符号あり整数を比較しようとすると,まず型変換が起こります. 比較される整数の大きさの関係によって,符号なしか符号ありのどちらかに合わせられます. このルールは複雑なので,覚えられると思わない方がいいでしょう.

そんなわけなので,コンパイル時に符号の有無の異なる整数同士を比較しようとすると警告を出してくれます*3

std::vector<int> v;
// いろいろ操作する
for (int i = 0; i < v.size()-1; ++i) v[i+1] += v[i];

これは,v.size() == 0 のとき,こわれます.

まず,i < v.size()-1 の部分について,v.size()-1size_t(-1) です. 型変換のルールの結果,size_t(i) < size_t(-1) となります. size_t(-1) はめちゃ大きい整数値になるので,無限回*4のループが回り,v[i] でまずいところにアクセスしちゃいます.

for (int i = 0; i+1 < v.size(); ++i) ...  // 警告は出る
for (int i = 0; i < int(v.size())-1; ++i) ...  // 警告なし
for (size_t i = 0; i+1 < v.size(); ++i) ...  // 警告なし

警告が出るというのは,警告を出されるようなことをしてしまっているということなんですよね.

特に異符号モノを無視する人は多い気がするのですが,「今までも大丈夫だったし」で無視していると,予期しない罠を踏んだりするので気をつけましょう.

size_t は逆順ループの際にも注意が必要です.

for (auto i = v.size()-1; i >= 0; --i) ...

などをすると継続条件が常に真となり,こわれちゃいます.

(停止性判定が難しいことなどの理由から?)(特定の副作用がある場合を除き)コンパイラは関数が return することを仮定できます. そのため,その条件を満たすときは未定義な動作となります.(もちろん,その結果無限ループになることもあります.)

よく用いられるイディオムは次のようなものです.

for (size_t i = v.size(); i-- > 0;) ...

どうしてうまく動くかは読者への課題としてみます.

bool

boolint などに変換されるとき,true なら 1 に,false なら 0 になります.

#include <cctype>

std::string s = "12345";
bool aredigits = true;
for (auto c: s) aredigits &= isdigit(c);

これをした後,aredigitsfalse である場合があります. 数字を引数にしたときの isdigit の返り値は「0 以外」としか規定されていないので,たとえば 1 のビットが立っていない値だった場合,こわれてしまいます.

isalphaislowerisupperisdigit などに,それぞれ別のビットが割り振られている処理系もあります.

bool valid = true;
int mask = 9;  // 1001
int i = 3;
valid &= (1 << i & mask);

これも同様の理由でこわれたりします.

valid &= (mask >> i & 1);

の方がおすすめです.

比較の等価な場合

!(a < b) && !(b < a) による等価性は equivalence,a == b による等価性は equality と呼ばれ,分けられています.

ここでは,equivalent が equal を意味しない自作クラスなどを考えます.

struct neko {
  int x, y;
  bool operator <(neko const& other) const {
    return x < other.x;
  }
  bool operator ==(neko const& other) const {
    return x == other.x && y == other.y;
  }
};

さて,std::min(a, b)std::max(a, b) などの式において,ab が equivalent なとき,a が返ってきます.そのため,次のようなコードはそうした状況下で意図に反することがあります.

neko min_ab = std::min(a, b);
neko max_ab = std::max(a, b);
// min_ab.y と max_ab.y が意図に反して同じになることがある

std::minmax というのが便利かもしれません.

neko min_ab, max_ab;
std::tie(min_ab, max_ab) = std::minmax(a, b);

これは,二つの返り値が別々になることが保証されています.

ところで C++17 で導入される structured bindings があると次のように書けて便利です.

auto [min_ab, max_ab] = std::minmax(a, b)

あとがき

まともに勉強もせず,未定義動作を踏んだり意図に反したときだけ C++ に文句を言うの,好ましくないですよね.

勉強をしていても踏んじゃうんですけどね.

おわり

にゃんにゃ.

*1:未定義動作を認識していないのも,仕様の勘違いではあるんですが.

*2:想定外参照というフレーズが流行ると面白そう.OutOfExpectationException.

*3:出してくれない処理系をお使いですか? 警告をよく出してくれる処理系を使うといいですよ.

*4:この無限はオタクの無限? 配列外参照の時点で未定義なので,真の無限回にならないとは言えなさそう.