質問

C++コンテナにおけるイテレータの無効化ルールとは？

<サブ ( 注意してください。 このQ&Aは、以下のエントリです。 スタックオーバーフローのC++FAQ . この質問に関するメタディスカッションは、以下のサイトに投稿してください。 すべての始まりとなったメタな質問 ここではない)

解決方法は？

C++17 (参考文献はすべてCPP17の最終作業草案から -) n4659 )

---

挿入

配列コンテナ

• vector : 機能 insert , emplace_back , emplace , push_back は、新しいサイズが古い容量より大きい場合、再割当を引き起こします。再割り当ては、シーケンス内の要素を参照しているすべての参照、ポインタ、イテレータを無効にします。再割り当てが行われない場合 が発生した場合、挿入ポイント以前のすべてのイテレータと参照は有効なままである。[26.3.11.5/1]
  に関しては reserve 関数の再割り当ては、シーケンス内の要素を参照しているすべての参照、ポインタ、イテレータを無効にします。を呼び出した後に起こる挿入の間，再割り当てを行ってはならない。 reserve() 挿入によってベクトルのサイズが capacity() . [26.3.11.3/6]

• deque : deque の途中への挿入は、deque のすべてのイテレータと要素への参照を無効にする。deque の両端への挿入は、deque のすべてのイテレータを無効にするが、 deque の要素への参照の有効性には影響を与えない。[26.3.8.4/1]

• list : イテレータやリファレンスの有効性に影響を与えない。例外が発生しても影響はない。[26.3.10.4/1].
  は、その insert , emplace_front , emplace_back , emplace , push_front , push_back 関数は、このルールの対象となる。

• forward_list : のオーバーロードは、いずれも insert_after は、イテレータと参照の有効性に影響を与えるものとする[26.3.9.5/1]。

• array : 原則として 配列へのイテレータは、その配列のライフタイムを通じて決して無効にはなりません。しかし、入れ替えの際には、イテレータは同じ配列要素を指し続けるので、値が変わってしまうことに注意しなければなりません。

アソシアティブコンテナ

• All Associative Containers : は insert と emplace メンバは，イテレータ及びコンテナへの参照の有効性に影響を及ぼしてはならない[26.2.6/9] 。

非順序型連想コンテナ

• All Unordered Associative Containers : リハッシュはイテレータを無効にし、要素間の順序を変更し、要素が出現するバケットを変更しますが、要素へのポインタや参照は無効にしません。[26.2.7/9]
  その insert と emplace メンバは，コンテナ要素への参照の有効性に影響を及ぼしてはならないが，コンテナへのすべてのイテレータを無効とすることができる。[26.2.7/14]
  は、その insert と emplace の場合、メンバはイテレータの有効性に影響を与えないものとする。 (N+n) <= z * B ここで N は、挿入操作前のコンテナ内の要素数です。 n は挿入された要素の数です。 B はコンテナのバケット数、そして z はコンテナの最大負荷率である。[26.2.7/15]

• All Unordered Associative Containers : マージ操作の場合（例． a.merge(a2) を参照するすべてのイテレータは、転送された要素を参照するイテレータになります。 a に残っている要素に対するイテレータは無効となります。 a2 は有効であり続ける。(表 91 - 順不同の連想コンテナの要件)

コンテナ用アダプター

• stack : 基本コンテナから継承
• queue : 下のコンテナから継承
• priority_queue : 下のコンテナから継承

---

消去

シーケンスコンテナ

• vector : 機能 erase と pop_back は，消去された時点以降のイテレータ及び参照を無効にする。[26.3.11.5/3]

• deque : の最後の要素を消す消去操作。 deque は、過去の終了イテレータと、消去された要素へのすべてのイテレータと参照のみを無効にします。の最初の要素を消去する操作は、終了したイテレータと、消去された要素のすべてのイテレータと参照を無効にします。 deque 最後の要素ではなく、イテレータとその要素への参照のみが無効となります。の最初の要素も最後の要素も消去しない消去操作では、消去された要素への参照のみが無効になります。 deque のすべての要素に対する過去の終了イテレータとすべてのイテレータと参照を無効にします。 deque . [ 注 pop_front と pop_back は消去操作です。-終了メモ- ]。[26.3.8.4/4]

• list : 消去された要素へのイテレータと参照のみを無効にする。[26.3.10.4/3]. これは、以下に適用されます。 erase , pop_front , pop_back , clear 関数を使用します。
  remove と remove_if メンバー関数です。リスト・イテレータが参照するリストの要素をすべて消去する関数です。 i で、以下の条件が成立するもの。 *i == value , pred(*i) != false . 消去された要素へのイテレータと参照のみを無効化する[26.3.10.5/15]。
  unique member function - イテレータが参照する連続した等しい要素群から、最初の要素以外を消去します。 i の範囲内で [first + 1, last) に対して *i == *(i-1) (引数なしのuniqueのバージョンの場合)または pred(*i, *(i - 1)) (述語の引数を持つバージョンのuniqueの場合)が成立する。消去された要素へのイテレータと参照のみを無効化する。[26.3.10.5/19]

• forward_list : erase_after は，消去された要素へのイテレータ及び参照のみを無効とする。[26.3.9.5/1].
  remove と remove_if メンバ関数 - リスト・イテレータ i が参照するリストのうち、以下の条件が成立する要素を全て消去する。 *i == value (以下は remove() ), pred(*i) が真になる（この場合 remove_if() ). 消去された要素へのイテレータと参照のみを無効にする。[26.3.9.6/12].
  unique メンバ関数 - イテレータiによって参照される連続した等しい要素群のうち， [first + 1, last]の範囲にあるものから，最初の要素以外を消去します。 *i == *(i-1) (引数なしのバージョンの場合)または pred(*i, *(i - 1)) (述語引数付きバージョンの場合)が成立する。消去された要素へのイテレータと参照のみを無効化する。 [26.3.9.6/16]

• All Sequence Containers : clear は、aの要素を参照するすべての参照、ポインタ、イテレータを無効にし、過去の終了イテレータを無効にする場合があります（表87 - シーケンスコンテナの要件）。しかし forward_list , clear は、過去の終了イテレータを無効にしない。[26.3.9.5/32]

• All Sequence Containers : assign は、すべての参照、ポインタ、および コンテナの要素を参照するイテレータです。の場合 vector と deque は、過去に終了したイテレータも無効にする。(表87 - シーケンスコンテナの要件)

アソシアティブコンテナ

• All Associative Containers : は erase メンバは，消去された要素へのイテレータ及び参照のみを無効化しなければならない[26.2.6/9]。

• All Associative Containers : は extract メンバは、削除された要素へのイテレータのみを無効にします。削除された要素へのポインタと参照は有効なままです[26.2.6/10]。

コンテナ用アダプター

• stack : 基本コンテナから継承
• queue : 下のコンテナから継承
• priority_queue : 下のコンテナから継承

---

イテレータの無効化に関する一般的なコンテナ要件。

• 特に指定がない限り（明示的に、または他の関数で関数を定義することによって）、コンテナのメンバ関数を呼び出したり、ライブラリ関数の引数としてコンテナを渡しても、そのコンテナ内のオブジェクトへのイテレータを無効化したり、その値を変更したりしてはならない。[26.2.1/12]

• いいえ swap() 関数は、交換されるコンテナの要素を参照している参照、ポインタ、イテレータをすべて無効にします。[注意： end()イテレータはどの要素も参照していないので、無効になる可能性があります。-終了メモ- ]。[26.2.1/(11.6)]

上記の要求事項の例として

• transform アルゴリズムを使用します。は op と binary_op 関数は，イテレータ又はサブレンジを無効にしたり，範囲内の要素を変更してはならない [28.6.4/1] 。

• accumulate のアルゴリズムを使用しています。範囲[first, last]で。 binary_op は，要素を修正したり，反復子又は部分範囲を無効にしたりしてはならない[29.8.2/1]。

• reduce algorithm: binary_op は、イテレータやサブレンジを無効にしてはならないし、範囲 [first, last] 内の要素を変更してはならない。[29.8.3/5]

などなど...。