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
がどう実装されているか考えてみますか? 動的な確保とかどうやっているんでしょう。
サイズ \(i\) のとき \(i+1\) 個の領域を新たに \(\Omega(i)\) 時間かけて確保するのを毎回やっていたら全体で \(\Omega(n^2)\) 時間になってしまいそうですね。
実は vector
には size
以外に capacity
という概念があります。確保している領域の大きさです。
size == capacity
のときに追加しようとすると領域が再確保されます。
元の capacity
の 2 倍を新たな capacity
とする実装が有名だと思います。
実はこれで償却 \(O(1)\) 時間になっているんですね〜*2。
で、push_back
の際にこの再確保が起きると、全部の要素へのイテレータが無効になってしまいます。
起きたかどうかは capacity
が変わったかどうかを見るとよいです(a.capacity()
のように呼び出します)。
また、予めどのくらい増えるかがわかっているのであれば a.reserve(n)
とすると capacity
を n
にできるので、増やす前に呼んでおくとよいです。
追記:capacity
が変化しない場合、.end()
のみが無効化されます。
vector::insert
あまり知られていないかもですが、vector
には任意位置に要素を挿入する機能があります。
計算量は、挿入位置以降の要素数に対して線形です*3。
挿入位置以降の要素をずらしていくので、挿入位置以降の要素へのイテレータが無効化されます。
特に、.end()
も無効化されます。
それ以外の操作は、これの Iterator Invalidation の表を見るとよいです。
コンテナの罠
multiset
は 前に書いた からいいですね。
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 つめは要素数が変化しません。
\(n\) 個の要素が入っている map
に対して、\(n^2\) 回ループをしてこの処理を行うことを考えてみましょう。
(これは雑な議論ですが)\(\log(n^2) = 2\log(n)\) なので、書き換えないものと比べて 2 倍ほど余分な時間がかかってしまいます。
map
自体が(ポインタ系のデータ構造ですし)定数倍が重いので、なるべくなら定数倍は軽く書きたいです。
余計な要素が挿入されるのを避けたいのは別の事情もあって、後述します。
要素が入っていることがわかっているときは a.at(x)
でアクセスすると const
なアクセスができます。
range-based for
これ〜〜。ループ中でコンテナに(主にサイズの変更が伴う)操作をすると大抵こわれます。
for (auto ai: a) { ねこ; }
のようなやつです。ちゃんとした説明はリンク先とかを見てね。
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
の項目と同じ理由で無限ループになりえます。
なにが追加されているかに注意して書くか、別の書き方をしましょう。
おわり
そすうさに感謝
そすうさが事故らせることでブログのネタができる
— えびちゃん (@rsk0315_h4x) 2020年8月9日
そすうさありがとう
本番でそすうさが事故らせたらかなしい