c++ - イテレータ無効化のルール

Question

STLコンテナクラス（Vector、Dequeue、list、map、multimap、set、multiset）を操作する場合のイテレータ無効化の通常のルールは何ですか。C ++ STLプログラマーがコンテナーとそのイテレーターを操作する際に知っておく必要のある一般的なルール/ガイドラインを分類して要約することは可能ですか？

Answer 1

これらのルールはコンテナ固有です。実際、これらは使用するコンテナを決定するための重要な基準です。

たとえば、オブジェクトへのイテレータはstd::vector、オブジェクトが挿入されると無効になり（オブジェクトが挿入される場所と再割り当てが行われるかどうかによって異なります）、イテレータの前にオブジェクトが削除されると無効になります。にstd::listはこの問題はありません。オブジェクト（イテレータが指すオブジェクトを除く）を挿入および削除しても、イテレータは無効になりません。

SGIは、これに関する優れたドキュメントを提供します。

Answer 2

無効化ルールは、これらのコンテナを実装するために使用される非常に基本的なデータ構造とアルゴリズムから着想を得ています。基本を学ぶ予定がない場合は、イテレータのドキュメントを覚えておく必要があります。

C ++標準は、単純なCポインターを使用して実装できるiteratorようにの動作を定義します。ライブラリが実際にポインタを使用する必要はありません。それは単にそうすることを可能にします。

vector基本的に、操作によって基になるストレージ要素（で使用されるヒープ配列、で使用されるリンクリストノード、またはlistで使用されるツリーノード）の割り当てが解除されるか、別のメモリにシフトされる場合、イテレータは無効になります。位置。mapset

Avectorは通常、動的メモリ（ヒープ）から配列を割り当てることによって実装されます。再割り当ての数を減らすために、アレイには常にある程度の余裕、つまり最初は未使用のスペースが割り当てられます。要素が配列に追加されると、スラックスペースが使い果たされます。すべてのスラックスペースが使用され、新しい要素を挿入する必要がある場合は、より大きなサイズの新しい配列が割り当てられます。これにより、古い配列を指すすべてのイテレータが無効になります。

同様に、要素がから消去されるvectorと、後続のすべての要素が前方にコピーされます。シフトされた要素を指すイテレータは、配列内の同じインデックスを参照しますが、そのインデックスには別の要素が含まれるようになりました。これも無効化の例です。

list、mapおよびの場合set、ツリーノードまたはリストノードは、含まれている要素が消去されるまで有効です。無効化されたノードを指すイテレータは、何にも使用できないことに注意してください。イテレータのインクリメント/デクリメントでもありません。これは、リンクリストまたはツリーの実装では、イテレータがノード自体に格納されている子ポインタに依存しているためです。

常に正しい動作を保証するために、標準は、単純なデータ構造が使用される場合よりも制限的な方法で表現されます（逆説的に、ライブラリの実装者はより高度なデータ構造を使用するための自由度が高くなります）。たとえば、http：//c2.com/cgi/wiki？IteratorInvalidationProblemおよびhttp://www.threadingbuildingblocks.org/codesamples.phpを参照してください。