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

[Siemel Naran]

"Jason Heyes" <ja********@optusnet.com.au> 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.

[David Harmon]

On Mon, 15 Nov 2004 14:44:16 +1100 in comp.lang.c++, "Jason Heyes" <ja********@optusnet.com.au> 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());

[Jason Heyes]

"Siemel Naran" <Si*********@REMOVE.att.net> wrote in message
news:CW*********************@bgtnsc04-news.ops.worldnet.att.net...

"Jason Heyes" <ja********@optusnet.com.au> 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]

"David Harmon" <so****@netcom.com> wrote in message
news:42****************@news.west.earthlink.net...

On Mon, 15 Nov 2004 14:44:16 +1100 in comp.lang.c++, "Jason Heyes"
<ja********@optusnet.com.au> 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?

[Howard Hinnant]

In article <41***********************@news.optusnet.com.au> ,
"Jason Heyes" <ja********@optusnet.com.au> 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

[Jason Heyes]

"Howard Hinnant" <hi*****@metrowerks.com> wrote in message
news:hi***************************@syrcnyrdrs-02-ge0.nyroc.rr.com...

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.