Removing elements from std::vector.

Discussion in 'C++' started by Jason Heyes, Nov 15, 2004.

  1. Jason Heyes

    Jason Heyes Guest

    What is a good way of removing elements from std::vector so that the
    elements removed satisfy a predicate and end up stored in another
    std::vector. It seems as though the algorithm std::remove_if only achieves
    half the job. Here is how I would use std::remove_if to remove elements from
    std::vector based on predicate:

    v.erase(std::remove_if(v.begin(), v.end(), pred), v.end());

    After that line is executed I cannot get back the elements that were
    removed. So I try to add something before the line:

    using namespace std;
    remove_copy_if(v.begin(), v.end(), back_inserter(r), not1(pred));
    v.erase(remove_if(v.begin(), v.end(), pred), v.end());

    This code does the job but it requires twice as many calls to the predicate.
    Anyone care to show me an improvement on this? Thanks.
    Jason Heyes, Nov 15, 2004
    #1
    1. Advertising

  2. Jason Heyes

    Siemel Naran Guest

    "Jason Heyes" <> wrote in message
    news:41982632$0$27451

    > What is a good way of removing elements from std::vector so that the
    > elements removed satisfy a predicate and end up stored in another
    > std::vector. It seems as though the algorithm std::remove_if only achieves
    > half the job. Here is how I would use std::remove_if to remove elements

    from
    > std::vector based on predicate:


    How about:

    typedef std::vector<Whatever>::iterator Iter;
    Iter newend = std::remove_if(v.begin(), v.end(), pred);
    r.reserve(v.end()-newend);
    std::copy (newend, v.end(), back_inserter(r));
    v.erase(newend, v.end());

    Now you have N calls to pred.operator(), but 2M or more calls to the
    operator= or copy constructor (where M is the number of elements to remove):
    remove_if uses operator= to move the removed elements to the end of the
    vector, and std::copy invokes M calls to the copy constructor. If your
    class Whatever is small or a smart pointer class, then this should be OK.

    There might be a special remove_if function in STL that moves the removed
    elements to a new range, but I don't know that yet.
    Siemel Naran, Nov 15, 2004
    #2
    1. Advertising

  3. Jason Heyes

    David Harmon Guest

    On Mon, 15 Nov 2004 14:44:16 +1100 in comp.lang.c++, "Jason Heyes" <> wrote,
    >v.erase(std::remove_if(v.begin(), v.end(), pred), v.end());
    >
    >After that line is executed I cannot get back the elements that were
    >removed. So I try to add something before the line:


    Save the iterator. Use it twice.

    vector<value_type>::iterator it = remove_if(v.begin(), v.end(), pred);
    copy(it, v.end(), back_inserter(r));
    v.erase(it, v.end());
    David Harmon, Nov 15, 2004
    #3
  4. Jason Heyes

    Jason Heyes Guest

    "Siemel Naran" <> wrote in message
    news:CWYld.907619$...
    > "Jason Heyes" <> wrote in message
    > news:41982632$0$27451
    >
    >> What is a good way of removing elements from std::vector so that the
    >> elements removed satisfy a predicate and end up stored in another
    >> std::vector. It seems as though the algorithm std::remove_if only
    >> achieves
    >> half the job. Here is how I would use std::remove_if to remove elements

    > from
    >> std::vector based on predicate:

    >
    > How about:
    >
    > typedef std::vector<Whatever>::iterator Iter;
    > Iter newend = std::remove_if(v.begin(), v.end(), pred);
    > r.reserve(v.end()-newend);
    > std::copy (newend, v.end(), back_inserter(r));
    > v.erase(newend, v.end());
    >
    > Now you have N calls to pred.operator(), but 2M or more calls to the
    > operator= or copy constructor (where M is the number of elements to
    > remove):
    > remove_if uses operator= to move the removed elements to the end of the
    > vector, and std::copy invokes M calls to the copy constructor. If your
    > class Whatever is small or a smart pointer class, then this should be OK.
    >
    > There might be a special remove_if function in STL that moves the removed
    > elements to a new range, but I don't know that yet.
    >


    Your code copies the wrong elements into r. Better luck next time.
    Jason Heyes, Nov 15, 2004
    #4
  5. Jason Heyes

    Jason Heyes Guest

    "David Harmon" <> wrote in message
    news:...
    > On Mon, 15 Nov 2004 14:44:16 +1100 in comp.lang.c++, "Jason Heyes"
    > <> wrote,
    >>v.erase(std::remove_if(v.begin(), v.end(), pred), v.end());
    >>
    >>After that line is executed I cannot get back the elements that were
    >>removed. So I try to add something before the line:

    >
    > Save the iterator. Use it twice.
    >
    > vector<value_type>::iterator it = remove_if(v.begin(), v.end(), pred);
    > copy(it, v.end(), back_inserter(r));
    > v.erase(it, v.end());
    >


    Your code copies the wrong elements into r. Care to try again?
    Jason Heyes, Nov 15, 2004
    #5
  6. In article <41982632$0$27451$>,
    "Jason Heyes" <> wrote:

    > What is a good way of removing elements from std::vector so that the
    > elements removed satisfy a predicate and end up stored in another
    > std::vector. It seems as though the algorithm std::remove_if only achieves
    > half the job. Here is how I would use std::remove_if to remove elements from
    > std::vector based on predicate:
    >
    > v.erase(std::remove_if(v.begin(), v.end(), pred), v.end());
    >
    > After that line is executed I cannot get back the elements that were
    > removed. So I try to add something before the line:
    >
    > using namespace std;
    > remove_copy_if(v.begin(), v.end(), back_inserter(r), not1(pred));
    > v.erase(remove_if(v.begin(), v.end(), pred), v.end());
    >
    > This code does the job but it requires twice as many calls to the predicate.
    > Anyone care to show me an improvement on this? Thanks.


    Consider partition:

    i = partition(v.begin(), v.end(), pred);

    And then do whatever you want with your two sets: [v.begin(), i) and
    [i, v.end()). The first set is the one with pred true.

    -Howard
    Howard Hinnant, Nov 15, 2004
    #6
  7. Jason Heyes

    Jason Heyes Guest

    "Howard Hinnant" <> wrote in message
    news:...
    > Consider partition:
    >
    > i = partition(v.begin(), v.end(), pred);
    >
    > And then do whatever you want with your two sets: [v.begin(), i) and
    > [i, v.end()). The first set is the one with pred true.
    >
    > -Howard


    Thanks heaps for this. It solves other problems I've been having.
    Jason Heyes, Nov 16, 2004
    #7
    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. Tino
    Replies:
    1
    Views:
    8,885
    Jonathan Turkanis
    Feb 20, 2004
  2. Anonymous
    Replies:
    20
    Views:
    4,276
    Pete Becker
    Mar 30, 2005
  3. Jason Heyes
    Replies:
    8
    Views:
    711
    Andrew Koenig
    Jan 15, 2006
  4. Replies:
    8
    Views:
    1,896
    Csaba
    Feb 18, 2006
  5. Rune Allnor
    Replies:
    4
    Views:
    929
    Rune Allnor
    Dec 11, 2008
Loading...

Share This Page