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

c++, stl

Solution

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

Problem

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

Original source