why doesn't std::remove_copy_if() actually remove?

Question

Could this be the worst named function in the STL? (rhetorical question)

std::remove_copy_if() doesn't actually appear to do any removing. As best I can tell, it behaves more like copy_if_not.

The negation is a bit confusing, but can be worked around with std::not1(), however I might be misunderstanding something as I cannot fathom what this function has to do with removing - am I missing something?

If not, is there an STL algorithm for conditionally removing (moving?) elements from a container & putting them in another container?

Editing to add an example so readers are less confused.

The following program appears to leave the input range (V1) untouched:

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

using std::cout;
using std::endl;

int main (void)
{
    std::vector<int> V1, V2;
    V1.push_back(-2);
    V1.push_back(0);
    V1.push_back(-1);
    V1.push_back(0);
    V1.push_back(1);
    V1.push_back(2);

    std::copy(V1.begin(), V1.end(), std::ostream_iterator<int>(cout, " "));
    cout << endl;

    std::remove_copy_if(
        V1.begin(),
        V1.end(),
        std::back_inserter(V2),
        std::bind2nd(std::less<int>(), 0));

    std::copy(V2.begin(), V2.end(), std::ostream_iterator<int>(cout, " "));
    cout << endl;
    std::copy(V1.begin(), V1.end(), std::ostream_iterator<int>(cout, " "));
    cout << endl;
}

It outputs:

-2 0 -1 0 1 2 
0 0 1 2 
-2 0 -1 0 1 2 

I was expecting so see something like:

-2 0 -1 0 1 2 
0 0 1 2 
0 0 1 2 ? ? ?

Where ? could be any value. But I was surprised to see that the input range was untouched, & that the return value is not able to be used with (in this case) std::vector::erase(). (The return value is an output iterator.)

Answer 1

Could this be the worst named function in the STL?

A bit of background information: in the standard library (or the original STL), there are three concepts, the containers, the iterators into those containers and algorithms that are applied to the iterators. Iterators serve as a cursor and accessor into the elements of a range but do not have a reference to the container (as mentioned before, there might not even be an underlying container).

This separation has the nice feature that you can apply algorithms to ranges of elements that do not belong to a container (consider iterator adaptors like std::istream_iterator or std::ostream_iterator) or that, belonging to a container do not consider all elements (std::sort( v.begin(), v.begin()+v.size()/2 ) to short the first half of the container).

The negative side is that, because the algorithm (and the iterator) don't really know of the container, they cannot really modify it, they can only modify the stored elements (which is what they can access). Mutating algorithms, like std::remove or std::remove_if work on this premise: they overwrite elements that don't match the condition effectively removing them from the container, but they do not modify the container, only the contained values, that is up to the caller in a second step of the erase-remove idiom:

v.erase( std::remove_if( v.begin(), v.end(), pred ),
         v.end() );

Further more, for mutating algorithms (those that perform changes), like std::remove there is a non-mutating version named by adding copy to the name: std::remove_copy_if. None of the XXXcopyYYY algorithms are considered to change the input sequence (although they can if you use aliasing iterators).

While this is really no excuse for the naming of std::remove_copy_if, I hope that it helps understanding what an algorithm does given its name: remove_if will modify contents of the range and yield a range for which all elements that match the predicate have been removed (the returned range is that formed by the first argument to the algorithm to the returned iterator). std::remove_copy_if does the same, but rather than modifying the underlying sequence, it creates a copy of the sequence in which those elements matching the predicate have been removed. That is, all *copy* algorithms are equivalent to copy and then apply the original algorithm (note that the equivalence is logical, std::remove_copy_if only requires an OutputIterator, which means that it could not possibly copy and then walk the copied range applying std::remove_if.

The same line of reasoning can be applied to other mutating algorithms: reverse reverses the values (remember, iterators don't access the container) in the range, reverse_copy copies the elements in the range to separate range in the reverse order.

If not, is there an STL algorithm for conditionally removing (moving?) elements from a container & putting them in another container?

There is no such algorithm in the STL, but it could be easily implementable:

template <typename FIterator, typename OIterator, typename Pred>
FIterator splice_if( FIterator first, FIterator last, OIterator out, Pred p )
{
   FIterator result = first;
   for ( ; first != last; ++first ) {
      if ( p( *first ) ) {
         *result++ = *first;
      } else {
         *out++ = *first;
      }
   }
   return result;
}

Answer 2

is there an STL algorithm for conditionally removing (moving?) elements from a container & putting them in another container?

The closest thing I can think of is std::stable_partition:

std::vector<int> v;
// ...
auto it = std::stable_partition(v.begin(), v.end(), pick_the_good_elements);
std::vector<int> w(std::make_move_iter(it), std::make_move_iter(v.end()));
v.erase(it, v.end());

Now v will contain the "good" elements, and w will contain the "bad" elements.

Answer 3

You are right, that is what it does... std::remove_copy_if copies the vector, removing anything that matches the pred.

std::remove_if ... removes on condition (or rather, shuffles things around).

Answer 4

If not, is there an STL algorithm for conditionally removing (moving?) elements from a container & putting them in another container?

Not really. The idea is that the modifying algorithms are allowed to "move" (not in the C++ sense of the word) elements in a container around but cannot change the length of the container. So the remove algorithms could be called prepare_for_removal.

By the way, C++11 provides std::copy_if, which allows you to copy selected elements from one container to another without playing funny logic games with remove_copy_if.

Answer 5

I agree that remove is not the best name for this family of functions.

But as Luc said, there's a reason for it working the way it does, and the GoTW item that he mentions explains how it works. remove_if works exactly the same way as remove - which is what you would expect.

You might also want to read this Wikibooks article.