596

C++ コンテナーのイテレーター無効化規則とは?

(注:この Q&A は、Stack Overflow の C++ FAQ のエントリです。質問自体に関するメタ ディスカッションは、ここではなく、このすべてを開始したメタの質問に投稿する必要があります。)
4

6 に答える 6

423

C++03 (出典:イテレータ無効化規則 (C++03) )

挿入

シーケンス コンテナー

  • vector: 新しいコンテナーのサイズが以前の容量よりも大きくない限り、挿入ポイントより前のすべてのイテレーターと参照は影響を受けません (この場合、すべてのイテレーターと参照は無効になります) [23.2.4.3/1]
  • deque: 挿入されたメンバーが両端キューの末尾 (前または後) にない限り、すべての反復子と参照が無効になります (この場合、すべての反復子は無効になりますが、要素への参照は影響を受けません) [23.2.1.3/1]
  • list: すべての反復子と参照は影響を受けません [23.2.2.3/1]

連想コンテナ

  • [multi]{set,map}: すべての反復子と参照は影響を受けません [23.1.2/8]

コンテナ アダプタ

  • stack: 基になるコンテナから継承
  • queue: 基になるコンテナから継承
  • priority_queue: 基になるコンテナから継承

消去

シーケンス コンテナー

  • vector: 消去ポイント以降のすべての反復子と参照が無効になります [23.2.4.3/3]
  • deque: 消去されたメンバーが両端キューの末尾 (前部または後部) にない限り、すべてのイテレーターと参照が無効になります (この場合、イテレーターと消去されたメンバーへの参照のみが無効になります) [23.2.1.3/4]
  • list: イテレータと消去された要素への参照のみが無効化される [23.2.2.3/3]

連想コンテナ

  • [multi]{set,map}: イテレータと消去された要素への参照のみが無効化される [23.1.2/8]

コンテナ アダプタ

  • stack: 基になるコンテナから継承
  • queue: 基になるコンテナから継承
  • priority_queue: 基になるコンテナから継承

サイズ変更

  • vector: 挿入/消去による [23.2.4.2/6]
  • deque: 挿入/消去による [23.2.1.2/1]
  • list: 挿入/消去による [23.2.2.2/1]

注1

別段の指定がない限り(明示的に、または他の関数に関して関数を定義することによって)、コンテナー メンバー関数を呼び出したり、コンテナーをライブラリー関数への引数として渡したりしても、そのコンテナー内のオブジェクトの反復子を無効にしたり、その値を変更したりしてはなりません。 . [23.1/11]

注2

C++2003 では、「終了」反復子が上記の規則に従うかどうかは明確ではありません。とにかく、それらがそうであると仮定する必要があります（実際にはそうです）。

注3

ポインターの無効化の規則は、参照の無効化の規則と同じです。

于 2011-06-22T10:01:57.873 に答える
367

C++11 (出典: Iterator Invalidation Rules (C++0x) )

挿入

シーケンス コンテナー

  • vector: 新しいコンテナーのサイズが以前の容量よりも大きくない限り、挿入ポイントより前のすべてのイテレーターと参照は影響を受けません (この場合、すべてのイテレーターと参照は無効になります) [23.3.6.5/1]
  • deque: 挿入されたメンバーが両端キューの末尾 (前または後) にない限り、すべての反復子と参照が無効になります (この場合、すべての反復子は無効になりますが、要素への参照は影響を受けません) [23.3.3.4/1]
  • list: すべての反復子と参照は影響を受けません [23.3.5.4/1]
  • forward_list: すべての反復子と参照は影響を受けません(に適用されますinsert_after) [23.3.4.5/1]
  • array: (該当なし)

連想コンテナ

  • [multi]{set,map}: すべての反復子と参照は影響を受けません [23.2.4/9]

ソートされていない連想コンテナ

  • unordered_[multi]{set,map}: 再ハッシュが発生するとすべての反復子が無効になりますが、参照は影響を受けません [23.2.5/8]。挿入によってコンテナーのサイズが最大負荷係数と現在のバケット数を超えない場合、再ハッシュは行われませんz * B。[23.2.5/14]zB

コンテナ アダプタ

  • stack: 基になるコンテナから継承
  • queue: 基になるコンテナから継承
  • priority_queue: 基になるコンテナから継承

消去

シーケンス コンテナー

  • vector: 消去ポイント以降のすべてのイテレータと参照が無効になります [23.3.6.5/3]
  • deque: 最後の要素を消去すると、反復子と、消去された要素への参照と末尾反復子のみが無効になります。最初の要素を消去すると、反復子と消去された要素への参照のみが無効になります。他の要素を消去すると、すべての反復子と参照が無効になります (過去の反復子を含む) [23.3.3.4/4]
  • list: イテレータと消去された要素への参照のみが無効化される [23.3.5.4/3]
  • forward_list: イテレータと消去された要素への参照のみが無効化されます (に適用されますerase_after) [23.3.4.5/1]
  • array: (該当なし)

連想コンテナ

  • [multi]{set,map}: イテレータと消去された要素への参照のみが無効化される [23.2.4/9]

順不同の連想コンテナー

  • unordered_[multi]{set,map}: イテレータと消去された要素への参照のみが無効化される [23.2.5/13]

コンテナ アダプタ

  • stack: 基になるコンテナから継承
  • queue: 基になるコンテナから継承
  • priority_queue: 基になるコンテナから継承

サイズ変更

  • vector: 挿入/消去による [23.3.6.5/12]
  • deque: 挿入/消去による [23.3.3.3/3]
  • list: 挿入/消去による [23.3.5.3/1]
  • forward_list: 挿入/消去による [23.3.4.5/25]
  • array: (該当なし)

注1

別の方法で指定されていない限り(明示的に、または他の関数に関して関数を定義することによって)、コンテナー メンバー関数を呼び出したり、コンテナーをライブラリー関数への引数として渡したりしても、そのコンテナー内のオブジェクトの反復子を無効にしたり、その値を変更したりしてはなりません。 . [23.2.1/11]

注2

swap() 関数は、スワップされるコンテナーの要素を参照する参照、ポインター、または反復子を無効にします。[注: end() イテレータは要素を参照しないため、無効化される可能性があります。—終わりのメモ] [23.2.1/10]

注3

に関する上記の警告以外に、swap()「終了」イテレータが上記のコンテナごとのルールの対象となるかどうかは明確ではありません。とにかく、それらがそうであると想定する必要があります。

注4

vectorまた、順序付けされていない連想コンテナはすべてサポートreserve(n)されており、少なくともコンテナのサイズがn. 順序付けされていない連想コンテナには注意が必要です。これは、将来の提案で最小負荷係数の指定が許可されるためです。これによりinsert、十分なerase操作でコンテナ サイズが最小値を下回った後に再ハッシュが発生する可能性があります。の後に保証が無効になる可能性があると見なされますerase。

于 2011-06-22T15:53:12.653 に答える
44

std::back_insert_iteratorすべての挿入がこの反復子を介して実行され、他の独立した反復子無効化イベントが発生しない限り、あらゆる種類の挿入反復子 ( 、std::front_insert_iterator、std::insert_iterator) が有効であることが保証されていることを追加する価値があるでしょう。

たとえば、std::vectorを使用して への一連の挿入操作を実行してstd::insert_iteratorいる場合、これらの挿入によってベクトルの再割り当てがトリガーされる可能性が非常に高く、そのベクトルを「指す」すべてのイテレータが無効になります。ただし、問題の挿入イテレータは有効なままであることが保証されています。つまり、一連の挿入を安全に続行できます。ベクトルの再割り当てのトリガーについて心配する必要はまったくありません。

これも、挿入反復子自体を介して実行される挿入にのみ適用されます。イテレータ無効化イベントがコンテナに対する何らかの独立したアクションによってトリガーされた場合、挿入イテレータも一般的なルールに従って無効化されます。

たとえば、このコード

std::vector<int> v(10);
std::vector<int>::iterator it = v.begin() + 5;
std::insert_iterator<std::vector<int> > it_ins(v, it);

for (unsigned n = 20; n > 0; --n)
  *it_ins++ = rand();

ベクトルがこのプロセスの途中で再割り当てを「決定」したとしても、ベクトルへの挿入の有効なシーケンスを実行することが保証されています。Iteratoritは明らかに無効になりますが、it_ins引き続き有効なままです。

于 2012-07-04T23:36:24.350 に答える