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

Member
Posts: 321
Joined: 2004.10
Post: #1
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?
Quote this message in a reply
Puzzler183
Unregistered
 
Post: #2
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.
Quote this message in a reply
Puzzler183
Unregistered
 
Post: #3
Actually here, easy thing to do:

Code:
[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.
Quote this message in a reply
Member
Posts: 184
Joined: 2004.07
Post: #4
The erase method returns the next element after the one you just erased. So you can use that to continue in your loop.
Code:
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.
Quote this message in a reply
Puzzler183
Unregistered
 
Post: #5
Erm d'oh, I should have known that.... Still, a list is probably a better choice...
Quote this message in a reply
Member
Posts: 131
Joined: 2004.10
Post: #6
How about...

Code:
int i
vector c;
for ( i = c.size(), i >=0, i--)
{
   if (c[i] == something)
   {
      c.erase(c.begin() + i);
   }
}
Quote this message in a reply
Puzzler183
Unregistered
 
Post: #7
phydeaux's is better (more clear). However, it should be in for loop notation:

Code:
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 Smile.
Quote this message in a reply
Post Reply