Ok, here we go:
vector<object*>::iterator removed_begin; // add all freed objects to free_objects remove_copy_if( objects.begin(), objects.end(), back_inserter(free_objects), not1(mem_fun(object::is_free))); // "remove" freed objects removed_begin = remove_if( objects.begin(), objects.end(), mem_fun(object::is_free)); // erase all "removed" objects objects.erase( removed_begin, objects.end());
remove_copy_if()'s signature:
template<class InputIterator, class OutputIterator, class Predicate> OutputIterator remove_copy_if( InputIterator first, InputIterator last, OutputIterator result, Predicate pred);
It copies all elements in the range [first, last) to a range starting at result, but skips elements for which pred(element) returns true.
The first two arguments are easy, just use objects.begin() and objects.end() to iterate over the entire sequence.
The result iterator is a bit harder, we can't use free_objects.end(), because remove_copy_if() only
copies elements, it doesn't
add new elements. Instead, we can use a back_insert_iterator. When an object is assigned to a back_insert_iterator, it appends that object to the back of a container.
Here's a simple example:
#include <iostream> #include <vector> #include <iterator> using namespace std; int main() { vector<int> v; back_insert_iterator<vector<int> > it(v); (*it) = 10; // v.push_back(10) (*it) = 20; // v.push_back(20) (*it) = 30; // v.push_back(30) for(int i=0; i<v.size(); ++i) cout << v << endl; }
back_inserter() is a function that returns a back_insert_iterator, it makes the syntax look a bit cleaner since template functions can automatically fill in the template parameters, you don't have to specify the types yourself.
A predicate is a function that returns true or false. For example:
bool is_free(object* obj) { return obj->is_free(); }
Instead of a function, it's also possible use a function
object:
struct is_free() { bool operator()(object* obj) { return obj->is_free(); } };
After you have instantiated a function object like this, you can use it just like you would use a normal function:
object o; is_free f; f(&o);
Little function objects that simply pass the call to a member function of operator()'s argument (like the one above) appear fairly often, so the standard library provides a function called mem_fun() that automatically generates such a function object (a mem_fun_t). mem_fun() takes the member function it should call as an argument.
In this case, we don't want to skip the arguments for which is_free() returns true, we want the exact opposite. not1() wraps a predicate and negates it.
Here's remove_if()'s signature:
template<class InputIterator, class Predicate> OutputIterator remove_if( InputIterator first, InputIterator last, Predicate pred);
This might sound a bit weird. remove_if() removes all elements in the range [first, last) for which pred returns true. However, since remove_if() doesn't know anything about the container on which it operates (only about the iterators), it can't
really remove the elements, instead it just rearranges the sequence and moves all "valid" elements to the front. It then returns an iterator to the end of the range of valid elements (== beginning of the invalid/removed elements).
To physically remove the elements from the container we erase the entire "invalid" range at once.
For more detailed info:
http://www.sgi.com/tech/stl/Vector.html
http://www.sgi.com/tech/stl/remove_copy_if.html
http://www.sgi.com/tech/stl/remove.html
http://www.sgi.com/tech/stl/back_insert_iterator.html
http://www.sgi.com/tech/stl/mem_fun_t.html
http://www.sgi.com/tech/stl/unary_negate.html
Hope that helped...
[edited by - kvh on April 29, 2002 1:28:57 PM]
