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]

"Jason Heyes" <ja********@opt usnet.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<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]

On Mon, 15 Nov 2004 14:44:16 +1100 in comp.lang.c++, "Jason Heyes" <ja********@opt usnet.com.au> wrote,

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:

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]

"Siemel Naran" <Si*********@RE MOVE.att.net> wrote in message
news:CW******** *************@b gtnsc04-news.ops.worldn et.att.net...

"Jason Heyes" <ja********@opt usnet.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<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.

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.w est.earthlink.n et...

On Mon, 15 Nov 2004 14:44:16 +1100 in comp.lang.c++, "Jason Heyes"
<ja********@opt usnet.com.au> wrote,

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:

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

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

[Howard Hinnant]

In article <41************ ***********@new s.optusnet.com. au>,
"Jason Heyes" <ja********@opt usnet.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::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.

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]

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

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

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