Removing elements from std::vector.

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" <jasonheyes@optusnet.com.au> wrote in message
news:41982632$0$27451
[color=blue]
> 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[/color]
from[color=blue]
> std::vector based on predicate:[/color]

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.

On Mon, 15 Nov 2004 14:44:16 +1100 in comp.lang.c++, "Jason Heyes" <jasonheyes@optusnet.com.au> wrote,[color=blue]
>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:[/color]

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

"Siemel Naran" <SiemelNaran@REMOVE.att.net> wrote in message
news:CWYld.907619$Gx4.526580@bgtnsc04-news.ops.worldnet.att.net...[color=blue]
> "Jason Heyes" <jasonheyes@optusnet.com.au> wrote in message
> news:41982632$0$27451
>[color=green]
>> 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[/color]
> from[color=green]
>> std::vector based on predicate:[/color]
>
> 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.
>[/color]

Your code copies the wrong elements into r. Better luck next time.

"David Harmon" <source@netcom.com> wrote in message
news:42386224.769913031@news.west.earthlink.net...[color=blue]
> On Mon, 15 Nov 2004 14:44:16 +1100 in comp.lang.c++, "Jason Heyes"
> <jasonheyes@optusnet.com.au> wrote,[color=green]
>>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:[/color]
>
> 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());
>[/color]

Your code copies the wrong elements into r. Care to try again?

In article <41982632$0$27451$afc38c87@news.optusnet.com.au> ,
"Jason Heyes" <jasonheyes@optusnet.com.au> wrote:
[color=blue]
> 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.[/color]

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" <hinnant@metrowerks.com> wrote in message
news:hinnant-556089.09190115112004@syrcnyrdrs-02-ge0.nyroc.rr.com...[color=blue]
> 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[/color]

Thanks heaps for this. It solves other problems I've been having.