イテレータの無効化（iterator invalidation）とは、イテレータ（C++）が有効な要素を指していない状態になることである。
イテレータ（C++）はポインタのようにコンテナ中の要素を指す。したがって、コンテナへの操作によって要素の位置や内部構造が変わると、既存のイテレータ・参照・ポインタが無効になることがある。
発生しうる条件の例
std::vector
- 要素を削除すると、その要素より後ろの要素を指すイテレータが全て無効になる。
- 要素を削除すると、連続構造を維持するようにその後ろの要素を詰める（移動させる）ため。
ループ中操作による無効化
ループ内でコンテナ構造を変更した結果、次の周回でのイテレータの無効化を発生させてしまうと、実行時エラーや不正な動作の原因となる。
ループ内で要素の挿入や削除など、コンテナの構造を変更する操作を行う場合は、遅延
具体例
range-for 中の push_back
for (auto& e : m_entities)
{
if (/* 条件 */)
{
m_entities.push_back(newEntity);
}
}このループでは、各周回で e は m_entities 内の要素への参照である。
ここで push_back によって capacity を超えると、std::vector はより大きなメモリ領域を確保し、既存要素をそこへ移動する。
その結果、それまで使っていた参照 e や、ループ継続のために内部で保持されていたイテレータは古いメモリ領域を指すことになり、無効化される。
つまり、危険なのは「追加したこと」そのものよりも、追加に伴う再確保が、現在使っている参照やイテレータの前提を壊すことである。
イテレータループ中の erase
for (auto it = m_entities.begin(); it != m_entities.end(); ++it)
{
if (!(*it)->isAlive())
{
m_entities.erase(it);
}
}この場合、erase(it) を呼んだ時点で、it 自身が指していた要素は削除される。
さらに std::vector では、その後ろの要素が前へ詰められるため、削除位置以降を指していたイテレータもまとめて無効化される。
すると、その直後の ++it や次回の比較 it != m_entities.end() は、すでに無効なイテレータに対して行われる可能性がある。
つまり、ループ中の操作で重要なのは次の点である。
- ループは内部でイテレータや参照を保持して進む
push_backは再確保によって、それらを無効化しうるeraseは削除位置以降のイテレータを無効化しうる- したがって、走査中のコンテナをその場で変更すると、ループの継続条件そのものが壊れることがある
for (auto& e : m_entities)
{
if (/* 条件 */)
{
m_entities.push_back(newEntity); // 再確保で既存参照が無効化されうる
}
}for (auto it = m_entities.begin(); it != m_entities.end(); ++it)
{
if (!(*it)->isAlive())
{
m_entities.erase(it); // 以降のイテレータが無効化されうる
}
}対策
- 追加・削除を遅延させる
- イテレータの無効化の影響を受けないタイミングになってから、対象のコンテナの変更操作を行うこと