5

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

6 Answers 6

7

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

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.

6
  • Finally, someone paid enough attention to answer the question the OP is really asking! I'd upvote this five times if it were allowed.
    – Head Geek
    Commented Mar 3, 2009 at 3:06
  • @dirkgently, I don't see where the OP asked for an in-place splice. He wants to remove certain elements from one container and put them into another. This algorithm works fine for that, as far as I know from the admittedly limited testing I did. Using this algorithm in-place makes no sense. Commented Mar 3, 2009 at 18:07
  • @Fred: Splice is splitting up a list. I generalized. That's what the OP wants: A list where each element satifies a given predicate and his problem is "how far back from the end of the source container to erase" i.e. removal.
    – dirkgently
    Commented Mar 3, 2009 at 18:55
  • @dirkgently: Yes, the OP is doing a splice. But in-place is not specified. What the OP is asking for is to avoid two passes. "I'm sure that two linear calls is not the way to do this." OP already has a working two-pass solution. Commented Mar 3, 2009 at 19:06
  • @Fred: you cannot simply split up a container except lists. What you are doing is no different than remove_copy_if at an abstract level. The only implementation level change is the end() iterator.
    – dirkgently
    Commented Mar 3, 2009 at 20:10
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.

2
  • -1 This won't work. The elements beginning at the iterator returned by remove_if are not the same as the removed elements. Some of them may be copies of elements that are not removed. Commented Mar 2, 2009 at 21:43
  • Removing downvote due to edit. You're right that the predicate does not do what the comments seem to suggest. Commented Mar 3, 2009 at 21:28
1
  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.

1

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;
}
1
  • +1. I think this is the best answer yet -- better than mine. Commented Mar 3, 2009 at 21:30
0

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.