4

イテレータに関して 2 つの質問があります。

  1. ベクターやリストなどのSTLコンテナーにイテレーターを定義すると、コンテナーに要素を追加すると、これらのイテレーターはそれらにアクセスできなくなると思いました。ただし、次のコードは 5 つの要素のリストを定義し、各ループ反復で別の要素を追加するため、無限ループになります。

    #include <iostream>
#include <list>

using namespace std;

int main()
{
    list<int> ls;

    for(int i = 0; i < 5; i++)
    {
        ls.push_back(i);
    }

    int idx = 0;

    for(list<int>::iterator iter = ls.begin(); iter != ls.end(); iter++)
    {
        cout << "idx: " << idx << ", *iter: " << *iter << endl;
        ls.push_back(7);
        idx++;
    }
}

    ただし、ベクトルに対して同じことを行うと、エラーが発生します。

    #include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> vec;

    for(int i = 0; i < 5; i++)
    {
        vec.push_back(i);
    }

    int idx = 0;

    for(vector<int>::iterator iter = vec.begin(); iter != vec.end(); iter++)
    {
        cout << "idx: " << idx << ", *iter: " << *iter << endl;
        vec.push_back(7);
        idx++;
    }
}

  2. ベクトル コンテナーのサイズを変更する必要がある場合、2 のべき乗でサイズ変更を行い、新しいメモリ領域に配置されると考えました。イテレータは新しいメモリ位置に渡されません)。たとえば、push_back 関数を呼び出した後、16 要素を含むベクターは、32 要素のスペースが割り当てられ、ベクター全体が再配置されると考えました。ただし、これは次のコードでは発生しませんでした。私はちょうど間違っていましたか？ 

    #include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> vec;

    for(int i = 0; i < 4; i++)
    {
        vec.push_back(i);
        cout << "address of vec: " << &vec << ", capacity: " << vec.capacity() << endl;
    }



    for(int i = 0; i < 20; i++)
    {
        vec.push_back(i);
        cout << "address of vec: " << &vec << ", capacity: " << vec.capacity() << endl;
    }
}
4

3 に答える 3

3

コンテナのイテレータが異なれば、プロパティも異なります。イテレータの無効化ルールは次のとおりです。

リスト ループ:list以前のすべてのイテレータをプッシュすると、まだ有効です。明らかに、前に反復するたびに新しい要素も追加すると、最後まで到達することはありません。

ベクトル ループ: ベクトルのpush_back場合、新しいサイズが古い容量を超えると、反復子は無効になります。これが発生するとすぐに、使用iterは未定義の動作になります (クラッシュする可能性があります)。

ベクターコンテナのサイズを変更する必要がある場合、2のべき乗でサイズを変更し、新しいメモリ領域に配置されると思いました

これは標準では規定されていません。C++ 標準ライブラリの一部の実装では、サイズが古い容量を超えた場合にベクトルの容量が 2 倍になり、他の実装では異なる速度で増加します。

于 2013-12-24T20:50:31.200 に答える
0

最初の質問に対する回答は、2 番目の質問に含まれています。

2番目の質問に関しては、ベクトルがメモリを割り当てる方法は実装で定義されています。使い果たされるたびにメモリのサイズを 2 倍にする必要はありません。

于 2013-12-24T20:50:18.513 に答える
0

通常、コンテナーごとに、イテレーターの有効性、および要素へのポインター/参照に関して異なる保証があります。

  1. std::list<T>イテレータと要素へのポインタ/参照は、対応するノードが消去されるか存在するまで有効なままですstd::list<T>。
  2. std::vector<T>有効性はより複雑です 。
    1. イテレータとポインタ/参照の有効性は同じです (以下ではイテレータのみを使用します)。
    2. std::vector<T>が内部バッファのサイズを変更する必要がある場合、つまり挿入が容量を超えた場合、すべてのイテレータは無効になります。容量を超えたときに割り当てられるメモリの量は、実装によって異なります (唯一の要件は、容量が指数関数的に増加することであり、2 倍が合理的な選択ですが、他にも多くの選択肢があります)。
    3. std::vector<T>再割り当てが必要でない限り、挿入ポイントの前にすべての反復子を挿入すると、有効なままになります。
    4. std::vector<T>消去ポイントを過ぎたすべてのイテレータから消去すると、無効になります。

他のコンテナーには、まだ異なる有効性制約があります (たとえば、std::deque<T>イテレーターを無効化し続けますが、ポインター/参照を有効に保つことができます)。

于 2013-12-24T20:53:43.620 に答える