4

Scott Meyers による効果的な STL を読んでいます。ここの項目 1 の著者は、さまざまなコンテナーの中から選択する方法について言及しています。以下は、私が理解するのが難しいテキスト スニペットです。

何も消去されず、コンテナーの末尾でのみ挿入が行われる限り、データへのポインターと参照が無効にされないランダム アクセス反復子を備えたシーケンス コンテナーを用意すると便利でしょうか? これは非常に特殊なケースですが、あなたの場合、deque は夢のコンテナーです。(興味深いことに、deque の反復子は、挿入がコンテナーの最後でのみ行われる場合に無効になる場合があります。deque は、ポインターと参照を無効にすることなく反復子を無効化できる唯一の標準 STL コンテナーです。)

上記のテキストに関する私の質問

  1. 上記のコンテキストでのポインターと参照とは、作者が何を意味し、イテレーターとどう違うのですか?

  2. 挿入が最後にのみ行われ、それでも有効なポインターと参照がある場合、deque のイテレーターはどのように無効になる可能性がありますか?

上記の 2 つの質問に、簡単な例で回答してもらいます。

お時間をいただきありがとうございます。

4

2 に答える 2

2

最初の部分の意味は次のとおりです。

deque<int> foo(10, 1); // a deque with ten elements with value of 1
int& bar = foo.front(); // reference
int* baz = &foo.front(); // pointer
deque<int>::iterator buz = foo.begin(); // iterator
deque.push_front(0); 
// At this point bar and baz are still valid, but buz may have been invalidated

2 番目の部分については、ここで詳細に説明されています。

push_back または push_front が両端キューのイテレータを無効にするのはなぜですか?

于 2012-11-20T13:57:58.640 に答える
1

forイテレータは、ループなどで配列インデックスを使用する場合と同様に、標準ライブラリコンテナの要素を「循環」させるためによく使用されます。

イテレータは多くの理由で無効になる可能性があります。forこれが発生する一般的なケースの1つは、次のようなループを使用する場合です。

std::deque<int> c;

for(std::deque<int>::iterator i = c.begin(); i != c.end(); ++i) {
    // do some stuff to the deque's elements here
}

上記のループの最後で、イテレータは、両端キューの最後の実際の要素の1ブロック後iの「要素」を指します。あなたが次のようなことをしようとした場合

*i = 88;

上記のループの終了直後は、コンテナがメモリを「ポイント」しforていないため、問題になります。i

しかし、マイヤーズが話している可能性が高いのは、標準では、両端キューの実装の多くが設計者に公開されているということです。Dequeは通常、複数の要素を保持するメモリブロックのリンクリストとして実装されるため、ベクトルとは異なり、要素がメモリ内で互いに隣接するという保証はありません。さらに、イテレータには、これらの「ブロック」に関する情報が含まれている必要があります。これにより、イテレータはスムーズにトラバースできます（つまり、イテレータは単なるポインタではありません）。

たとえばpush_back()、新しい要素であるが、メモリの「最後の」チャンクにスペースがない場合、dequeは、新しい要素（および最後に追加される将来の要素）に新しいメモリブロックを割り当てる必要があります。以前使用していたイテレータは、この新しいメモリチャンクを「認識」していない可能性があるため、無効である可能性があります。

一方、参照と実際のポインタは、このコンテキストでは、コンテナ内の個々のオブジェクトを参照/参照するために使用されます。私が書いたら

int& j = *c.begin();

その場合、jはの最初の要素への参照ですc。私がそうしたら

c.push_front(74);

j両端キューの先頭にない場合でも、前の最初の要素を参照します。

ただし、両端キューの途中に何かを挿入すると、それらの連続するメモリのチャンクの1つを効果的に分割し、そこに新しい要素を絞り込もうとしている可能性があります。スペースを確保するには、一方または他方の要素をメモリ内でシャッフルする必要があります（場合によっては新しいメモリを割り当てる必要があります）。これは必然的に、挿入のその「側」にある要素へのポインタ/参照を無効にします。挿入された要素のためにどの程度正確にスペースを空けるかは実装者次第であるため、挿入に関してどこにあるかに関係なく、すべてのベットはポインター/参照に関してオフになります。

于 2012-11-20T13:50:02.170 に答える