Is there a reason to use `remove` outside of the erase-remove idiom?

Question

As far as the algorithm is concerned, removing a set of element from a contiguous array can be done effectively in two parts.

1. Move all the elements not to be deleted to the front of the array.
2. Mark the array smaller.

This can be done in C++ with the erase-remove idiom.

vector<T> v; // v = {0,1,2,3,0,0,7};
vector<T>::iterator it = remove(v.begin(),v.end(),e);
// move all elements not to be deleted to the front
// Yes, remove is not the brightest name for that.
// Especially as list::remove really remove elements from the list.
// now v = {1,2,3,7,?,?,?} results marked in question marks
// are implementation dependent.
v.erase(it,v.end());
// get rid of the elements marked as question marks.
// v = {1,2,3,7}

Now, the content of the elements in the question mark is unknown. The only thing we can do with them is get rid of them (by overwriting them, or by removing them).

Is there a real world situation where you need to use remove without erase? The only situation I could think of is

copy(src.begin(),src.end(),remove(v.begin(),v.end(),e),v.end());

replacing all As with Bs, and requiring that all those new Bs will be contiguous. Doesn't make too much sense.

edit: Does it make sense to anything other than contigious memory container (deque and vector actually)?

If indeed I'm correct, why was it implemented as a standalone algorithm, instead of vector::remove_if, dequeue::remove_if etc.

Answer 1

Your question goes the wrong way round. Rather, one would ask "why should I implement this identical algorithm repetitively for each container, instead of making it a single, free function"?

The key idea behind separating containers, iterators and algorithms is that you don't have a complexity explosion as you write more algorithms and more containers. If you want to write a new container that has contiguous storage, you can use remove on it right out of the box (provided you supply forward or random-access iterators), without duplicating any code.

The only reason that certain containers implement their own, member versions of algorithms is because either they can do it better than the generic version (e.g. std::set::find vs. std::find; or list::remove), or because they can do what the generic version cannot do (e.g. std::list::sort vs. std::sort). But if you can, you should use the free version for maximal generality and genericity.

Answer 2

First of all: actually implementing remove_if as member methods would have meant duplicating the code again and again. I always considered that the mistake was in list (why is there a remove: MarkB answered this, in C++03 it's more efficient, and in C++11 it's slightly more efficient)

This is the design goal of the STL: separate data structures and algorithms so that if you have N structures and M algorithms, you do not have N*M implementations of the algorithms, but only N+M which is definitely more manageable.

Notably, the specification of remove that the elements "left out" have unspecified value allows the new C++11 move operations to be applied for efficient removal.

Now, I'll admit that most of the times, it is used as part of the remove-erase idiom. No one prevents you from creating your own:

 template <typename C>
 void erase(C& container, typename C::const_reference r) {
   container.erase(std::remove(container.begin(), container.end(), r), container.end());
 }

Answer 3

Yes. A simple counter-example:

void bar {
  // Get vector of T's from foo()
  vector<T> v = foo();
  // Print only non-zero elements.
  vector<T>::iterator it = remove(v.begin(),v.end(), T(0));
  // I could call erase here, but why bother?
  std::copy(v.begin(), it, std::ostream_iterator<T>(std::cout));
}

If I'm going to use only the selected part of the vector, and have no other uses for the vector, I don't need to erase the vector. All elements will be destructed anyway when the vector goes out of scope.

Answer 4

If, for some reason, you don't want to re-size your container, but just remove some elements and later set some other values to replace the removed space, then you could just use remove.

As I understand, the value of removed elements are unspecified after removal, so you can't use their data. They are kind of removed, but the space isn't freed.

Answer 5

Yes. first of all remove() is container independent. You can use it on 2 iterators of any container and should not do things like:

if(<iterator is vector iterator>)
{
   vector::remove_if(...);
}
else(<iterator is dequeue iterator>)
{
   dequeue::remove_if(...);
}
else(<iterator is list iterator>)
{
   list::remove_if(...);
}
// etc

Yes there is reason to not perform erase(). For vector it's making it smaller and therefore performing memory reallocation. What's not always desired because that will cause a lot of copy constructors for other elements of vector.