Question about STL erase function

Discussion in 'C++' started by Piotr, Jan 18, 2006.

  1. Piotr

    Piotr Guest

    In Effective STL item 9 "Choose carefully among erasing options", it
    has this example:

    bool badValue(int x); // returns whether x is 'bad'
    c.erase ( remove_if(c.begin(), c.end(), badValue), c.end()); // this
    is the best way to get rid of objects where badValue returns true when
    c is a vector, string, or dequeue

    c.remove_if(badValue); // this is the best way to get rid of objects
    where badValue returns true when c is a list

    My question is "For the first case, why we need to call c.erase() again
    and pass in the return value of remove_if()?" Doesn't the call to
    remove_if() remove the item from the container (in this case a vector)?
    why we need to call erase() again?

    Thank you.
    Piotr, Jan 18, 2006
    #1
    1. Advertising

  2. Piotr wrote:
    > In Effective STL item 9 "Choose carefully among erasing options", it
    > has this example:
    >
    > bool badValue(int x); // returns whether x is 'bad'
    > c.erase ( remove_if(c.begin(), c.end(), badValue), c.end()); // this
    > is the best way to get rid of objects where badValue returns true when
    > c is a vector, string, or dequeue
    >
    > c.remove_if(badValue); // this is the best way to get rid of objects
    > where badValue returns true when c is a list
    >
    > My question is "For the first case, why we need to call c.erase() again
    > and pass in the return value of remove_if()?" Doesn't the call to
    > remove_if() remove the item from the container (in this case a vector)?
    > why we need to call erase() again?


    I believe the book you are reading has the answer to your question.
    std::remove_if does not change the size of the container - it couldn't,
    since you are only passing it a range specified by two iterators.
    Instead, it returns a new iterator indicating the new end of the range.

    See here for an explanation:

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

    Best regards,

    Tom
    Thomas Tutone, Jan 18, 2006
    #2
    1. Advertising

  3. Piotr

    Heinz Ozwirk Guest

    "Piotr" <> schrieb im Newsbeitrag
    news:...
    > In Effective STL item 9 "Choose carefully among erasing options", it
    > has this example:
    >
    > bool badValue(int x); // returns whether x is 'bad'
    > c.erase ( remove_if(c.begin(), c.end(), badValue), c.end()); // this
    > is the best way to get rid of objects where badValue returns true when
    > c is a vector, string, or dequeue
    >
    > c.remove_if(badValue); // this is the best way to get rid of objects
    > where badValue returns true when c is a list
    >
    > My question is "For the first case, why we need to call c.erase() again
    > and pass in the return value of remove_if()?" Doesn't the call to
    > remove_if() remove the item from the container (in this case a vector)?
    > why we need to call erase() again?


    remove_if(first, last, pred) removes unwanted elements from the sequence
    [first, last) and it copies the remaining elements to the places of the
    removed elements. But it does not actually discard unused space from the end
    of the sequence. For each element removed, you get a copy of another
    element. Basically remove_if does something like

    iterator free = first;
    while (first != last)
    {
    if (badValue(*first))
    ++first;
    else
    *free++ = *first++;
    }
    return free;

    HTH
    Heinz
    Heinz Ozwirk, Jan 18, 2006
    #3
  4. Piotr

    Pete Becker Guest

    Piotr wrote:
    >
    > My question is "For the first case, why we need to call c.erase() again
    > and pass in the return value of remove_if()?" Doesn't the call to
    > remove_if() remove the item from the container (in this case a vector)?
    > why we need to call erase() again?
    >


    Algorithms work on sequences designated by pairs of iterators. They do
    not work on containers. remove_if "removes" elements from the sequence
    that's passed to it by copying replacement elements on top of rejected
    ones, and giving back a new end iterator that designates the end of the
    new sequence. Typically that sequence is shorter than the original one,
    and any elements pointed to by the end iterator and beyond are
    irrelevant to the algorithm.

    The algorithm doesn't know anything about the source of the sequence,
    and cannot modify a container that might have been the source of the
    sequence that was passed to it. But because it rearranges elements, you
    can use the end iterator that it returns to tell you where the remaining
    elements are in your container: they're the ones from the end iterator
    returned by the algorithm to the actual end of the container. So you
    erase 'em if that's appropriate.

    If I haven't made too many typos, try this:

    int data[] = { 1, 2, 3, 4, 5, 6, 7 }

    struct is_odd
    {
    bool operator()(int val)
    {
    return val & 1;
    }
    };

    int main()
    {
    int *begin = data;
    int *end = data + sizeof(data) / sizeof(*data);

    std::cout << "Original sequence: ";
    std::copy(begin, end, std::eek:stream_iterator<int>(std::cout, " ");
    std::cout << '\n';

    int *new_end = std::remove_if(begin, end, is_odd());
    // nothing to erase, 'cause the container's size is fixed

    std::cout << "Modified sequence: ";
    std::copy(begin, new_end, std::eek:stream_iterator<int>(std::cout, " ");
    std::cout << '\n';

    std::cout << "Original container: ";
    std::copy(begin, end, std::eek:stream_iterator<int>(std::cout, " ");
    std::cout << '\n';

    return 0;
    }

    Now modify it to use a vector<int> instead of an array.

    --

    Pete Becker
    Dinkumware, Ltd. (http://www.dinkumware.com)
    Pete Becker, Jan 18, 2006
    #4
  5. Piotr

    Piotr Guest

    Thanks.
    But why I don't need to do that for list?
    Piotr, Jan 19, 2006
    #5
  6. Piotr wrote:
    > Thanks.
    > But why I don't need to do that for list?


    Well, to quote your example (assume vec is a std::vector and list is a
    std::list):

    bool badValue(int x);

    vec.erase(std::remove_if(vec.begin(),
    vec.end(),
    badValue), vec.end());

    list.remove_if(badValue);

    In the vector example, you are using an algorithm, std::remove_if. In
    the list example, you are using a std::list member function,
    std::list::remove_if. The algorithm does not erase the removed
    elements. The list member function does erase the removed elements.
    In other words, the algorithm and the member function are not the same.

    If you can, get yourself a copy of Josuttis's The C++ Standard Library.
    It is an excellent resource, and will answer all of your questions
    like this.

    Best regards,

    Tom
    Thomas Tutone, Jan 19, 2006
    #6
  7. Piotr

    Ian Collins Guest

    Piotr wrote:
    > Thanks.
    > But why I don't need to do that for list?
    >

    Do what? Please quote.

    --
    Ian Collins.
    Ian Collins, Jan 19, 2006
    #7
  8. Piotr

    Pete Becker Guest

    Piotr wrote:
    > Thanks.
    > But why I don't need to do that for list?
    >


    Because list::remove_if is a member function of the template. Unlike the
    standalone algorithm, it knows that it's working on a container.

    --

    Pete Becker
    Dinkumware, Ltd. (http://www.dinkumware.com)
    Pete Becker, Jan 19, 2006
    #8
  9. Piotr

    Piotr Guest

    After the return of remove_if() to remove elements from the container
    which matches the condition, how can I get the address of all the
    removed elements and call their destructor?

    Thank you.
    Piotr, Jan 19, 2006
    #9
  10. Piotr wrote:
    > After the return of remove_if() to remove elements from the container
    > which matches the condition, how can I get the address of all the
    > removed elements and call their destructor?


    Which remove_if() are you referring to? If you are referring to the
    algorithm std::remove_if, then calling erase() as you showed in your
    original example will results in the removed elements' destructors
    being called automatically.

    If you are referring to the std::list member function remove_if, that
    function will result in the removed elements' destructors being called
    automatically.

    In neither case you should you explicitly call the elements'
    destructors yourself.

    Best regards,

    Tom
    Thomas Tutone, Jan 19, 2006
    #10
  11. In message <>,
    Piotr <> writes
    >After the return of remove_if() to remove elements from the container
    >which matches the condition, how can I get the address of all the
    >removed elements and call their destructor?
    >

    No need. container.erase(remove_if(/*...*/), container.end()) will do
    it for you.

    (Note that the sequence bounded by remove_if() and container.end() is
    stuff you no longer need, but not necessarily "the removed elements",
    since some of the unwanted elements may have had wanted ones copied into
    them.)

    --
    Richard Herring
    Richard Herring, Jan 19, 2006
    #11
    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. John Harrison

    Re: STL insert/erase behaviour

    John Harrison, Aug 13, 2003, in forum: C++
    Replies:
    0
    Views:
    629
    John Harrison
    Aug 13, 2003
  2. Nan Li
    Replies:
    2
    Views:
    1,058
    Andrew Koenig
    Nov 8, 2005
  3. erase vs. erase

    , Mar 25, 2006, in forum: C++
    Replies:
    7
    Views:
    354
    Pete Becker
    Mar 30, 2006
  4. Replies:
    8
    Views:
    628
  5. Boltar
    Replies:
    6
    Views:
    2,232
    Jerry Coffin
    Jan 5, 2008
Loading...

Share This Page