Thread: Vector erase loop invalidating iterators

How do you do something like check all elements in a vector for some condition, and erase those that meet the condition?

I have always been doing something like this -

Code:

for (std::vector<T>::iterator it = v.begin(); it != v.end();)
{
     std::vector<T>::iterator next = it + 1;
     if (should_remove(*it))
     {
          v.erase(it);
     }
     it = next;
}

The problem is, I just realized, if the element removed is the last element, "it" will end up pointing to end()+1, and bad things will happen.

I can do a special case for last element, but is there a cleaner way?

Ah! Found it. erase() returns iterator to the next element, or endl if last.

Code:

for (std::vector<T>::iterator it = v.begin(); it != v.end();)
{
     if (should_remove(*it))
     {
          it = v.erase(it);
     }
     else
     {
          ++it;
     }
}

you can also use remove_if():

#include <algorithm>
remove_if(v.begin(), v.end(), should_remove);

Btw...shouldn't you be using std::list for this?

you can also use remove_if():

#include <algorithm>
remove_if(v.begin(), v.end(), should_remove);

Cool! I didn't know that.

Btw...shouldn't you be using std::list for this?

Nope... I only need to do this very infrequently, and need fast random access all the time.

Originally Posted by Elysia

since linked lists jump randomly, they're horrible for cache performance, but vectors are contiguous, which caches love.

it's for this reason that managed technologies like java and .Net have trouble competing with the performance of fully native code. even arrays in those languages are still just arrays of pointers, which may point to anywhere in the process's address space.

for very large collections of items, a std::list will be more efficient on insertions and deletions, but because the items are not guaranteed to be contiguous in memory, iterating over them will likely be slower than a vector or a real array.

Originally Posted by Elkvis

for very large collections of items, a std::list will be more efficient on insertions and deletions, but because the items are not guaranteed to be contiguous in memory, iterating over them will likely be slower than a vector or a real array.

Not really. For a vector, locating the correct position to insert is O(1) and inserting is O(n). For list, inserting is O(1) but finding the location to insert is O(n). I've never seen a situation where the trade-off favored list. There are obviously siyuations where it might, but those are academic, mostly.