Strange remove_if behaviour

Discussion in 'C++' started by hugo_ribeira@hotmail.com, Oct 20, 2011.

  1. Guest

    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?
     
    , Oct 20, 2011
    #1
    1. Advertising

  2. "" <> 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.
     
    Alain Ketterlin, Oct 20, 2011
    #2
    1. Advertising

  3. Guest

    On 20 Out, 11:14, Alain Ketterlin <-strasbg.fr> wrote:
    > "" <> 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?
     
    , Oct 20, 2011
    #3
  4. On 10/20/2011 8:17 AM, wrote:
    > On 20 Out, 11:14, Alain Ketterlin<-strasbg.fr> wrote:
    >> ""<> 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
     
    Victor Bazarov, Oct 20, 2011
    #4
  5. Edek Guest

    On 10/20/2011 02:17 PM, wrote:
    > On 20 Out, 11:14, Alain Ketterlin<-strasbg.fr> wrote:
    >> ""<> 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
     
    Edek, Oct 20, 2011
    #5
  6. Ben Cottrell Guest

    wrote:
    > On 20 Out, 11:14, Alain Ketterlin <-strasbg.fr> wrote:
    >
    >>"" <> 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.
     
    Ben Cottrell, Oct 20, 2011
    #6
  7. Stephen Howe Guest

    Stephen Howe, Oct 20, 2011
    #7
  8. Jorgen Grahn Guest

    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 .
     
    Jorgen Grahn, Oct 21, 2011
    #8
  9. "" <> writes:

    > On 20 Out, 11:14, Alain Ketterlin <-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.
     
    Alain Ketterlin, Oct 21, 2011
    #9
  10. Guest

    Thank's guys,

    Problem solved and understood.
     
    , Oct 22, 2011
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. CupOfWater

    std::remove_if errors!

    CupOfWater, Oct 22, 2003, in forum: C++
    Replies:
    4
    Views:
    1,544
    Jerry Coffin
    Oct 23, 2003
  2. Wang Tong

    Need help on remove_if

    Wang Tong, Dec 8, 2003, in forum: C++
    Replies:
    5
    Views:
    2,648
    Stewart Gordon
    Dec 9, 2003
  3. Paavo K

    STL remove_if function

    Paavo K, Feb 17, 2004, in forum: C++
    Replies:
    1
    Views:
    4,301
    David Harmon
    Feb 17, 2004
  4. marco_segurini

    remove_if and functions overloading

    marco_segurini, Apr 7, 2004, in forum: C++
    Replies:
    1
    Views:
    1,081
    tom_usenet
    Apr 7, 2004
  5. marco_segurini
    Replies:
    0
    Views:
    1,680
    marco_segurini
    May 28, 2004
Loading...

Share This Page