ベクトルのサイズを変更すると反復子は無効になりますか?

StackOverflow https://stackoverflow.com/questions/1624803

  •  06-07-2019
  •  | 
  •  

質問

この C++ コードは次のとおりであることがわかりました。

vector<int> a;
a.push_back(1);
a.push_back(2);
vector<int>::iterator it = a.begin();
a.push_back(4);
cout << *it;

大きな乱数を出力します。しかし、追加すると a.push_back(3) 3行目と4行目の間には1が出力されます。説明してもらえますか？

役に立ちましたか？

解決

より慎重な表現で編集

はい、ベクターのサイズを変更すると、ベクターを指すすべての反復子が無効になる場合があります。

ベクトルは、データが格納されている配列を内部的に割り当てることで実装されます。ベクトルが大きくなると、その配列はスペースを使い果たす可能性があり、大きくなると、ベクトルは新しい大きな配列を割り当て、その上にデータをコピーし、古い配列を削除します。

したがって、古いメモリを指す古いイテレータは無効になります。 ただし、ベクトルが downwards にサイズ変更された場合（たとえば pop_back（）によって）、同じ配列が使用されます。配列が自動的に縮小されることはありません。

この再割り当て（およびポインターの無効化）を回避する1つの方法は、最初に vector :: reserve（）を呼び出して、このコピーが不要な十分なスペースを確保することです。あなたの場合、最初の push_back（）操作の前に a.reserve（3）を呼び出した場合、内部配列は push_back 'sは配列を再割り当てすることなく実行できるため、イテレータは有効なままです。

他のヒント

ベクトル反復子は、ベクトルが再割り当てを実行するときにのみ無効になります。

push_back（4）の呼び出しにより、ベクトルは新しいメモリブロックを割り当てます。イテレータが無効になります。 push_back（3）も使用すると、 push_back（4）の再割り当ては実行されないため、反復子は有効なままです。

はい、ベクトルのサイズを変更する可能性のあるアクションは、イテレーターを無効にする可能性があります。

編集：コンテナのサイズを縮小する操作（例： erase（）、 resize（））が含まれます。 erase（）は all イテレータを無効にしませんが、消去された要素の後のポイントを参照するイテレータは無効にします。 resize（）は insert（）および erase（）で定義されているため、同じ可能性があります。

イテレータの無効化のルールはコンテナに固有です。

現在、無効化にはベクトルの 2 つの意味があります。

  1. 無効化 = [begin,end] で定義された範囲外のポイント
  2. 無効化 = 元のオブジェクトとは異なるオブジェクトを指す

ご覧のとおり、2 番目の方がはるかに厳密です。

std::vector<int> myVector;
myVector.push_back(0);
myVector.push_back(1);

std::vector<int>::iterator it = myVector.begin(); // it points to 0
myVector.erase(it); // it points to 1
myVector.erase(it); // it == myVector.end()

この場合、常に包含範囲 [begin,end] 内にあるという点で「有効」であるため、myVector に対するあらゆる操作に安全に使用できます。一方、(*it) という表現は変わり続けます。最初に 0 を返し、次に 1 を返し、その後は未定義の動作になります...

一般に、人々はむしろ 2 番目の要件について話します。イテレータを無効にするということは、単に (* それが) 以前と同じ結果を生成しない可能性があることを意味します。

そうは言っても、Vector のイテレータを無効にする方法はいくつかあります (実際、これは STL の構造の中で最も不安定です)。

要素の追加中:

  • これにより、次のような問題が引き起こされる可能性があります。 再割り当て (1) myVector.size() == myVector.capacity() の場合、これをチェックするとエラーが発生しやすいため、通常は追加によって反復子が無効になると考えられます。
  • 「厳選」したい場合で、再割り当てがトリガーされないことがわかっている場合でも、次のことを心配する必要があります。 insert. 。要素を挿入すると、要素はベクトルの終端に向かって 1 ステップシフトされるため、この現在位置を指す反復子とその後のすべての反復子が無効になります。

要素の削除中:

  • バッファーが必要以上に大きくなった場合でも、再割り当ては行われません。ただし、次を使用してこれを強制することは可能です ぴったりと縮む イディオム(2)。
  • 削除された要素以降を指すすべての反復子は無効になります。特に、以前の 'end' イテレータは [begin,end] の範囲を超えており、たとえば STL アルゴリズム内で安全に使用できません。

(1) std::vector の内部構造は T の配列です。これは、C プログラムとの互換性 (配列のアドレスとして &myVector.front() を使用) のためであり、連続性と最小値が保証されるためです。スペース オーバーヘッド (つまり、ベクトル自体のデータが占めるスペースの量とオブジェクトが占めるスペースの量)

.capacity() メソッドを使用すると、いつでもベクターが保持できるオブジェクトの数を知ることができます。

オブジェクトを挿入する必要があり、ベクターに必要な容量がない場合、 .reserve(size_t) メソッドの呼び出しがトリガーされます。このメソッドでは、必要なアイテムの数が現在の容量を超えている場合、 再割り当て.

次に、ベクトルは要素の新しい配列 (通常、そのサイズは 2*n+1 (n は現在の容量)) を割り当て、現在の配列の要素を新しい配列にコピーし、現在の配列を破棄します。

現在の配列が破棄されるため、ベクトル反復子は一般に単純なポインターであるため (効率性のため)、反復子は無効になります。

イテレータが次のように実装されている場合に注意してください。ベクトルへの参照 + カウント、および逆参照は実際には *(&m_vector.front() + n) でした。再割り当てはそれらを無効にしません...しかし、効率は悪くなります。

(2) 縮小してフィットさせる:警告、これにより要素の COPY がトリガーされ、反復子が無効になります。

// myVector has 10 elements, but myVector.capacity() == 1000
myVector.swap(std::vector<int>(myVector));

まず、必要なだけのメモリ (ライブラリに応じた最小量) のみを割り当て、myVector の要素をコピーする一時的なベクトルを作成します。次に、スワップ操作によって myVector とこのコピーのバッファーが交換されるため、myVector は必要最小限のメモリーを備えたバッファーを保持するようになります。操作の終了時に一時ファイルは破棄され、一時ファイルが保持していたメモリは解放されます。

今後の参照用に、このようなすべてのSTL類の情報はSGIのWebサイトにあります： http://www.sgi.com/tech/stl/Vector.html

コレクションに追加または削除した後にイテレータを有効に保つ必要がある場合は、リストなどの別の種類のコレクションを見てください。

しかし、最善の方法は、コレクション（ランダムアクセスなど）から必要な機能のマトリックスを特定し、適切なコンテナーを選択することです。

開始点については、Standard_Template_Library Containersのウィキペディアの記事を参照してください。現金がある場合は、スコットマイヤーの「効果的なSTL：標準テンプレートライブラリの使用を改善する50の具体的な方法」を強くお勧めします。

サポートリンクがないことをおologiesび申し上げます。私はここの初心者であり、複数のリンクを投稿する評判がありません。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top