4

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?

Sasha Chedygov
  • 127,549
  • 26
  • 102
  • 115
user198729
  • 61,774
  • 108
  • 250
  • 348

4 Answers4

8

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.

GManNickG
  • 494,350
  • 52
  • 494
  • 543
4

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.

kevlar
  • 1,110
  • 3
  • 17
  • 30
  • can also replace the `if(...)` with `while(...)`, as long as the condition can also tell when it's past the end of the vector. – goldPseudo Sep 05 '10 at 05:30
  • I don't quite understand GMan's solution,so I accept this hack version. – user198729 Sep 05 '10 at 05:36
  • 1
    @user: You should ask for clarification and/or get [a book](http://stackoverflow.com/questions/388242/the-definitive-c++-book-guide-and-list) to teach you C++. – GManNickG Sep 05 '10 at 05:46
  • 1
    btw: `erase()` returns a new (valid) iterator to the next element after the erased one. – sth Sep 06 '10 at 07:43
  • @sth I see, you're right. Ivan's edited solution uses that fact. – kevlar Sep 06 '10 at 18:02
1

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.

mpen
  • 272,448
  • 266
  • 850
  • 1,236
0

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;
}
Ivan Krechetov
  • 18,802
  • 8
  • 49
  • 60
  • This seems to be the easiest solution,but I'm not sure whether it really works? – user198729 Sep 05 '10 at 05:14
  • 3
    I guess the one after the erased entry will be skipped by `it++` – user198729 Sep 05 '10 at 05:18
  • this is slightly broken, you need to not do thr `it++` when the if is true (otherwise you can skip over an element or worse yet, you can skip over `end()`. Better would be this: `for (it = v.begin(); it != v.end();) { if(...) it = v.erase(it); else ++it; }` – Evan Teran Sep 05 '10 at 06:30
  • 3
    It is also worth noting that this is algorithmically terrible, because `erase` will cause all of the following elements to be "moved down one" the remove_if/erase idiom is much better because it avoids this. – Evan Teran Sep 05 '10 at 06:32
  • Yep, all true. Thanks for your comments. Will add "continue" now, and move the increment down. – Ivan Krechetov Sep 06 '10 at 07:09