えびちゃんの日記

えびちゃん（競プロ）の日記です。

C++ のコンテナやイテレータの罠

C++ を使うのが悪くて、Rust を使えばいいんじゃないですか？

これ系の記事を乱立させていて申し訳ないです（これこれの話ってどの記事？となりそうなので）が、罠が多い C++ 側に責任があるので、えびちゃんは悪くありません。 それに、一つ長い記事を書いたとしても人々は読まないと思うので。追記したときに差分を探すのも大変そうですし。

イテレータとはなんですか

イテレータをちゃんとは知らない人への説明を書きます。 ある程度 C++ のコードを書いたことがあるくらいのことは仮定しちゃいます。 この仮定がだめだったら、別で記事を書いてリンクを貼ります。

vector などのコンテナについて、その要素を指しているものです*1。 基本的には「次の要素を指して」「指している要素の値を教えて」のような操作ができます。

sort(a.begin(), a.end()); のように書いたことがあると思いますが、この a.begin() や a.end() などがイテレータです。 「a.begin() が指す要素から a.end() が指す要素（の直前）までをソートしてね」ということです。

書きました。書いたことにします。

イテレータの無効化

イテレータを取得して変数に入れたりしますね。

auto it = a.begin();
++*it;
cout << *it << '\n';

これなんですが、コンテナ a 自体に特定の操作をした場合、イテレータ it が無効になることがあります。 無効になったイテレータで操作した場合の動作は未定義です。

「未定義動作ということは実行時エラーになるんですか？」「これ見てね」

特定の操作というのが何かというのをいくつか紹介します。 コンテナの種類によって違いますが、コンテナ自体の実装に思いを馳せると想像がつくものも多いと思います。

無効化する操作

erase

次のように書くと、そのイテレータが指す要素を消すことができます。

auto it = a.begin();
a.erase(it);

消してしまったら無効になり、使うことはできません。 *it はもちろんのこと、++it などもできません。

メモリに値が残っていると、たまたまうまくいったように動くことはありますが、未定義動作とはそういうものです。

vector::push_back

まず、vector がどう実装されているか考えてみますか？ 動的な確保とかどうやっているんでしょう。 サイズ ii のとき i+1i+1 個の領域を新たに Ω(i)\Omega(i) 時間かけて確保するのを毎回やっていたら全体で Ω(n2)\Omega(n^2) 時間になってしまいそうですね。

実は vector には size 以外に capacity という概念があります。確保している領域の大きさです。 size == capacity のときに追加しようとすると領域が再確保されます。 元の capacity の 2 倍を新たな capacity とする実装が有名だと思います。 実はこれで償却 O(1)O(1) 時間になっているんですね〜*2。

で、push_back の際にこの再確保が起きると、全部の要素へのイテレータが無効になってしまいます。 起きたかどうかは capacity が変わったかどうかを見るとよいです（a.capacity() のように呼び出します）。 また、予めどのくらい増えるかがわかっているのであれば a.reserve(n) とすると capacity を n にできるので、増やす前に呼んでおくとよいです。

追記：capacity が変化しない場合、.end() のみが無効化されます。

vector::insert

あまり知られていないかもですが、vector には任意位置に要素を挿入する機能があります。 計算量は、挿入位置以降の要素数に対して線形です*3。

挿入位置以降の要素をずらしていくので、挿入位置以降の要素へのイテレータが無効化されます。 特に、.end() も無効化されます。

en.cppreference.com

それ以外の操作は、これの Iterator Invalidation の表を見るとよいです。

コンテナの罠

multiset は 前に書いた からいいですね。

set 系のイテレータの話も 書きました。

map も罠があります。[] でのアクセスは const ではありません。 map の中にあるキーが入っているかを確認するときに、次のように書くことがあります。 ただし、キーが入っているとき、それに結びつく値は 0 でないとします。

map<int, int> a;
if (a[x] == 0) 入っていない;

a[x] += y のように書くのができるように、キーが入っていなければデフォルト値で挿入されて、それが返ってくることになっているんですね〜。

それよりも、次のように書くのが無難でしょう。

map<int, int> a;
if (a.count(x) == 0) 入っていない;
if (a.contains(x)) 入っている; // C++20 から使える

あるいは次のようなことも書けます。C++17 からは if にも初期化文が書けるんですね〜（それ以前なら if の外に書いてください）。

map<int, int> a;
if (auto it = a.find(x); it != a.end()) {
  入っている; // it->second を書き換えたりできる
}

2 つめと 3 つめは要素数が変化しません。

nn 個の要素が入っている map に対して、n2n^2 回ループをしてこの処理を行うことを考えてみましょう。 （これは雑な議論ですが）log⁡(n2)=2log⁡(n)\log(n^2) = 2\log(n) なので、書き換えないものと比べて 2 倍ほど余分な時間がかかってしまいます。 map 自体が（ポインタ系のデータ構造ですし）定数倍が重いので、なるべくなら定数倍は軽く書きたいです。

余計な要素が挿入されるのを避けたいのは別の事情もあって、後述します。

要素が入っていることがわかっているときは a.at(x) でアクセスすると const なアクセスができます。

range-based for

これ〜〜。ループ中でコンテナに（主にサイズの変更が伴う）操作をすると大抵こわれます。

for (auto ai: a) {
  ねこ;
}

のようなやつです。ちゃんとした説明はリンク先とかを見てね。

en.cppreference.com

C++17 では以下のように書くのと等価でしょう（__ を含む識別子は我々用のものではないです）。

{
  auto&& __range = a;
  auto __begin = __range.begin();
  auto __end = __range.end();
  for (; __begin != __end; ++__begin) {
    auto ai = *__begin;
    ねこ;
  }
}

set で消すやつ

ループ中で a.insert(ai) などを書くと、__begin が無効になってしまいますね。 ということは、++__begin ができなくなるので、だめそうです。 諦めて次のように書くのがよさそうです。

for (auto it = a.begin(); it != a.end();) {
  if (消したい) {
    it = a.erase(it);
  } else {
    ++it;
  }
}

set で追加するやつ

ループ中で a.insert(x) を行い、今の __begin と __end の間に要素が入ると、ループの計算量が想定と変わってしまうことがありそうです。 具体的には、a の最大値 +1 などを挿入すると、__end に到達できなくなりそうです（実際には int などは有限なので、オーバーフローでこわれそうです）。

set では、insert をしてもイテレータが無効にはならないので、そこでの未定義動作は大丈夫そうです。

vector で前に入れるやつ

ループ中で先頭に要素を追加する状況を考えます。 いや、そんなことは滅多にしないと思いますが、こわすのは滅多にしない操作をしたときだと思うので、一応考えましょうね。

vector の insert では、挿入位置以降が無効化されるので、__begin がこわれて、未定義動作です。 __begin と言っていますが、現在指している要素ですね。

vector で後ろに入れるやつ

ループ中で push_back などを呼ぶ状況を考えます。

capacity が十分であれば問題ないはずです。 十分でなければ未定義動作でしょう。

__end はループ前に固定されるので、capacity の変化しない push_back では無効化されません。 また同様の理由で、ループ中に追加された値がこのループで走査されることもありません。

追記：ここ嘘で、.end() が push_back で無効化されるので未定義動作だと思います。

map の [] をするやつ

これ自体は未定義ではないですが、set の項目と同じ理由で無限ループになりえます。 なにが追加されているかに注意して書くか、別の書き方をしましょう。

おわり

そすうさに感謝

本番でそすうさが事故らせたらかなしい

*1:past-the-end などは「要素」は指していませんが...。

*2:最悪時は O(1)O(1) 時間ではないが、mm 回目までの時間の合計は O(m)O(m) であるということ。

*3:再確保が発生した場合はその分の時間がかかると思います。