Привет, я прочитал в учебнике по С++, что добавление элементов в вектор делает недействительными итераторы. Я не понимаю, почему удаление элементов не делает их недействительными, поскольку работает следующий код
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.
То, что какой-то код работает, не означает, что в нем нет ошибок. Неопределенное поведение, к сожалению, часто может казаться "работающим".
Чтобы решить вашу проблему, вам нужно использовать итератор, который возвращает erase.
@Someprogrammerdude ссылка en.cppreference.com/w/cpp/container/vector/erase тоже имеет тот же код
@ArkanSaaS не тот код. В примере есть it = c.erase(it);
@ArkanSaaS Почти тот же код, но работает (с использованием вашего кода) b = a.erase(b)
. Отличие в назначении.
вы не можете доказать наличие или отсутствие неопределенного поведения, запустив код и посмотрев на результат. Вы можете перейти на красный свет светофора и не попасть под машину, но это не делает это законным и не означает, что вас никогда не собьет машина.
Добавление элементов к вектору может привести к полному перераспределению вектора. Это делает недействительными все итераторы, удерживаемые ранее.
Если вы удаляете запись вектора, метод стирания возвращает: а) итератор к следующему допустимому элементу б) конечный итератор.
Но вы должны использовать это. В твоем случае:
b = a.erase(b);
Но что происходит, когда промежуточный элемент удаляется, как поддерживается непрерывность данных?
Его поддерживает перемещение (cplusplus.com/reference/vector/vector/erase). Это эффективно уменьшает размер контейнера на количество удаленных элементов, которые уничтожаются. Поскольку векторы используют массив в качестве базового хранилища, стирание элементов в позициях, отличных от конца вектора, заставляет контейнер перемещать все элементы после стирания сегмента в их новые позиции. Таким образом, каждая запись после удаленного элемента перемещается.
Имейте в виду, что пример cpprefence также делает это = v.erase(it); по сравнению с вашим или оригинальным исходным кодом
В общем, этот фрагмент кода
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, вероятно, реализован как указатель с некоторыми вспомогательными функциями. Удаление одного элемента сместит все, так что тот же самый указатель теперь указывает на новый элемент, где раньше был старый. Это работает только потому, что элементы хранятся в непрерывной памяти без промежутков.
b
становится недействительным послеerase
, и поэтому это UB. Все может случиться, и даже если это работает, это не значит, что это действительно.