Инвалидация итераторов

Привет, я прочитал в учебнике по С++, что добавление элементов в вектор делает недействительными итераторы. Я не понимаю, почему удаление элементов не делает их недействительными, поскольку работает следующий код

std::vector<int> a = {1,2,3,4,5,6};

auto b = a.begin();

while (b != a.end()){
    
    if (*b%2 != 0)
        a.erase(b);
    else
        b++;
}

ПРИМЕЧАНИЕ. Этот код взят из самого учебника по C++, а также из cpp reference.

b становится недействительным после erase, и поэтому это UB. Все может случиться, и даже если это работает, это не значит, что это действительно.
wohlstad 13.01.2023 11:02

То, что какой-то код работает, не означает, что в нем нет ошибок. Неопределенное поведение, к сожалению, часто может казаться "работающим".

Some programmer dude 13.01.2023 11:02
std::vector::erase "... делает недействительными итераторы и ссылки в точке стирания или после нее, включая итератор end()...". "invalidates" означает, что код не должен их использовать, и если это так, то он получает Undefined Behavior. Неопределенное поведение включает видимость работы.
Richard Critten 13.01.2023 11:02

Чтобы решить вашу проблему, вам нужно использовать итератор, который возвращает erase.

Some programmer dude 13.01.2023 11:03

@Someprogrammerdude ссылка en.cppreference.com/w/cpp/container/vector/erase тоже имеет тот же код

ArkanSaaS 13.01.2023 11:40

@ArkanSaaS не тот код. В примере есть it = c.erase(it);

463035818_is_not_a_number 13.01.2023 12:03

@ArkanSaaS Почти тот же код, но работает (с использованием вашего кода) b = a.erase(b). Отличие в назначении.

Some programmer dude 13.01.2023 12:03

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

463035818_is_not_a_number 13.01.2023 12:05
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
2
8
94
5
Перейти к ответу Данный вопрос помечен как решенный

Ответы 5

Добавление элементов к вектору может привести к полному перераспределению вектора. Это делает недействительными все итераторы, удерживаемые ранее.

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

Но вы должны использовать это. В твоем случае:

b = a.erase(b);

Но что происходит, когда промежуточный элемент удаляется, как поддерживается непрерывность данных?

ArkanSaaS 13.01.2023 11:44

Его поддерживает перемещение (cplusplus.com/reference/vector/vector/erase). Это эффективно уменьшает размер контейнера на количество удаленных элементов, которые уничтожаются. Поскольку векторы используют массив в качестве базового хранилища, стирание элементов в позициях, отличных от конца вектора, заставляет контейнер перемещать все элементы после стирания сегмента в их новые позиции. Таким образом, каждая запись после удаленного элемента перемещается.

Gunther 13.01.2023 11:48

Имейте в виду, что пример cpprefence также делает это = v.erase(it); по сравнению с вашим или оригинальным исходным кодом

Gunther 13.01.2023 11:52
Ответ принят как подходящий

В общем, этот фрагмент кода

auto b = a.begin();

while (b != a.end()){
    
    if (*b%2 != 0)
        a.erase(b);
    else
        b++;
}

является недействительным. Это работает, потому что контейнер std::vector удовлетворяет концепции смежных диапазонов. Если вместо вектора вы будете использовать например std::list<int>, когда итератор b будет недействителен.

Правильно было бы написать

auto b = a.begin();

while (b != a.end()){
    
    if (*b%2 != 0)
        b = a.erase(b);
    else
        b++;
}

Распространенная идиома. Из cppreference: (erase) 'Деактивирует итераторы и ссылки в точке стирания или после нее, включая итератор end().

Другие указали, что это должно быть написано так:

#include <vector>

std::vector<int> vec = { 1, 2, 3, 4 };

for (auto it = vec.begin(); it != vec.end(); )
{
    if (*it % 2 != 0)
    {
        it = vec.erase(it);
    }
    else
    {
       ++it;
    }
}

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

Обновлено: фрагмент кода — это буквально ссылка cppreference.

На самом деле это не ответ на вопрос, но я думаю, что стоит упомянуть, что в современном С++ вы должны стараться избегать итераторов, используя алгоритмы и циклы for на основе диапазона. В этом конкретном случае используйте std::erase_if:

std::vector<int> a = {1,2,3,4,5,6};
std::erase_if (a, [](int x) { return x%2 != 0; });

Как многие указывали, это работает случайно. Не делайте этого в прод. Итераторы спроектированы так, чтобы быть как можно более легкими, поэтому не будет флага, говорящего о том, что они недействительны. Это было бы слишком расточительно.

Итератор std::vector, вероятно, реализован как указатель с некоторыми вспомогательными функциями. Удаление одного элемента сместит все, так что тот же самый указатель теперь указывает на новый элемент, где раньше был старый. Это работает только потому, что элементы хранятся в непрерывной памяти без промежутков.

Другие вопросы по теме