CODEWITHSUNDEEP
c++windowsvector
user198729
user198729

Reputation: 63646

How to erase entries from vector in C++?

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?

Upvotes: 4

Views: 1078

Answers (4)

mpen
mpen

Reputation: 282885

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.

Upvotes: 1

Ivan Krechetov
Ivan Krechetov

Reputation: 19220

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;
}

Upvotes: 0

kevlar
kevlar

Reputation: 1173

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(n2) 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.

Upvotes: 4

GManNickG
GManNickG

Reputation: 503913

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.

Upvotes: 8

Related Questions