15

vector再割り当てが発生したときに'イテレータを無効にする必要がある理由がわかりません。

ポインタの代わりにオフセットをイテレータに格納するだけで、これを防ぐことはできませんでしたか？

なぜvectorこのように設計されなかったのですか？

4

7 に答える 7

15

イテレータがそれを行うには、ベクトルオブジェクトへのポインタを格納する必要があるためです。データアクセスごとに、ベクトルへのポインターをたどり、その中のポインターをデータ配列の現在の位置までたどり、オフセット*要素サイズを追加する必要があります。size_typeそれははるかに遅くなり、メンバーのためにより多くのメモリが必要になります。

確かに、それは時々良い妥協案であり、必要なときにそれを選択できるといいのですが、（Cスタイルの）直接配列の使用よりも遅くてかさばります。 std::vectorSTLが導入されたとき、パフォーマンスについて容赦なく精査されました。通常の実装は、アレイと同等のoperator[]速度がアレイと同じくらい高速ですが、より安全性が低いのと同じように、この利便性/信頼性の要素よりもスペースと速度が最適化されていますat()。

于 2012-06-11T01:09:35.890 に答える
15

パフォーマンス関連の正当化に引用を追加するだけです。C++を設計するとき、Stroustrupは、std::vectorのようなテンプレートクラスがネイティブ配列のパフォーマンス特性に近づくことが重要であると考えました。

実行時の効率を重視する理由の1つは、配列やリストなどの低レベルの型に使用できるように、時間と空間で十分に効率的なテンプレートが必要だったためです。

..。

より高いレベルの選択肢（たとえば、size（）演算を使用した範囲チェック配列、多次元配列、適切な数値ベクトル演算とコピーセマンティクスを使用したベクトル型など）は、ユーザーが実行した場合にのみ受け入れられます。時間、スペース、および表記上の利便性は、組み込みアレイのものに近づきました。

言い換えると、パラメータ化された型を提供する言語メカニズムは、関係するユーザーが標準ライブラリクラスを優先して配列の使用を排除できるようにする必要があります。

Bjarne Stroustrup、C ++の設計と進化、p.342。

于 2012-06-11T01:53:59.037 に答える
5

標準をラップすることで安全性を追加できstd::vector<T>::iteratorますが、をラップすることで速度を追加することはできませんextension::vector<T>::safe_iterator。これは一般的な原則であり、多くのC++設計の選択を説明しています。

于 2012-06-11T08:58:15.423 に答える
3

これらの決定には多くの理由があります。他の人が指摘しているようにiterator、ベクトルの最も基本的な実装は、要素への単純なポインタです。イテレータを処理できるようにするpush_backには、ベクトルと位置へのポインタを処理するように変更する必要があります。演算子を介してアクセスすると、ベクトルポインタが逆参照され、取得されたデータへのポインタと位置が追加されます。余分な逆参照。

これは最も効率的な実装ではありませんが、実際には制限要因ではありません。VS / Dinkumwareライブラリ（リリース中であっても）のイテレータのデフォルトの実装は、同等の量の情報を管理するチェックされたイテレータです。

実際の問題は、他のミューテーション操作にあります。ベクトルの中央に挿入/消去することを検討してください。すべてのイテレータの有効性を維持するには、コンテナはイテレータのすべてのインスタンスを追跡し、同じ要素（挿入/削除によって置き換えられた）を参照するように位置フィールドを調整する必要があります。

于 2012-06-11T02:38:26.397 に答える
1

オフセットとベクトルオブジェクト自体へのポインタの両方を格納する必要があります。

指定されているように、イテレータは単なるポインタにすることができ、より少ないスペースで済みます。

于 2012-06-11T01:08:42.883 に答える
1

TL;DR-無効化のための単純なルールをはるかに複雑な遠隔作用のルールと交換しているためです。

「ベクターオブジェクトへのポインタを保存する」と、新しい無効化のケースが発生することに注意してください。たとえば、今日でswapはイテレータの有効性が保持されています。ベクトルへのポインタ（または参照）がイテレータ内に格納されている場合、それはできなくなります。ベクトルメタデータ自体（ベクトルのベクトルは誰か？）を移動するすべての操作は、イテレータを無効にします。

「要素へのポインタ/参照が無効になるとイテレータが無効になる」と「ベクトルへのポインタ/参照が無効になるとイテレータが無効になる」と交換します。

提案された代替実装は正しくないため、パフォーマンスの議論はそれほど重要ではありません。

于 2016-12-08T17:24:17.360 に答える
0

イテレータは無効化されていませんが、同じ要素を指す必要がありますか、それともその前に挿入した後の同じ位置を指す必要がありますか？つまり、パフォーマンスの問題がなかったとしても、使用する代替定義を決定するのは簡単ではありません。

于 2012-06-11T15:01:23.373 に答える