insert() and erase() with C++ STL vector and deque

[WhatMeWorry]

Many times I've come across the following caveat:

"Be careful if you erase() or insert() elements in the middle of a vector. This can invalidate all existing iterators."

And I played around with an STL loop in the following general form:

// extremely rough pseudo code from memory

vector c; terator i
for ( i = c.begin, i = c.end, i++)
{
if (i == something)
{
c.erase(i)
}
}

And sure enough, the iterator was screwed up after the erase().

OK, so is there a preferred method (idiom) for dealing with the
invalidation of the iterator after the erase() of insert()?

One quick and dirty fix that I did was to put a break command after the
c.erase which would exit the loop. Was wondering if there was a
better approach. Maybe the above form is not even recommended?

[Puzzler183]

A better approach is to use std::list on something you are doing a lot of inserts and erases on because they are O(n) with std::vectors and O(1) with lists. This of course assumes you are only needing iterative access (not random).

And if you insist on using a vector or need the random access, then just keep track of how far you are in the vector and get a new iterator.

[Puzzler183]

Actually here, easy thing to do:


[5] A vector's iterators are invalidated when its memory is reallocated.
Additionally, inserting or deleting an element in the middle of a vector invalidates
all iterators that point to elements following the insertion or deletion point. It
follows that you can prevent a vector's iterators from being invalidated if you use
reserve() to preallocate as much memory as the vector will ever use, and if all
insertions and deletions are at the vector's end.


That's from the SGI docs. So basically, if you keep an iterator one before the one you erase, and then increment it, it will be valid.

[phydeaux]

The erase method returns the next element after the one you just erased. So you can use that to continue in your loop.

vector c;
iterator i = c.begin();
while(i != c.end()){
if (i == something) {
i = i.erase();
} else {
i++;
}
}


If the erase causes the vector to re-allocate memory, it should correctly return the next element to you after the allocation is finished.

[Puzzler183]

Erm d'oh, I should have known that.... Still, a list is probably a better choice...

[Zekaric]

How about...

int i
vector c;
for ( i = c.size(), i >=0, i--)
{
if (c[i] == something)
{
c.erase(c.begin() + i);
}
}

[Puzzler183]

phydeaux's is better (more clear). However, it should be in for loop notation:


std::vector<some type> c;
for (std::vector<some type>::iterator i = c.begin(); i != c.end(); )
if (<some condition>)
i = i.erase();
else
++i;


And remember kids, always preincrement your variables to prevent the creation of temporaries on classes with the operator overloaded :).