How to erase entries from vector in C++ ?

Question

I'm basically looping through all the entries to check whether some entries is to be erased, but seems in a wrong way:

std::vector<HANDLE> myvector; 
for(unsigned int i = 0; i < myvector.size(); i++)
{
    if(...)
         myvector.erase(myvector.begin()+i);
}

Anyone spot the problem in it? How to do it correctly?

Answer 1

You can use std::remove_if. This will move all remaining elements to the front, and returns an iterator to the new back. You can then erase it:

struct my_predicate
{
    bool operator()(HANDLE) const
    {
        return ...;
    }
};

typedef std::vector<HANDLE> vector_type;

vector_type::iterator newEnd =
    std::remove_if(myvector.begin(), myvector.end(), my_predicate());

myvector.erase(newEnd, myvector.end());

It's commonly done on one line. If your compiler supports lambda's (C++0x), you can do:

vector_type::iterator newEnd =
    std::remove_if(myvector.begin(), myvector.end(), [](HANDLE){ return ... });

myvector.erase(newEnd, myvector.end());

To keep the predicate local.

---

If you think this is ugly, just wrap it up:

template <typename Vec, typename Pred>
Pred erase_if(Vec& pVec, Pred pPred)
{
    pVec.erase(std::remove_if(pVec.begin(), pVec.end(),
                                pPred), pVec.end());

    return pPred;
}

Then:

erase_if(myvector, mypredicate);

C++0x lambda's work the same, of course.

Answer 2

You should use vector iterator for that, AND, on deletion, assign the iterator the value returned by erase()

for (it = myvector.begin(); it != myvector.end();) {
    if (...) {
        it = myvector.erase(it);
        continue;
    }

    ++it;
}

Answer 3

Your problem is algorithmic. What happens if two adjacent elements meet your criterion for deletion? The first will be deleted, but because i is incremented after each iteration of the loop, the second will be skipped. This is because a vector is contiguous in memory, and all elements after the deleted one are moved forwards one index.

An ugly hack would be to do the following:

std::vector<HANDLE> myvector; 
for(unsigned int i = 0; i < myvector.size();)
{
    if(...)
         myvector.erase(myvector.begin()+i);
    else
         i++;
}

I'm not sure if using iterators would work, because calling erase invalidates iterators to elements after the erased element.

The elegant solution would be to use std::remove_if, as GMan suggested. This would abstract away two things:

1. Your removal condition
2. The process by which the elements of a container are removed

Edit: I should also add, the hacked solution is O(n²) in the worst case. GMan's solution is O(n), assuming your removal condition is O(1). I would strongly encourage you to learn and use GMan's solution.

Answer 4

Perhaps another hacky solution...

std::vector<HANDLE> myvector; 
for(unsigned int i = myvector.size()-1; i >=0; --i)
{
    if(...)
         myvector.erase(myvector.begin()+i);
}

But at least it's simple.