CODEWITHSUNDEEP
c++vectoriteratorerase
Paul Grinberg
Paul Grinberg

Reputation: 1477

c++ vector erase advances iterator

The following simplified code works, in that it deletes all vector elements. However, I do not understand why. Since f.erase(r) does not capture the returned value which would be the new iterator value, and there is no other iterator incrementor, and according to documentation, erase(iterator position) argument is not passed by reference, where does the iterator get advanced?

#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;
}

Upvotes: 0

Views: 2279

Answers (7)

Vlad from Moscow
Vlad from Moscow

Reputation: 311156

You have to write

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

because after erasing the iterator becomes invalid.

Or you could just write

f.clear();

because the loop removes all elements of the vector.

Take into account that as the iterator r is used only in the loop it is better to declare it in the scope of the loop that is where it is used. for example

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

Upvotes: 2

Oblivion
Oblivion

Reputation: 7374

Adding/removing elements to/from vector in most cases (that includes erase())invalidates references and iterators. Using old iterators results in undefined behavior.

As @Nathan mentioned in the comments f.clear() is all you need.

Upvotes: 1

Marek R
Marek R

Reputation: 38209

and according to documentation,

You should read it to the end:

vector::erase - C++ Reference

Because vectors use an array as their underlying storage, erasing elements in positions other than the vector end causes the container to relocate all the elements after the segment erased to their new positions. This is generally an inefficient operation compared to the one performed for the same operation by other kinds of sequence containers (such as list or forward_list).

and

Return value

An iterator pointing to the new location of the element that followed the last element erased by the function call. This is the container end if the operation erased the last element in the sequence.

vector::erase - C++ Reference

And finally:

Iterator validity

Iterators, pointers and references pointing to position (or first) and beyond are invalidated, with all iterators, pointers and references to elements before position (or first) are guaranteed to keep referring to the same elements they were referring to before the call.

Upvotes: 1

HolyBlackCat
HolyBlackCat

Reputation: 96976

erase invalidates r. Dereferening r after that causes undefined behavior.

But in the real world, it shouldn't cause any problems unless the implementation intentionally checks iterator validity.

A vector iterator normally only stores a pointer to the element. When you delete an element, all elements to the right of it are shifted to the left by one position. Because of that, the memory location that used to be occupied by the deleted element, will be occupied by the next element.

Upvotes: 0

NathanOliver
NathanOliver

Reputation: 181068

where does the iterator get advanced?

It doesn't, the iterator stays pointing to the same location. This is technically undefined behavior but if you think about what the loop is actually doing, you'll see why you get the "correct" results.

Your vector holds a pointer to the objects that it stores. Your iterator is going to point to that memory with the offset to the element you want. In this case it is going to point to the beginning of the data. When you erase the first element, the iterator is invalidated but it is still pointing to the beginning of the vector. erase moves all of the elements forward so when you go into the next iteration, your in the same state that you were in the first iteration except the vector is one element smaller. You repeatedly do this until there are no elements left and end() == begin()

You should not depend on this always happening though and instead just use clear() to remove all of the elements from the vector.

Upvotes: 2

eerorika
eerorika

Reputation: 238461

Passing the iterator to erase invalidates that iterator, and therefore using it further (when passing it to erase in the next iteration) has undefined behaviour. Thus, the program doesn't actually "work". It may appear to work, because that is one possible behaviour. But that behaviour is not guaranteed.

Upvotes: 0

463035818_is_not_an_ai
463035818_is_not_an_ai

Reputation: 123488

where does the iterator get advanced?

The iterator does not get advanced. The fact that your code seems to work is just by chance and in fact you have undefined behaviour.

From cppreference on std::vector::erase:

Invalidates iterators and references at or after the point of the erase, including the end() iterator.

You are not allowed to use r after calling f.erase(r);. If you do, funny things can happen.

Upvotes: 2

Related Questions