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?

Quote:

---

you can also use remove_if():

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

---

Cool! I didn't know that.

Quote:

---

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.

Bjarne recently (well, okay, in february this year) showed a slide (okay, so it wasn't visible, but he explained his point) where it showed that a vector usually beats a list in many cases where you wouldn't expect it.
The reason is cache performance, since linked lists jump randomly, they're horrible for cache performance, but vectors are contiguous, which caches love.
So actually, try a vector first, and if it's slow, then time it with a list. You might be surprised at the results.

Quote:

---

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.

I am trying to think of a time I used std::list for something. I am coming up blank.

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.

Quote:

---

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.

If you have a double-linked list, you don't need to find the location to insert... well, at least if you don't want to keep your structure sorted.

Quote:

---

Originally Posted by Elysia

If you have a double-linked list, you don't need to find the location to insert... well, at least if you don't want to keep your structure sorted.

---

And if you do want to keep it sorted, then a list is not necesarily the best choice.

I think it's more a case that a lookup, for the reasons of inserting or otherwise, is O(n).
I can only think of about one place where I think I used list over all the other cotainers.