14

deque でのイテレータの無効化に関して、私は少し混乱しています。（この質問の文脈で）

以下は抜粋です -- The C++ Standard Library: A Tutorial and Reference, by Nicolai M. Josuttis

先頭または末尾以外の要素を挿入または削除する と、deque の要素を参照するすべてのポインター、参照、および反復子が無効になります。

以下は、 SGIサイトからの抜粋です。

deque の反復子無効化のセマンティクスは次のとおりです。Insert (push_frontおよびを含むpush_back) は、deque を参照するすべての反復子を無効にします。両端キューの途中で消去すると、両端キューを参照するすべての反復子が無効になります。pop_front両端キュー (およびを含む) の先頭または末尾での消去は、消去され pop_backた要素を指している場合にのみ反復子を無効にします。

IMHO、deque は、最初のブロックが一方向に成長し、最後のブロックが反対方向に成長するブロックのコレクションです。

  -   -  -  
  -   -  -
  |   -  -  ^
  |   -  -  |
  V   -  -  |
      -  -  -
      -  -  -

push_back, push_frontdeque イテレータに影響を与えるべきではありません (私は Josuttis に同意します)。

正しい説明は何ですか？これについて標準は何と言っていますか？

4

3 に答える 3

13

標準作業草案から

template < class InputIterator > void insert ( iterator position , InputIterator first , InputIterator last );

1 効果:両端キューの途中に挿入すると、すべてのイテレータと両端キューの要素への参照が無効になります。両端キューのいずれかの端に挿入すると、両端キューのすべての反復子が無効になりますが、両端キューの要素への参照の有効性には影響しません。」

したがって、どちらも正しいです。Josuttis が示すように、前後に挿入しても両端キューの要素への参照は無効にならず、両端キュー自体へのイテレータのみが無効になります。

編集:より最新のドラフトでは、本質的に同じことが述べられています (セクション 23.2.2.3)

于 2009-05-27T05:06:22.653 に答える
12

IMHO、deque は、最初のブロックが一方向に成長し、最後のブロックが反対方向に成長するブロックのコレクションです。

あなたの意見はあなたの特権ですが、それは間違っています。:)

dequeは意味的にはそのようなコンテナーですが、実装に関しては、1 つ以上のメモリ ブロックによって実装されるように設計されています。C++ の反復子無効化規則は実装に由来するため、これが理由です。間違いなく、これは小さな抽象化のリークですが、まあまあです。

SGI STL は C++ 標準ライブラリではないため、SGI STL ドキュメントは適切なドキュメントではありません。残念ながら、Josuttis はこれを「STL」と呼んでいる人の 1 人であり、これが混乱を招いています。

以下は抜粋です -- The C++ Standard Library: A Tutorial and Reference, by Nicolai M. Josuttis

先頭または末尾以外の要素を挿入または削除すると、deque の要素を参照するすべてのポインター、参照、および反復子が無効になります。

簡単に言えば、Josuttis からのこの一節は、先頭または末尾にある要素の挿入または削除がポインター、参照、またはイテレーターを無効にしないことを暗示している点で誤解を招くものです。

の実際の、適切な、公式のルールは次のstd::dequeとおりです。

C++03

  • 挿入: 挿入されたメンバーが両端キューの末尾 (先頭または末尾) にない限り、すべての反復子と参照が無効になります (この場合、すべての反復子は無効になりますが、要素への参照は影響を受けません) [23.2.1.3/1]

  • 消去: 消去されたメンバーが両端キューの末尾 (前部または後部) にない限り、すべてのイテレーターと参照が無効になります (この場合、イテレーターと消去されたメンバーへの参照のみが無効になります) [23.2.1.3/4]

  • サイズ変更 : 挿入/消去 [23.2.1.2/1] による

C++11

  • 挿入: 挿入されたメンバーが両端キューの末尾 (先頭または末尾) にない限り、すべての反復子と参照が無効になります (この場合、すべての反復子は無効になりますが、要素への参照は影響を受けません) [23.3.3.4/1]

  • Erasure : 最後の要素を消去すると、反復子と、消去された要素への参照と末尾反復子のみが無効になります。最初の要素を消去すると、反復子と消去された要素への参照のみが無効になります。他の要素を消去すると、すべての反復子と参照が無効になります (過去の反復子を含む) [23.3.3.4/4]

  • サイズ変更 : 挿入/消去 [23.3.3.4/1] に従って

参考文献

あなたが探している信頼できる情報源へのさらなる参照はわかりません — 関連する標準的な文章はすでに引用され引用されています.

于 2013-01-05T14:31:23.027 に答える
0

SGI 実装はおそらく拡張可能な配列を使用するため、挿入によって配列が拡張される場合、古い配列を指す反復子は無効になります。

編集：

The C++ Programming Language Third Edition のセクション 17.2.3 を見ると、どの操作がイテレータを保持または無効化するかを示す deque の説明には何も表示されません。間違った場所を見ているか、動作が未定義である可能性があります。

于 2009-05-27T05:05:29.970 に答える