Why there is no std::erase?

Question

While reading the STL I realized that there is no std::erase provided. I am not really sure why it is not there. A valid use case is following

std::vector<int> odd { 1, 3, 5, 3, 9, 11, 5, 17 };
std::sort(odd.begin(), odd.end());
std::erase(std::unique(odd.begin(), odd.end()), odd.end());

It is embedded in every container though. If performance is the reason, in a manner that if the objects are contiguous they could be deleted in one shot. But I guess that is doable with help template specialization.

Answer 1

How would it work? It only accepts a pair of iterators. Iterators don't have to keep a reference to their container (a vector's iterators can be mere aliases for pointers).

So how would the algorithm modify the container itself? It needs that access.

It must be a member function.

Answer 2

The glue between sequences and algorithms are iterators (thanks to @Pete Becker for pointing me to the right term here). They are boiled down to the minimal functionality necessary for powerful algorithms that can be applied to multiple sequence (container) types. An example is such a snippet:

std::vector<int> vec{1, 2, 3, 4};
std::list<int> lst;

std::copy(vec.cbegin(), vec.cend(), std::back_inserter(lst));
std::copy(lst.cbegin(), lst.cend(), std::ostream_iterator<int>(std::cout, " "));

Here, std::copy can be implemented independently of the specific sequence type it operates on, because it workes with iterators that are meant to do two things: traverse a sequence and provide access to its elements.

However, this ships with a limitation when elements shall be deleted from a container.

The need to do so while leveraging a (std-)algorithm is common enough to give rise to the erase remove idiom being a well-known pattern or range libraries that take advantage of whole containers being passed to algorithms:

#include <boost/range/algorithm_ext.hpp>

std::vector<int> vec{1, 2, 3, 4};

boost::remove_erase(vec, 3);

The last function invocation can actually delete the element with value 3 from the container, because no information has been hidden in that function call. In contrast, the family of *begin/*end (member) functions does exactly that: hiding information behind an abstraction.

Answer 3

Uniform container erasure was added to std/experimental int the Library Fundamentals 2 TS at the end of 2014. This was voted into the standard recently for C++-2a but even the draft from github doesn't show it yet. I know gcc, clang, and Visual Studio support experimental.

So instead of your usual container include one of these versions:

<experimental/deque>
<experimental/forward_list>
<experimental/list>
<experimental/map>
<experimental/set>
<experimental/string>
<experimental/unordered_map>
<experimental/unordered_set>
<experimental/vector>

These are the signatures from from a more recent paper:

  // <experimental/string>
  template <class charT, class traits, class A, class Predicate>
    void erase_if(basic_string<charT, traits, A>& c, Predicate pred);
  template <class charT, class traits, class A, class U>
    void erase(basic_string<charT, traits, A>& c, const U& value);

  // <experimental/deque>
  template <class T, class A, class Predicate>
    void erase_if(deque<T, A>& c, Predicate pred);
  template <class T, class A, class U>
    void erase(deque<T, A>& c, const U& value);

  // <experimental/vector>
  template <class T, class A, class Predicate>
    void erase_if(vector<T, A>& c, Predicate pred);
  template <class T, class A, class U>
    void erase(vector<T, A>& c, const U& value);

  // <experimental/forward_list>
  template <class T, class A, class Predicate>
    void erase_if(forward_list<T, A>& c, Predicate pred);
  template <class T, class A, class U>
    void erase(forward_list<T, A>& c, const U& value);

  // <experimental/list>
  template <class T, class A, class Predicate>
    void erase_if(list<T, A>& c, Predicate pred);
  template <class T, class A, class U>
    void erase(list<T, A>& c, const U& value);

  // <experimental/map>
  template <class K, class T, class C, class A, class Predicate>
    void erase_if(map<K, T, C, A>& c, Predicate pred);
  template <class K, class T, class C, class A, class Predicate>
    void erase_if(multimap<K, T, C, A>& c, Predicate pred);

  // <experimental/set>
  template <class K, class C, class A, class Predicate>
    void erase_if(set<K, C, A>& c, Predicate pred);
  template <class K, class C, class A, class Predicate>
    void erase_if(multiset<K, C, A>& c, Predicate pred);

  // <experimental/unordered_map>
  template <class K, class T, class H, class P, class A, class Predicate>
    void erase_if(unordered_map<K, T, H, P, A>& c, Predicate pred);
  template <class K, class T, class H, class P, class A, class Predicate>
    void erase_if(unordered_multimap<K, T, H, P, A>& c, Predicate pred);

  // <experimental/unordered_set>
  template <class K, class H, class P, class A, class Predicate>
    void erase_if(unordered_set<K, H, P, A>& c, Predicate pred);
  template <class K, class H, class P, class A, class Predicate>
    void erase_if(unordered_multiset<K, H, P, A>& c, Predicate pred);