Removing elements from std::vector.

[Jason Heyes]

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::re move_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.

[Siemel Naran]

Re: Removing elements from std::vector.

"Jason Heyes" <jasonheyes@opt usnet.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<Wha tever>::iterato r 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.

[David Harmon]

Re: Removing elements from std::vector.

On Mon, 15 Nov 2004 14:44:16 +1100 in comp.lang.c++, "Jason Heyes" <jasonheyes@opt usnet.com.au> wrote,[color=blue]
>v.erase(std::r emove_if(v.begi n(), 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_ty pe>::iterator it = remove_if(v.beg in(), v.end(), pred);
copy(it, v.end(), back_inserter(r ));
v.erase(it, v.end());

[Jason Heyes]

Re: Removing elements from std::vector.

"Siemel Naran" <SiemelNaran@RE MOVE.att.net> wrote in message
news:CWYld.9076 19$Gx4.526580@b gtnsc04-news.ops.worldn et.att.net...[color=blue]
> "Jason Heyes" <jasonheyes@opt usnet.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<Wha tever>::iterato r 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.

[Jason Heyes]

Re: Removing elements from std::vector.

"David Harmon" <source@netcom. com> wrote in message
news:42386224.7 69913031@news.w est.earthlink.n et...[color=blue]
> On Mon, 15 Nov 2004 14:44:16 +1100 in comp.lang.c++, "Jason Heyes"
> <jasonheyes@opt usnet.com.au> wrote,[color=green]
>>v.erase(std:: remove_if(v.beg in(), 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_ty pe>::iterator it = remove_if(v.beg in(), 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?

[Howard Hinnant]

Re: Removing elements from std::vector.

In article <41982632$0$274 51$afc38c87@new s.optusnet.com. au>,
"Jason Heyes" <jasonheyes@opt usnet.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::re move_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.beg in(), 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

[Jason Heyes]

Re: Removing elements from std::vector.

"Howard Hinnant" <hinnant@metrow erks.com> wrote in message
news:hinnant-556089.09190115 112004@syrcnyrd rs-02-ge0.nyroc.rr.co m...[color=blue]
> Consider partition:
>
> i = partition(v.beg in(), 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.