❌

イテレータの無効化 (C++)

2023/11/26に公開

C++

はじめに

C++ でコンテナを扱う際にはイテレータの習得が不可欠です。
イテレータはコンテナの操作によって無効になることがあるという話です。

イテレータとは

イテレータ (iterator) はコンテナ内の要素を指すオブジェクトで、よく「ポインタのようなもの」と説明されます。
実際、ポインタのように使えるように設計されていて、イテレータが指している要素を参照するには * 演算子が使えますし、今指している要素のひとつ先に進めるには ++ 演算子が使えます。
また、要素の型がクラスであれば -> 演算子でメンバを参照できます。

イテレータの必要性

初めて触れるコンテナが std::vector で、「動的にサイズを変更できる配列」と認識されている方 (多いと思います) は、「要素へのアクセスはインデックスですむのに、なぜわざわざイテレータなどというものを使うのか？」という感想を持たれるのではないかと思います。

std::vector だけを見ているとイテレータの必要性はわかりにくいのですが、標準ライブラリには C++20 時点で 13 種類のコンテナがあり、この中にはインデックスでアクセスできないものもあります (むしろインデックスでアクセスできるコンテナの方が少数派です)。
これはコンテナ内部の構造の違いに起因するのですが^[1]、どのようなコンテナであっても統一された方法で要素にアクセスできるようにするためにイテレータを使います。
独自の (構造の) コンテナを自作した場合でも、イテレータを適切に用意してあげれば、標準ライブラリに備わっている 100 を超えるアルゴリズムが適用できます。

この辺の話は、よろしければ以前の拙記事をご覧ください:

イテレータの無効化

イテレータを扱う際にはその無効化 (invalidation) を理解しておく必要があります。
イテレータオブジェクト自身は生存中なのに、それが要素を指していないのが無効な状態で、そうなるのが無効化です。

イテレータはポインタのようにコンテナ中のある要素を指しています。
何らかの要因でメモリ上の要素の位置が変わると、それまでその要素を指していたイテレータは無効となります。
ポインタで考えてみると簡単に理解できると思います。

イテレータが無効になってもそれが通知されるようなことはなく、イテレータを使って要素にアクセスする際に有効か無効かを知る一般的な方法もありません。
と言われるとイテレータの利用に不安を感じられるかもしれませんが、イテレータが無効化される条件は明確に規定されているので心配はいりません。

イテレータが無効化される条件

イテレータが無効化される条件はコンテナの種類によって異なります。
たとえばコンテナ中の要素を削除するケースを考えます。
std::vector のようなコンテナはすべての要素が連続したメモリ領域に配置されています。
そのため、要素を削除するとその後ろの要素を前に移動させてすき間を埋め、連続した状態を維持する必要があります。
その結果、削除した要素だけでなく、その要素より後ろの要素を指していたイテレータがまとめて無効化されます。

一方、要素が連続していない std::list のようなコンテナでは要素を削除してもそれより後ろの要素を指していたイテレータは無効化されません。

コンテナごとにイテレータが無効化される条件を覚えるのは大変のように思えますが、コンテナの内部構造を考えればある操作によってイテレータが無効化されるかどうかは推測できるので、実際にはそれほど難しくありません。

また、参考文献 [2] のような Web サイトにもまとめられているので必要に応じて参照するとよいでしょう:

このページによると、要素を削除した場合にイテレータが有効かどうかは次のように読み取れます (「Yes」が有効で「No」が無効):

std::vector
- Yes, Before modified element(s)
- No, At or after modified element(s)
std::list
- Yes, except erased element(s)

おわりに

本記事は、たまたま拝見したこちらの記事をきっかけに書きました:

こちらで期待どおりの動作にならない理由は、記事中で著者の方が説明されているように、 (std::back_inserter 関数テンプレートがインスタンスを生成する) std::back_insert_iterator クラステンプレートが std::vector::push_back メンバ関数を呼び出し、それが既存のイテレータを無効化するからです。

std::vector クラステンプレートのイテレータが無効化される条件は、規格では次のように規定されています (参考文献 [1] の p.935, 24.3.11.5 Modifiers [vector.modifiers], paragraph 2):

Remarks: Causes reallocation if the new size is greater than the old capacity. Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence, as well as the past-the-end iterator. If no reallocation happens, then references, pointers, and iterators before the insertion point remain valid but those at or after the insertion point, including the past-the-end iterator, are invalidated.

reallocation が発生しなければ、挿入された位置より前の要素を指すイテレータは無効化されません。
このケースでは事前に reserve しておけば最初のコードでも問題ないはずです。

参考文献 [2] の Web サイトでも同様に説明されています:

push_back (や emplace_back) 操作の場合は、 Invalidated

If the vector changed capacity, all of them. If not, only end().

参考文献

N4950: Working Draft, Standard for Programming Language C++
https://open-std.org/jtc1/sc22/wg21/docs/papers/2023/n4950.pdf
cppreference.com
https://en.cppreference.com/w/

脚注

コンテナの内部の構造の違いは、コンテナに求められる特性の違いによります。 ↩︎