Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #11000 > unrolled thread

Strange remove_if behaviour

Back to article view | Back to comp.lang.c++

Contents

  Strange remove_if behaviour "hugo_ribeira@hotmail.com" <hugo_ribeira@hotmail.com> - 2011-10-20 02:58 -0700
    Re: Strange remove_if behaviour Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2011-10-20 12:14 +0200
      Re: Strange remove_if behaviour "hugo_ribeira@hotmail.com" <hugo_ribeira@hotmail.com> - 2011-10-20 05:17 -0700
        Re: Strange remove_if behaviour Victor Bazarov <v.bazarov@comcast.invalid> - 2011-10-20 08:29 -0400
        Re: Strange remove_if behaviour Edek <edek.pienkowski@gmail.com> - 2011-10-20 18:02 +0200
        Re: Strange remove_if behaviour Ben Cottrell <email@address.invalid> - 2011-10-20 17:25 +0100
          Re: Strange remove_if behaviour Jorgen Grahn <grahn+nntp@snipabacken.se> - 2011-10-21 07:58 +0000
        Re: Strange remove_if behaviour Stephen Howe <stephen.howe@kantarmedia.com> - 2011-10-20 14:42 -0700
        Re: Strange remove_if behaviour Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2011-10-21 10:20 +0200
          Re: Strange remove_if behaviour "hugo_ribeira@hotmail.com" <hugo_ribeira@hotmail.com> - 2011-10-22 15:41 -0700

#11000 — Strange remove_if behaviour

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?

[toc] | [next] | [standalone]

#11001

"hugo_ribeira@hotmail.com" <hugo_ribeira@hotmail.com> writes:

> 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.

[toc] | [prev] | [next] | [standalone]

#11005

On 20 Out, 11:14, Alain Ketterlin <al...@dpt-info.u-strasbg.fr> wrote:
> "hugo_ribe...@hotmail.com" <hugo_ribe...@hotmail.com> writes:
> > 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.

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?

[toc] | [prev] | [next] | [standalone]

#11007

On 10/20/2011 8:17 AM, hugo_ribeira@hotmail.com wrote:
> On 20 Out, 11:14, Alain Ketterlin<al...@dpt-info.u-strasbg.fr>  wrote:
>> "hugo_ribe...@hotmail.com"<hugo_ribe...@hotmail.com>  writes:
>>> 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.
>
> 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
-- 
I do not respond to top-posted replies, please don't ask

[toc] | [prev] | [next] | [standalone]

#11021

On 10/20/2011 02:17 PM, hugo_ribeira@hotmail.com wrote:
> On 20 Out, 11:14, Alain Ketterlin<al...@dpt-info.u-strasbg.fr>  wrote:
>> "hugo_ribe...@hotmail.com"<hugo_ribe...@hotmail.com>  writes:
>>> 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.
>
> 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

[toc] | [prev] | [next] | [standalone]

#11022

hugo_ribeira@hotmail.com wrote:
> On 20 Out, 11:14, Alain Ketterlin <al...@dpt-info.u-strasbg.fr> wrote:
> 
>>"hugo_ribe...@hotmail.com" <hugo_ribe...@hotmail.com> writes:
>>
>>>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.
> 
> 
> 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.

[toc] | [prev] | [next] | [standalone]

#11034

On Thu, 2011-10-20, Ben Cottrell wrote:
...
> 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

-- 
  // Jorgen Grahn <grahn@  Oo  o.   .     .
\X/     snipabacken.se>   O  o   .

[toc] | [prev] | [next] | [standalone]

#11031

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

[toc] | [prev] | [next] | [standalone]

#11035

"hugo_ribeira@hotmail.com" <hugo_ribeira@hotmail.com> writes:

> On 20 Out, 11:14, Alain Ketterlin <al...@dpt-info.u-strasbg.fr> wrote:

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

> 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.

[toc] | [prev] | [next] | [standalone]

#11042

Thank's guys,

Problem solved and understood.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c++

csiph-web