С++ векторное стирание продвигает итератор

Следующий упрощенный код работает, поскольку он удаляет все элементы вектора. Однако я не понимаю, почему. Поскольку f.erase(r) не фиксирует возвращаемое значение, которое было бы новым значением итератора, и нет другого инкремента итератора, и согласно документации, erase(iterator position) аргумент не передается по ссылке, где итератор получает дополнительные возможности?

#include <iostream>
#include <vector>

int main ()
{
  std::vector<int> f = {1,2,3,4,5};
  auto r = f.begin();
  while (r != f.end())
  {
    std::cout << "Erasing " << *r << std::endl;
    f.erase(r);
  }
  return 0;
}

person Paul Grinberg    schedule 25.10.2019    source источник
comment
Добро пожаловать в страну неопределенного поведения, где результат, которого вы хотите, может быть даже результатом, который вы получаете. Если вы хотите очистить вектор, просто используйте clear() -> f.clear();   -  person NathanOliver    schedule 25.10.2019
comment
erase делает недействительными итераторы, поэтому после этого вы не должны использовать r. это работает, это худшее воплощение неопределенного поведения   -  person 463035818_is_not_a_number    schedule 25.10.2019


Ответы (7)


где итератор становится продвинутым?

Это не так, итератор продолжает указывать на одно и то же место. Технически это неопределенное поведение, но если вы задумаетесь о том, что на самом деле делает цикл, вы поймете, почему вы получаете «правильные» результаты.

Ваш вектор содержит указатель на объекты, которые он хранит. Ваш итератор будет указывать на эту память со смещением к нужному элементу. В этом случае он будет указывать на начало данных. Когда вы стираете первый элемент, итератор становится недействительным, но он все еще указывает на начало вектора. erase перемещает все элементы вперед, поэтому, когда вы переходите к следующей итерации, вы находитесь в том же состоянии, что и в первой итерации, за исключением того, что вектор на один элемент меньше. Вы повторяете это до тех пор, пока не останется элементов и end() == begin()

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

person NathanOliver    schedule 25.10.2019

где итератор становится продвинутым?

Итератор не продвигается. Тот факт, что ваш код работает, является случайностью, и на самом деле у вас неопределенное поведение.

Из cppreference на std::vector::erase:

Делает недействительными итераторы и ссылки в точке стирания или после нее, включая итератор end().

Вам не разрешено использовать r после вызова f.erase(r);. Если вы это сделаете, могут произойти забавные вещи.

person 463035818_is_not_a_number    schedule 25.10.2019

Вы должны написать

  while (r != f.end())
  {
    std::cout << "Erasing " << *r << std::endl;
    r = f.erase(r);
   ^^^^^^^^^^^^^^^^
  }

потому что после стирания итератор становится недействительным.

Или вы могли бы просто написать

f.clear();

потому что цикл удаляет все элементы вектора.

Учтите, что поскольку итератор r используется только в цикле, лучше объявить его в области действия цикла, где он используется. Например

  for ( auto r = f.begin(); r != f.end(); )
  {
    std::cout << "Erasing " << *r << std::endl;
    r = f.erase(r);
  }
person Vlad from Moscow    schedule 25.10.2019

и согласно документации,

Вы должны прочитать его до конца:

vector::erase — Справочник по C++

Поскольку векторы используют массив в качестве базового хранилища, стирание элементов в позициях, отличных от конца вектора заставляет контейнер перемещать все элементы после удаления сегмента на их новые позиции. Как правило, это неэффективная операция по сравнению с той, которую выполняют для той же операции контейнеры последовательностей других типов (например, list или forward_list).

и

Возвращаемое значение

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

vector::erase — Справочник по C++

И наконец:

Срок действия итератора

Итераторы, указатели и ссылки, указывающие на position (или first) и далее, становятся недействительными со всеми итераторами, указателями и ссылками на элементы до position ( или first) гарантированно будут ссылаться на те же элементы, на которые они ссылались до вызова.

person Marek R    schedule 25.10.2019

Добавление/удаление элементов в/из вектора в большинстве случаев (включая стирание()) делает ссылки и итераторы недействительными. Использование старых итераторов приводит к неопределенному поведению.

Как упомянул @Nathan в комментариях, f.clear() - это все, что вам нужно.

person Oblivion    schedule 25.10.2019

Передача итератора в erase делает этот итератор недействительным, и поэтому его дальнейшее использование (при передаче его в erase на следующей итерации) имеет неопределенное поведение. Таким образом, программа на самом деле не "работает". Может показаться, что это работает, потому что это одно из возможных действий. Но такое поведение не гарантируется.

person eerorika    schedule 25.10.2019

erase делает недействительным r. Разыменование r после этого приводит к неопределенному поведению.


Но в реальном мире это не должно вызывать никаких проблем, если реализация намеренно не проверяет правильность итератора.

Итератор vector обычно хранит только указатель на элемент. При удалении элемента все элементы справа от него сдвигаются влево на одну позицию. Из-за этого ячейка памяти, которую раньше занимал удаленный элемент, будет занята следующим элементом.

person HolyBlackCat    schedule 25.10.2019
comment
Почему минус? Объяснение УБ теперь считается ересью? :П - person HolyBlackCat; 25.10.2019
comment
Не минусовал, но это не должно вызывать проблем... Просто нет. И не только из-за ложных срабатываний в проверенных билдах. - person Max Langhof; 25.10.2019
comment
@MaxLanghof Я не могу придумать никакой другой причины, по которой это может сломать что-то. - person HolyBlackCat; 25.10.2019