Strange remove_if behaviour

[hugo_ribeira]

Hello guys,

this is my code:

"
// CHAPTER 14

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#include "mine.h"

using namespace std;

int x[] = {1,2,1,4,3,2,1,4,5,6,7,8,1,3,1,3};
vector<int> y(x, x + sizeof(x)/sizeof(int));

class equals
{
int _test_case;

public:
equals(int test_case): _test_case(test_case) {}
bool operator()(int var)
{
return _test_case == var;
}
};

int main()
{
for(auto i = y.begin(); i < y.end(); ++i)
cout << *i;

cout << endl << endl;

remove_if(y.begin(), y.end(), equals(1));

for(auto i = y.begin(); i < y.end(); ++i)
cout << *i;

keepopen();
return EXIT_SUCCESS;
}
"

It's suposed to remove all the 1's from y, but it isn't. This is the
output:

1214321456781313

2432456783381313
^ ^

Those 1's were not suposed to be there, or were they?

 

[Alain Ketterlin]

int x[] = {1,2,1,4,3,2,1,4,5,6,7,8,1,3,1,3};
vector<int> y(x, x + sizeof(x)/sizeof(int));

class equals
{
int _test_case;

public:
equals(int test_case): _test_case(test_case) {}
bool operator()(int var)
{
return _test_case == var;
}
};

int main()
{
for(auto i = y.begin(); i < y.end(); ++i)
cout << *i;
cout << endl << endl;
remove_if(y.begin(), y.end(), equals(1));
for(auto i = y.begin(); i < y.end(); ++i)
cout << *i;
return EXIT_SUCCESS;
}
"

It's suposed to remove all the 1's from y, but it isn't. This is the
output:

1214321456781313

2432456783381313

Those 1's were not suposed to be there, or were they?

Yes, this is documentted behavior: remove doesn't remove, it moves them
to the back and returns an iterator to the new "end". You need an
additional call to y.erase().

-- Alain.

 

[hugo_ribeira]

int x[] = {1,2,1,4,3,2,1,4,5,6,7,8,1,3,1,3};
vector<int> y(x, x + sizeof(x)/sizeof(int));

class equals
{
   int _test_case;

   public:
           equals(int test_case): _test_case(test_case) {}
           bool operator()(int var)
                   {
                           return _test_case == var;
                   }
};

int main()
{
   for(auto i = y.begin(); i < y.end(); ++i)
           cout << *i;
   cout << endl << endl;
   remove_if(y.begin(), y.end(), equals(1));
   for(auto i = y.begin(); i < y.end(); ++i)
           cout << *i;
   return EXIT_SUCCESS;
}
"

It's suposed to remove all the 1's from y, but it isn't. This is the
output:


Those 1's were not suposed to be there, or were they?

Yes, this is documentted behavior: remove doesn't remove, it moves them
to the back and returns an iterator to the new "end". You need an
additional call to y.erase().

-- Alain.

But it removed the first 3 ocurrences of 1, it just left the last two.

Besides I'm printing the entire vector so if they were moved to the
back should it be in the output?

 

[Victor Bazarov]

int x[] = {1,2,1,4,3,2,1,4,5,6,7,8,1,3,1,3};
vector<int> y(x, x + sizeof(x)/sizeof(int));

class equals
{
int _test_case;

public:
equals(int test_case): _test_case(test_case) {}
bool operator()(int var)
{
return _test_case == var;
}
};

int main()
{
for(auto i = y.begin(); i< y.end(); ++i)
cout<< *i;
cout<< endl<< endl;
remove_if(y.begin(), y.end(), equals(1));
for(auto i = y.begin(); i< y.end(); ++i)
cout<< *i;
return EXIT_SUCCESS;
}
"

It's suposed to remove all the 1's from y, but it isn't. This is the
output:


Those 1's were not suposed to be there, or were they?

Yes, this is documentted behavior: remove doesn't remove, it moves them
to the back and returns an iterator to the new "end". You need an
additional call to y.erase().

-- Alain.

But it removed the first 3 ocurrences of 1, it just left the last two.

Besides I'm printing the entire vector so if they were moved to the
back should it be in the output?

Can you read? Then *read* the documentation. You need to use the
return value of 'remove_if'. Instead of printing to '.end()', print
only until the return value:

vector<int>::iterator newend = remove_if(...

for (auto i = y.begin(); i != newend; ++i) ...

V

 

[Edek]

int x[] = {1,2,1,4,3,2,1,4,5,6,7,8,1,3,1,3};
vector<int> y(x, x + sizeof(x)/sizeof(int));

class equals
{
int _test_case;

public:
equals(int test_case): _test_case(test_case) {}
bool operator()(int var)
{
return _test_case == var;
}
};

int main()
{
for(auto i = y.begin(); i< y.end(); ++i)
cout<< *i;
cout<< endl<< endl;
remove_if(y.begin(), y.end(), equals(1));
for(auto i = y.begin(); i< y.end(); ++i)
cout<< *i;
return EXIT_SUCCESS;
}
"

It's suposed to remove all the 1's from y, but it isn't. This is the
output:


Those 1's were not suposed to be there, or were they?

Yes, this is documentted behavior: remove doesn't remove, it moves them
to the back and returns an iterator to the new "end". You need an
additional call to y.erase().

-- Alain.

But it removed the first 3 ocurrences of 1, it just left the last two.

Besides I'm printing the entire vector so if they were moved to the
back should it be in the output?

Nothing is actually moved to the back, only moved to front, but
that is an implementation detail and may vary.

The front is stripped if deleted. It is a common misconception,
sometimes people do not read the details in remove_if's documentation,
including myself. Read it carefully again.

One alternative may be remove_copy_if - for remove_if you either use
the returned iterator, or do an extra erase also using this iterator
and you get a good result in the container instead of iterator pair
[start,end)

Edek

 

[Ben Cottrell]

int x[] = {1,2,1,4,3,2,1,4,5,6,7,8,1,3,1,3};
vector<int> y(x, x + sizeof(x)/sizeof(int));

class equals
{
int _test_case;

public:
equals(int test_case): _test_case(test_case) {}
bool operator()(int var)
{
return _test_case == var;
}
};

int main()
{
for(auto i = y.begin(); i < y.end(); ++i)
cout << *i;
cout << endl << endl;
remove_if(y.begin(), y.end(), equals(1));
for(auto i = y.begin(); i < y.end(); ++i)
cout << *i;
return EXIT_SUCCESS;
}
"

It's suposed to remove all the 1's from y, but it isn't. This is the
output:


Those 1's were not suposed to be there, or were they?

Yes, this is documentted behavior: remove doesn't remove, it moves them
to the back and returns an iterator to the new "end". You need an
additional call to y.erase().

-- Alain.

But it removed the first 3 ocurrences of 1, it just left the last two.

Besides I'm printing the entire vector so if they were moved to the
back should it be in the output?

They weren't moved to the back; the goal the algorithm is to remove them
from the range (basically by overwriting them), not to swap them around.

- swapping would be additional unnecessary work; since you've asked for
them to be removed, the assumption is that the data is of no use to you.

the 3 positions at the back are beyond the end of your new valid data
range, and the algorithm knows this so it doesn't make any attempt to
make modifications to those positions.
Essentially those last 3 elements are "junk" data whose value doesn't
matter, and therefore remain unchanged from before you used remove_if.

If you had a range such as

1 2 3 1 2 3 1 2 3 4

then your code would produce

2 3 2 3 2 3 4 2 3 4

- in other words, whatever was at those positions before will still be
there because they are now outside of the 'valid' range.

 

[Stephen Howe]

Change

remove_if(y.begin(), y.end(), equals(1));

to

y.erase(remove_if(y.begin(), y.end(), equals(1)), y.end());

and see
http://en.wikipedia.org/wiki/Erase-remove_idiom

Stephen Howe

 

[Jorgen Grahn]

.

They weren't moved to the back; the goal the algorithm is to remove them
from the range (basically by overwriting them), not to swap them around.

- swapping would be additional unnecessary work; since you've asked for
them to be removed, the assumption is that the data is of no use to you.

the 3 positions at the back are beyond the end of your new valid data
range, and the algorithm knows this so it doesn't make any attempt to
make modifications to those positions.
Essentially those last 3 elements are "junk" data whose value doesn't
matter,

Junk perhaps, but still valid objects. You just don't know which ones.

and therefore remain unchanged from before you used remove_if.


If you had a range such as

1 2 3 1 2 3 1 2 3 4

then your code would produce

2 3 2 3 2 3 4 2 3 4

- in other words, whatever was at those positions before will still be
there because they are now outside of the 'valid' range.

Are you talking about what the standard says here, or about one
particular implementation? The old STL manual states quite clearly
what happens:

Remove_if removes from the range [first, last) every element x such
that pred(x) is true. That is, remove_if returns an iterator
new_last such that the range [first, new_last) contains no elements
for which pred is true. [1] The iterators in the range [new_last,
last) are all still dereferenceable, but the elements that they
point to are unspecified.
-- http://www.sgi.com/tech/stl/remove_if.html

That's not the standard of course, but I'd be surprised if it has
changed.

/Jorgen

 

[Alain Ketterlin]

Besides I'm printing the entire vector so if they were moved to the
back should it be in the output?

Yes, sorry, answered too fast, it's the other way round: items that
remain are moved to the front, "overwriting" the ones that are removed.
Anyway, all details are in the documentation.

-- Alain.

 

[hugo_ribeira]

Thank's guys,

Problem solved and understood.