STL removing elements that match a predicate

Question

Hi Folks, 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.

Thanks for any help, Martin.

#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

If you are going to downvote a technically correct answer, fine. But as other posters have noted (including the accepted answer's author) keeping in line with my analysis -- I'll keep my answer.

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

Answer 2

There will be copy_if and remove_if.

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

It is better to understand code where Predicate class answering "true" if something is present. In that case you won't need not1 two times.

Because std::find looks for substring not obligatory from the begin you need to change "beginning with 1" to "with 1" to avoid future misunderstanding of your code.

Answer 3

remove*() don't relally remove elements, it simply reorders them and put them at the end of the collection and return a new_end iterator in the same container indicating where the new end is. You then need to call erase to remove the range from the vector.

source.erase(source.remove(source.begin(), source.end(), element), source.end());

remove_if() does the same but with a predicate.

source.erase(source.remove_if(source.begin(), source.end(), predicate), source.end());

remove_copy_if() will only copy the elements NOT matching the predicate, leaving the source vector intact and providing you with the end iterator on the target vector, so that you can shrink it.

// target must be of a size ready to accomodate the copy
target.erase(source.remove_copy_if(source.begin(), source.end(), target.begin(), predicate), target.end());

Answer 4

1. The whole reason why the remove_* algorithms do not erase elements is because it is impossible to "erase" an element by the iterator alone. You can't get container by iterator This point is explained in more details in the book "Effective STL"

2. Use 'copy_if', followed by 'remove_if'. remove_copy_if does not modify the source.

3. On lists you can do better - reordering followed by splice.

Answer 5

I see your point, that you'd like to avoid doing two passes over your source container. Unfortunately, I don't believe there's a standard algorithm that will do this. It would be possible to create your own algorithm that would copy elements to a new container and remove from the source container (in the same sense as remove_if; you'd have to do an erase afterward) in one pass. Your container size and performance requirements would dictate whether the effort of creating such an algorithm would be better than making two passes.

Edit: I came up with a quick implementation:

template<typename F_ITER, typename O_ITER, typename FTOR>
F_ITER move_if(F_ITER begin, F_ITER end, O_ITER dest, FTOR match)
{
  F_ITER result = begin;
  for(; begin != end; ++begin)
  {
    if (match(*begin))
    {
      *dest++ = *begin;
    }
    else
    {
      *result++ = *begin;
    }
  }

  return result;
}

Edit: Maybe there is confusion in what is meant by a "pass". In the OP's solution, there is a call to remove_copy_if() and a call to remove_if(). Each of these will traverse the entirety of the original container. Then there is a call to erase(). This will traverse any elements that were removed from the original container.

If my algorithm is used to copy the removed elements to a new container (using begin() the original container for the output iterator will not work, as dirkgently demonstrated), it will perform one pass, copying the removed elements to the new container by means of a back_inserter or some such mechanism. An erase will still be required, just as with remove_if(). One pass over the original container is eliminated, which I believe is what the OP was after.

Answer 6

If you don't mind having your strings in the same container, and having just an iterator to separate them, this code works.

#include "stdafx.h"

#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;

        Strings.push_back("213");
        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");

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

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

        cout << "Elements not matching with 1" << endl;
        copy(Strings.begin(), end1, ostream_iterator<string>(cout,"\n"));

        return 0;
}