Removing elements from std::vector.

J

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

Siemel Naran

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

David Harmon

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

Jason Heyes

Siemel Naran said:
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.
 
J

Jason Heyes

David Harmon said:
On Mon, 15 Nov 2004 14:44:16 +1100 in comp.lang.c++, "Jason Heyes"


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?
 
H

Howard Hinnant

Jason Heyes said:
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
 
J

Jason Heyes

Howard Hinnant said:
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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top