c++ - イテレータとポインタの deque insert 無効化 (参照)

Question

cplusplus.com からの引用に基づく

挿入がシーケンスの先頭または末尾で発生した場合、このコンテナーに関連するすべての反復子は無効になりますが、ポインターと参照は有効なままで、呼び出し前に参照していたのと同じ要素を参照します。

フロントまたはエンドへの挿入がイテレータを無効にするのに、ポインタと参照を無効にしないのはなぜですか?

Answer 1

基本的に、dequeは と考えることができますvector<array<T>*>。

つまり、一連の固定サイズ配列へのポインターを含む小さな「インデックス」ベクトルで構成されます。両端キューの先頭または末尾に挿入すると、最初/最後の配列が埋められ、必要に応じて別の配列が追加されるため、既存の要素を移動する必要はありません。これが、ポインター/参照が無効にされない理由です。

ただし、この「インデックス」はベクトルのようなものに格納されるため、サイズ変更時にコピーされて再割り当てされる可能性があるため、新しい配列がインデックスに追加されるたびに、インデックスが別のメモリ位置にコピーされる可能性があります。

イテレーターは、コンテナーを反復処理できるように、コンテナーについて十分に認識している必要があります。つまり、現在指している特定の要素がどこにあるかを知るだけでは十分ではなく、次/前の配列を見つけることができるように、それがどの配列の一部であるか、およびインデックスがどこにあるかを知る必要もあります。

そのため、「インデックス」を無効にするリスクのある操作は、イテレータも無効にします。これは、イテレータが有効な要素を指している可能性はあるものの、deque 全体を反復処理できなくなるためです。

Answer 2

ポインタには個々のアイテムの正しいメモリ アドレスがありますが、たとえば次の場合:

1. シーケンスの先頭を指す反復子を取得する
2. 新しいアイテムを前に挿入する

先頭を指すイテレータがまだありますか? この例では、出力の数字 5 を見逃すことになります。

#include <deque>
#include <iostream>
using namespace std;

int main()
{
    deque<int> d;
    d.push_back(1);
    d.push_back(2);
    d.push_back(3);

    deque<int>::iterator it=d.begin();

    d.push_front(5);

    for(;it!=d.end();++it)
    {
        cout << *it << endl;
    }
}