1

回答ベクトルを自己コピーする方法は?イテレータの無効化について少し混乱しました。一部の文献には、「insert、push_backなどを使用する場合は、すべてのイテレータを無効と見なす」と記載されています。それは明らかです、それはイテレータを無効にするベクトルを成長させるかもしれません。十分なスペースがあることがわかっている特別な場合はどうですか?

初挑戦:

myvec.reserve(myvec.size()*3);  //does this protect me from iterator invalidation?
vector<string>::iterator it = myvec.end();    
myvec.insert(myvec.end(), myvec.begin(), it);
myvec.insert(myvec.end(), myvec.begin(), it);

いくつかの優れた回答の後、2回目の試行:

auto size = myvec.size();
myvec.reserve(size*3);  //does this protect me from iterator invalidation?  
myvec.insert(myvec.end(), myvec.begin(), myvec.begin()+size);
myvec.insert(myvec.end(), myvec.begin(), myvec.begin()+size);

より優れた回答の後、3回目の試行:

auto size = myvec.size();
myvec.reserve(size*3);  //does this protect me from iterator invalidation?  
back_insert_iterator< vector<string> > back_it (myvec);
copy (myvec.begin(),myvec.begin()+size,back_it);
copy (myvec.begin(),myvec.begin()+size,back_it);

Josuttisの「C++標準ライブラリリファレンス」からのこの引用:

要素を挿入または削除すると、次の要素を参照する参照、ポインター、およびイテレーターが無効になります。挿入によって再割り当てが発生すると、すべての参照、イテレータ、およびポインタが無効になります。

私のコードが安全で定義された動作であることを示唆しています。これを保証する基準に一節はありますか?

4

3 に答える 3

7

過去のイテレータは常に少し特別です。気をつけます。標準はこれを言います(23.3.6.5):

再割り当てが発生しない場合、挿入ポイントの前のすべてのイテレータと参照は有効なままです。

ここで重要なのは「挿入点の前」です。あなたのオリジナルitは挿入ポイントの前にないので(それ挿入ポイントであるため)、私はそれが有効であることに頼ることはありません。

于 2013-02-11T21:11:50.310 に答える
2

ベクトルへの挿入は、容量を超えない限り再割り当てを引き起こさず、挿入ポイントのend()の要素へのイテレーターを無効にしないことは事実ですが( @KerrekSBが指摘したように、これは間違いなくケースです)、 C ++ 11標準の表100(段落23.2.3)は、シーケンスコンテナの関数の次の前提条件を指定しています。a.insert(p,i,j)

[...] pre:iとjはaへのイテレータではありません。[...]

あなたの場合、それらは明らかにそうです、それは私にプログラムが未定義の振る舞いを持っていると私に思わせます。

于 2013-02-11T21:14:34.093 に答える
0

関数の途中でイテレータを無効にしないでください。自明でないコンストラクターを持つオブジェクトでは使用できないため、メモリーが再配置される可能性があるという考えは支持されません。realloc構築が問題ではなかったとしても、最悪の場合は最初のシーケンスを2回コピーする必要があり、平均的な場合の利点はありません。

つまり、そのように実装するのは意味がありません。、、はalloc、規格の内容に関係なくcopyfreeほぼ確実に実行されます。

v.begin()v.end()は常に最新であるため、これは安全です。

v.insert(v.end(), v.begin(), v.end());
v.insert(v.end(), v.begin(), v.end());

これではありません。

vector<foo>::iterator i = v.begin();
vector<foo>::iterator j = v.end();
v.insert(v.end(), i, j);
v.insert(v.end(), i, j);

ただし、自己挿入は不安定な場合があります。GCCで次のことを試してください。十分なメモリが使用可能な場合にのみ、自己挿入によって誤った結果が得られます(これがバグかどうかはわかりません)。

int main()
{
    int position = 1, first = 2, last = 3;
    // enforce error condition.
    assert(position < first);
    int size = 8;
    // sanity check.
    assert(first < last && last <= size);

    std::vector<int> right, wrong;
    // force resize during insertion.
    right.reserve(size);
    // avoid resize during insertion.
    wrong.reserve(size + (last - first));

    for ( int i = 0; i < size; i++ )
     {
       right.push_back(i);
       wrong.push_back(i);
     }

    std::vector<int>::iterator i;
    i = right.begin();
    right.insert(i + position, i + first, i + last);
    i = wrong.begin();
    wrong.insert(i + position, i + first, i + last);

    assert(right == wrong);
    return 0;
}

注:上記の意見はvector、一般的なコンテナーではなく、具体的に適用されます。また、上記の動作がバグである可能性があるという提案は、標準とは関係がなく、の堅牢な自己挿入の実装の容易さではありませんvector

于 2014-05-04T04:55:35.207 に答える