vector & remove_if

[mickey]

Hello,
this below doens't work but it gives the idea (hope) of my problem:

class Feature {
public:

bool isNotValid(int i) {
return this->_indexMissedMask[i];
}
void compute() {
vector<double>::iterator iter = remove_if(validValue.begin(),
validValue.end(), &Feature::isNotValid );

}

_indexMissedMask is a vector of bool like this: false, false, true, false........
I have to remove from validValue all elements at the position with _indexMissedMask is "true".
Any hints, please?

[wysota]

for(int i = validValue.size()-1;i>=0;i--)
if(_indexMissedMask[i])
validValue.removeAt(i); // or equivalent

[mickey]

for(int i = validValue.size()-1;i>=0;i--)
if(_indexMissedMask[i])
validValue.removeAt(i); // or equivalent
How always you've found the simplest solution (that always was there)....
But wanting use that way above, just only to learn to use algorithm generics....how could I do?
Furthermore: isn't "remove_if" above faster than your suggestion?
thanks,

[caduel]

you have to erase the rest... remove_if does not erase the elements. it reorders the vector and returns an iterator pointing to the 'new end'.

See http://www.sgi.com/tech/stl/remove_if.html

[mickey]

for(int i = validValue.size()-1;i>=0;i--)
if(_indexMissedMask[i])
validValue.removeAt(i); // or equivalent

hello,
I write this and seems work but I don't know why. In fact, I encountered some problem from the fact that, when I call erase(), the size of vector change and increment the iterator can cause crash at runtime:

vector<double>::iterator ivalid = validValue.end() - 1;
vector<bool>::iterator imask = _indexMissedMask.end() - 1;
for ( ; imask != _indexMissedMask.begin(); --imask, /*--ivalid*/) { //here "--ivalid crash program"
if ( *imask )
validValue.erase(ivalid--);
}

Could you tell me why there crash "--ivalid", please?

[caduel]

If you erase the element at ivalid you decrement the iterator twice.
once in the loop's body, and once in the for-statement.

Coding (even such trivial) stuff again just introduces further possibilities for errors. Try to use the available algorithms like remove_if, erase etc.

HTH

[mickey]

sorry,
what I meant was:
This seems work:

vector<double>::iterator ivalid = validValue.end() - 1;
vector<bool>::iterator imask = _indexMissedMask.end() - 1;
for ( ; imask != _indexMissedMask.begin(); --imask) {
if ( *imask )
validValue.erase(ivalid--);
}

This crashes:

vector<double>::iterator ivalid = validValue.end() - 1;
vector<bool>::iterator imask = _indexMissedMask.end() - 1;
for ( ; imask != _indexMissedMask.begin(); --imask, --ivalid) {
if ( *imask )
validValue.erase(ivalid);
}
Why, please?

[caduel]

The code above is wrong (twice decrementing of iterator).
The code below is wrong, too: after erase() the iterator ivalid is no longer valid.
You would have to do something like

vector<double>::iterator ivalid = validValue.end() - 1;
vector<bool>::iterator imask = _indexMissedMask.end() - 1;
for ( ; imask != _indexMissedMask.begin(); --imask)
{
vector<double>::iterator tmp = ivalid;
--tmp;
if ( *imask )
validValue.erase(ivalid); // invalidates ivalid; would return iterator pointing behind it
ivalid=tmp;
}
(untested, of course)

This is why you should not reinvent the wheel yourself. Use the algorithms.

[wysota]

But wanting use that way above, just only to learn to use algorithm generics....how could I do?

You have to start with the last element and not the first one, that's for sure. Otherwise probably your iterators/indexes on both containers will go out of sync.

Furthermore: isn't "remove_if" above faster than your suggestion?
No, you can't get better than O(n) here - you have to check each element (so it's actually omega(n) and theta(n)).