Каково поведение вектора здесь? - PullRequest
Новая
       19

Каково поведение вектора здесь?

0 голосов
/ 17 февраля 2020

Я не могу понять, почему в тесте, показанном ниже, итератор p никогда не достигает конца, и поэтому l oop ломается только тогда, когда k = 20? Что именно делает push_back, чтобы вызвать неопределенное поведение? Это потому, что вектор динамически выделяет кучу дополнительного хранилища для новых элементов, которые я хочу использовать, а сумма не обязательно равна сумме, которую я буду использовать? 

#include <iostream>
#include <vector>
#include <list>
using namespace std;

const int MAGIC = 11223344;

void test()
{
    bool allValid = true;

    int k = 0;
    vector<int> v2(5, MAGIC);
    k = 0;
    for (vector<int>::iterator p = v2.begin(); p != v2.end(); p++, k++)
    {
        if (k >= 20)  // prevent infinite loop
            break;
        if (*p != MAGIC)
        {
            cout << "Item# " << k << " is " << *p << ", not " << MAGIC <<"!" << endl;
            allValid = false;
        }
        if (k == 2)
        {
            for (int i = 0; i < 5; i++)
                v2.push_back(MAGIC);
        }
    }
    if (allValid  &&  k == 10)
        cout << "Passed test 3" << endl;
    else
        cout << "Failed test 3"  << "\n" <<  k << endl;
}

int main()
{
    test();
}

1 Ответ

0 голосов
/ 17 февраля 2020

Вставка в вектор во время итерации - плохая идея. Вставка данных может привести к перераспределению памяти, что делает недействительными итераторы. В этом случае емкости было недостаточно для вставки дополнительных элементов, что вызвало выделение памяти с другим адресом. Вы можете проверить это сами: 

void test() 
{
    bool allValid = true;
    int k = 0;
    vector<int> v2(5, MAGIC);
    k = 0;

    for (vector<int>::iterator p = v2.begin(); p != v2.end(); p++, k++) 
    {
        cout << v2.capacity() << endl; // Print the vector capacity

        if (k >= 20)  // prevent infinite loop
            break;

        if (*p != MAGIC) {
            //cout << "Item# " << k << " is " << *p << ", not " << MAGIC <<"!" << endl;
            allValid = false;
        }
        if (k == 2) {
            for (int i = 0; i < 5; i++)
                v2.push_back(MAGIC);
        }
    }
    if (allValid && k == 10)
        cout << "Passed test 3" << endl;
    else
        cout << "Failed test 3" << "\n" << k << endl;
}

Этот код выведет что-то вроде следующего: 

5
5
5
10 <-- the capacity has changed
10
... skipped ...
10
10
Failed test 3
20

Мы можем видеть, что где k равно 2 (третья строка), емкость вектора удвоилось (четвертая строка), потому что мы добавляем новые элементы. Память перераспределяется, и векторные элементы, скорее всего, теперь находятся в другом месте. Вы также можете проверить это, напечатав векторный базовый адрес с помощью data функции-члена вместо capacity: 

Address: 0x136dc20 k: 0
Address: 0x136dc20 k: 1
Address: 0x136dc20 k: 2
Address: 0x136e050 k: 3 <-- the address has changed
Address: 0x136e050 k: 4
... skipped ...
Address: 0x136e050 k: 19
Address: 0x136e050 k: 20
Failed test 3
20

Код написан плохо, вы можете сделать его более устойчивым, используя индексы вместо итераторов.

...