Now to remove elements that match a predicate?

Question

I have a source container of strings I want to remove any strings from the source container that match a predicate and add them into the destination container.

remove_copy_if and other algorithms can only reorder the elements in the container, and therefore have to be followed up by the erase member function. My book (Josuttis) says that remove_copy_if returns an iterator after the last position in the destination container. Therefore if I only have an iterator into the destination container, how can I call erase on the source container? I have tried using the size of the destination to determine how far back from the end of the source container to erase from, but had no luck. I have only come up with the following code, but it makes two calls (remove_if and remove_copy_if).

Can someone let me know the correct way to do this? I'm sure that two linear calls is not the way to do this.

#include <iostream>
#include <iterator>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>

using namespace std;  

class CPred : public unary_function<string, bool>
{
public:
        CPred(const string& arString)
                :mString(arString)
        {
        }

        bool operator()(const string& arString) const
        {
                return (arString.find(mString) == std::string::npos);
        }
private:
        string mString;
};

int main()
{
        vector<string> Strings;
        vector<string> Container;

        Strings.push_back("123");
        Strings.push_back("145");
        Strings.push_back("ABC");
        Strings.push_back("167");
        Strings.push_back("DEF");

        cout << "Original list" << endl;
        copy(Strings.begin(), Strings.end(),ostream_iterator<string>(cout,"\n"));

        CPred Pred("1");

        remove_copy_if(Strings.begin(), Strings.end(),
                       back_inserter(Container),
                       Pred);

        Strings.erase(remove_if(Strings.begin(), Strings.end(),
                      not1(Pred)), Strings.end());

        cout << "Elements beginning with 1 removed" << endl;
        copy(Strings.begin(), Strings.end(),ostream_iterator<string>(cout,"\n"));

        cout << "Elements beginning with 1" << endl;
        copy(Container.begin(), Container.end(),ostream_iterator<string>(cout,"\n"));

        return 0;
}

Answer 1

With all due respect to Fred's hard work, let me add this: the move_if is no different than remove_copy_if at an abstract level. The only implementation level change is the end() iterator. You are still not getting any erase(). The accepted answer does not erase() the matched elements -- part of the OP's problem statement.

As for the OP's question: what you want is an in-place splice. This is possible for lists. However, with vectors this will not work. Read about when and how and why iterators are invalidated. You will have to take a two pass algorithm.

remove_copy_if and other algorithms can only reorder the elements in the container,

From SGI's documentation on remove_copy_if:

This operation is stable, meaning that the relative order of the elements that are copied is the same as in the range [first, last).

So no relative reordering takes place. Moreover, this is a copy, which means the elements from Source vector in your case, is being copied to the Container vector.

how can I call erase on the source container?

You need to use a different algorithm, called remove_if:

remove_if removes from the range [first, last) every element x such that pred(x) is true. That is, remove_if returns an iterator new_last such that the range [first, new_last) contains no elements for which pred is true. The iterators in the range [new_last, last) are all still dereferenceable, but the elements that they point to are unspecified. Remove_if is stable, meaning that the relative order of elements that are not removed is unchanged.

So, just change that remove_copy_if call to:

vector<string>::iterator new_last = remove_if(Strings.begin(), 
                                              Strings.end(), 
                                              Pred);

and you're all set. Just keep in mind, your Strings vector's range is no longer that defined by the iterators [first(), end()) but rather by [first(), new_last).

You can, if you want to, remove the remaining [new_last, end()) by the following:

Strings.erase(new_last, Strings.end());

Now, your vector has been shortened and your end() and new_last are the same (one past the last element), so you can use as always:

copy(Strings.begin(), Strings.end(), ostream_iterator(cout, "\"));

to get a print of the strings on your console (stdout).