9

今、ジョスティスのSTLの本を読んでいます。

私の知る限り、c++ vector は再割り当て可能な c-array です。それで、 push_back() の後にすべてのイテレータと参照が無効になる理由を理解しています。

しかし、私の質問は std::deque に関するものです。私が知っているように、それは大きなブロックの配列です（c配列のc配列）。したがって、push_front() は最初に要素を挿入し、スペースがない場合、deque は新しいブロックを割り当て、割り当てられたブロックの最後に要素を配置します。

真ん中の insert() の後、すべての参照とイテレータが無効になり、その理由がわかりました - すべての要素が移動されます。しかし、「... push_back() および push_front() の後、すべての参照は有効なままですが、イテレータはそうではありません」というフレーズを本当に誤解しています (同じフレーズは @ standard:23.2.2.3 で見つかります)。

どういう意味ですか？！参照が有効な場合、deque はその要素を再割り当て (== 移動) できませんでした。では、なぜ反復子が無効になるのでしょうか? 非移動要素の挿入後にそれらを使用できないのはなぜですか? それとも、begin() または end() とオーバーフローに対するイテレータの等価性について確信が持てないということですか?

また、ererase() の後、すべてのイテレータと参照が有効なままであることにも言及したいと思います (消去されたものを除く:-))。

PS: 「標準」形式で回答しないでください: 「標準でそう言っているので使用できません」。なぜ、何が起こるのかを理解したい。

4

1 に答える 1

10

イテレータが無効になる理由は無効になると思いますが、参照が無効になるのは、要素を格納するdequeのページへのポインタの配列がdequeで実装されている可能性があるためである可能性があります。deque内の要素への参照は、「ページ」内の要素を直接参照します。ただし、両端キューへのイテレータは、さまざまなページを指すポインタのベクトルに依存する場合があります。

新しい要素を一方または他方の端の両端キューに挿入する場合、既存のデータページを再割り当ておよび移動する必要はありませんが、ページポインタの配列に追加（したがって、再割り当ておよびコピー）して、前の配列に依存していたイテレータを無効にする必要がある場合があります。ページポインタの。

Array of pointers           
(if this grows                 Data Pages
 and gets copied,           (these never move
 iterators are invalid)      due to insert at ends)
-----------------          --------------------

 +----------+               +----------+
 |         -+-------------->|          |
 +----------+               +----------+
 |         -+---------+     |          |
 +----------+         |     +----------+
 |         -+---+     |     |          |
 +----------+   |     |     +----------+ 
                |     |
                |     |
                |     |
                |     |     +----------+
                |     +---->|          |
                |           +----------+
                |           |          |
                |           +----------+
                |           |          |
                |           +----------+ 
                |           
                |           +----------+
                +---------->|          |
                            +----------+
                            |          |
                            +----------+
                            |          |
                            +----------+
于 2009-11-02T06:18:52.923 に答える