20

There have been a few questions regarding this issue before; my understanding is that calling std::vector::erase will only invalidate iterators which are at a position after the erased element. However, after erasing an element, is the iterator at that position still valid (provided, of course, that it doesn't point to end() after the erase)?

My understanding of how a vector would be implemented seems to suggest that the iterator is definitely usable, but I'm not entirely sure if it could lead to undefined behavior.

As an example of what I'm talking about, the following code removes all odd integers from a vector. Does this code cause undefined behavior?

typedef std::vector<int> vectype;
vectype vec;

for (int i = 0; i < 100; ++i) vec.push_back(i);

vectype::iterator it = vec.begin();
while (it != vec.end()) {
    if (*it % 2 == 1) vec.erase(it);
    else ++it;
}

The code runs fine on my machine, but that doesn't convince me that it's valid.

James McNellis
  • 348,265
  • 75
  • 913
  • 977
Channel72
  • 283
  • 1
  • 2
  • 5

2 Answers2

43

after erasing an element, is the iterator at that position still valid

No; all of the iterators at or after the iterator(s) passed to erase are invalidated.

However, erase returns a new iterator that points to the element immediately after the element(s) that were erased (or to the end if there is no such element). You can use this iterator to resume iteration.

Note that this particular method of removing odd elements is quite inefficient: each time you remove an element, all of the elements after it have to be moved one position to the left in the vector (this is O(n2)). You can accomplish this task much more efficiently using the erase-remove idiom (O(n)). You can create an is_odd predicate:

bool is_odd(int x) { return (x % 2) == 1; }

Then this can be passed to remove_if:

vec.erase(std::remove_if(vec.begin(), vec.end(), is_odd), vec.end());
James McNellis
  • 348,265
  • 75
  • 913
  • 977
0

Or:

class CIsOdd
{
public:
    bool operator()(const int& x) { return (x % 2) == 1; }
};

vec.erase(std::remove_if(vec.begin(), vec.end(), CIsOdd()), vec.end());
ssianky
  • 97
  • 7
  • 1
    Why do you pass `x` by const reference instead of by value? – fredoverflow Sep 20 '10 at 08:14
  • 3
    Question: why do people often favor the approach here (functor with only operator() overloaded, i.e. no state/data) vs. a simple freestanding function like in James McNellis' answer above? I understand they'll both work, but I usually take the same approach as James, to me it seems simpler & more obvious. At a certain point, I start to ask myself, "what am I missing?" If it's just personal preference, that's fine. – Dan Sep 20 '10 at 19:28
  • @FredOverflow, x can be a strucure, @Dan, ...and operator() a member of that structure – ssianky Sep 21 '10 at 02:15
  • @ssianky Late, I know, but for completeness: No, if `x` gets a structure `operator()` remains a member of `CIsOdd`, whether `x` comes with its own operator nor not. And actually `x` cannot be a struct either (it's an `int`) *unless* you modify `CIsOdd` to accept something different. Reference would be a near *must* for templates, though... – Aconcagua Aug 09 '22 at 15:09