Изменение структуры данных во время итерации по ней

Question

Что происходит, когда вы добавляете элементы к структуре данных, такие как вектор, во время итерации по ней.Разве я не могу этого сделать?

Я пробовал это, и оно ломается:

int main() {
    vector<int> x = { 1, 2, 3 };

    int j = 0;
    for (auto it = x.begin(); it != x.end(); ++it) {
        x.push_back(j);
        j++;
        cout << j << " .. ";
    }
}

Answer 1

Итераторы лишены законной силы некоторыми операциями, которые изменяют std::vector.

Другие контейнеры имеют различные правила относительно того, когда итераторы находятся и не являются недействительными. Это сообщение (по-вашему) с деталями.

Кстати, функция точки входа main() ДОЛЖНА return int:

int main() { ... }

Answer 2

Что происходит, когда вы добавляете элементы к структуре данных, такие как вектор, во время итерации по ней.Могу ли я этого не делать?

Итератор станет недействительным, если вектор изменится сам.Так что вы в безопасности, пока вектор не изменяет свой размер.

Я бы посоветовал вам этого избежать.

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

Изначально вектор имеет некоторую емкость (которую вы можете узнать, вызвав vector::capacity().), И вы добавляете к нему элементы, а когда он заполняется, он выделяет больший объем памяти, копируя элементы из старой памяти во вновь выделенную.памяти, а затем удаляет старую память, и проблема в том, что итератор все еще указывает на старую память, которая была освобождена.Именно так изменение размера делает итератор недействительным.

Вот простая демонстрация.Просто посмотрите, когда capacity изменится:

std::vector<int> v;
for(int i = 0 ; i < 100 ; i++ )
{
  std::cout <<"size = "<<v.size()<<", capacity = "<<v.capacity()<<std::endl;
  v.push_back(i);
}       

Частичный вывод:

size = 0, capacity = 0
size = 1, capacity = 1
size = 2, capacity = 2
size = 3, capacity = 4
size = 4, capacity = 4
size = 5, capacity = 8
size = 6, capacity = 8
size = 7, capacity = 8
size = 8, capacity = 8
size = 9, capacity = 16
size = 10, capacity = 16

См. Полный вывод здесь: http://ideone.com/rQfWe

Примечание: capacity() сообщает максимальное количество элементов, которое вектор может содержать без выделения новой памяти , а size() сообщает количество элементов, которое вектор содержит в настоящее время.

Answer 3

В общем, это плохая идея, потому что если вектор будет изменен, итератор станет недействительным (он помещает указатель в память вектора).

Также не ясно, что ваш код действительно пытается сделать. Если бы итератор как-то не стал недействительным (предположим, он был реализован как индекс), я бы ожидал, что у вас там будет бесконечный цикл - конец никогда не будет достигнут, потому что вы всегда добавляете элементы.

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

vector<int> temp;

// ...

// Inside loop, do this:
temp.push_back(j);

// ...

// After loop, do this to insert all new elements onto end of x
x.insert(x.end(), temp.begin(), temp.end());

Answer 4

Это не очень хорошая идея.

Вы можете подумать о случае, когда ваш вектор должен быть изменен после push_back.Затем его нужно будет перенести в больший объем памяти, и ваши итераторы теперь будут недействительными.

Answer 5

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

Answer 6

В то время как вы использовали vector в качестве примера, есть другие контейнеры stl, которые могут отодвигать элементы без аннулирования итераторов.Выдвижение элемента обратно в std :: list не требует перераспределения существующих элементов, поскольку они не сохраняются непрерывно (списки вместо этого содержат узлы, связанные вместе указателями на следующий узел), поэтому итераторы остаются действительными какузел, на который они указывают, все еще находится по тому же адресу.