Document number: N4009
Date: 2014-05-22
Project: Programming Language C++, Library Evolution Working Group
Reply-to: Stephan T. Lavavej <stl@microsoft.com>


Uniform Container Erasure


I. Introduction

This is a proposal to add erase_if(container, pred), making it
easier to eliminate unwanted elements correctly and efficiently.


II. The Problem

It's surprisingly difficult to eliminate unwanted elements from a container,
given a predicate that distinguishes "bad" elements from "good" elements.

One of the STL's major strengths is that all of its containers have similar
interfaces - they have many functions in common and they follow the same
conventions.  When container interfaces vary, fundamental differences between
their data structures are responsible.  Even those differences can often be
ignored, thanks to the STL's container-iterator-algorithm design.

At first glance, it may appear that the containers have a uniform interface
for erasure, which is true for single-element and range erasure.  However,
for the common task of erasing elements that are recognized by a given
predicate, the containers have a highly non-uniform interface, filled with
traps and pitfalls for the unwary.

Trap #1: Repeated single-element erasure is terrible for the vector family.
When novices are faced with this task, they usually attempt to call erase()
in a loop.  In addition to being easy to get wrong, this triggers quadratic
complexity for vectors, deques, and basic_strings.  The correct response
is to use the erase-remove idiom, which is non-obvious and must be taught
instead of discovered (it's called an "idiom" for a reason).

Trap #2: The erase-remove idiom can suffer from silent typos.  Observe:

v.erase(remove_if(v.begin(), v.end(), pred), v.end()); // OK
v.erase(remove_if(v.begin(), v.end(), pred)); // GOTCHA

With this verbose idiom, forgetting to repeat v.end() produces code that will
silently compile and misbehave at runtime by calling the single-element
overload of erase() that takes one iterator.

Trap #3: The erase-remove idiom isn't ideal for the list family.  While the
remove_if() algorithm takes ForwardIterators and compiles for lists and
forward_lists, it requires MoveAssignable elements (25.3.8 [alg.remove]).
There's actually a list::remove_if() member function that behaves differently
(23.3.5.5 [list.ops]/15-18, and similarly for forward_list).  This member
function is confusingly named because it changes the list's size (unlike the
non-member algorithm).  Notably, the member function works with
non-MoveAssignable elements, preserves iterators/pointers/references to the
remaining elements, and doesn't throw exceptions (except from
predicate invocation).

Trap #4: The erase-remove idiom doesn't compile for ordered/unordered
associative containers.  That's because their keys are const.  It's good that
keys can't be modified in-place, because that would break the data structure's
invariants, but the resulting diagnostics can be confusing to programmers who
don't eat angle brackets and drink compiler errors for a living.  I've seen at
least two senior developers within Microsoft who were confused by this issue,
and I can only imagine how novices must be suffering.

Trap #5: For ordered/unordered associative containers, handwritten erase()
loops must be used, but they're easy to get wrong.  (Only list and
forward_list have remove_if() member functions.)  There are at least two ways
to implement this incorrectly: erasing the node that you're standing on,
and skipping nodes as a result of not paying enough attention to
iterator incrementing.


III. The Solution

To solve this problem, we must provide uniform syntax that selects the proper
semantics for each container.  This proposal provides
erase_if(container, pred), implemented with an overload for each container.

Design Decision #1: Member versus non-member?  We could provide this
functionality through member functions, like how vector::shrink_to_fit() was
added to supersede a verbose idiom.  Member functions might be more
discoverable, especially for users with autocompleting IDEs.  However,
basic_string is a cautionary tale of what happens to a class when it provides
too many member functions that aren't fundamental services.  More importantly,
because list and forward_list already have remove_if() member functions,
adding that to the other containers would increase consistency.  But as
previously noted, it's a confusing name because the member function alters the
container's size while the non-member algorithm doesn't.  The Standard Library
has other confusingly-different members versus non-members - one example is
non-member lower_bound() compiling for maps/sets while being much slower than
member lower_bound(), and an even more pernicious example is good non-member
getline() versus evil member getline().  I am reluctant to add to this problem,
hence the non-member choice in this proposal.  However, it could be argued that
providing remove_if() member functions would cause the non-member algorithm to
fall into deserved obscurity, so there would be little confusion in practice.
I would be open to that approach if the LEWG strongly favors it.

Design Decision #2: Naming?  The Library currently uses two verbs, "erase" and
"remove".  Ignoring list/forward_list's relatively obscure member functions,
"erase" always modifies container sizes, while "remove" never does.  Since the
ultimate goal of the functionality being considered here is to modify container
sizes, that's a point in favor of "erase".  Additionally, the Library currently
contains no non-member functions named erase(), and nothing at all
named erase_if().  (For completeness, remove_if(first, last, pred) could be
unambiguously overloaded with remove_if(container, pred) - unambiguous to
compilers, but perhaps not to humans.)  Another name could be chosen, although
good short names are hard to find.  (I would favor eliminate_if() as
an alternative, or perhaps discard_if().)

Design Decision #3: Just predicates, or also values?  This is related
to naming.  Providing eliminate(container, value) and
eliminate_if(container, pred) would be perfectly acceptable.  However,
providing erase(container, value) in addition to erase_if(container, pred)
would be problematic, and has therefore been avoided in this proposal.
The problem is that the ordered/unordered associative containers have
erase(key) member functions that perform efficient lookups.  This could lead
to confusion about erase(container, value)'s complexity.  (It would have to be
a linear scan, even for sets - erase(key) works with operator<() equivalence,
but erase(container, value) would have to use operator==(), and they are not
required to have any particular relationship.)  In contrast,
erase_if(container, pred) "sounds like" linear complexity (which it is),
even for ordered/unordered associative containers.  And of course, lambdas
(especially C++14's generic lambdas) make it relatively easy to use erase_if()
to eliminate all occurrences of a given value.  Informally speaking
(i.e. without hard data), I've found that having to erase all occurrences of
a particular value is a much less common task than having to erase all
elements that satisfy some condition.  On the other hand, symmetry would be
desirable, and it would prevent users from wondering why one flavor
was missing.

Additional note: These design decisions interact in one more way.  If the LEWG
wants to provide this functionality with member functions, in both predicate
and value flavors, then a verb other than "erase" (due to erase(key) as
previously mentioned) and "remove" should be chosen.  The problem is that while
list::remove_if() is perfectly fine, the signature of the value flavor is
list<T>::remove(const T&).  That is, it doesn't work transparently with
differing element and value types.  In contrast, the non-member remove()
algorithm has always worked with heterogeneous element and value types.
Alternatively, we could keep the container.remove(value) and
container.remove_if(pred) names, and simply change list/forward_list's
behavior.  That could affect the performance and (much less likely)
the correctness of existing code, but we could probably get away with it.


IV. Questions And Answers

Q1. What's the impact on the Standard?

A1. This proposal is a pure extension.  It doesn't affect user code, except for
adding a new name to namespace std.  This proposal doesn't interact with any
other proposals (it is concerned with runtime-resizable containers only, and
dynarray isn't - see [1]), and it doesn't need new Core Language features
(in fact, it's implementable in C++98 with minor implementation tweaks).

Q2. Are any containers missing here?

A2. std::array is fixed-size, so it can't be used here.  The implementation for
vector<T> works for vector<bool>, so it doesn't need to be special-cased.
(Implementers are free to optimize erase_if() for vector<bool> behind the
scenes, just as they are free to optimize count_if() and other algorithms.)
The container adaptors aren't containers and don't even provide iterators,
much less arbitrary erasure.

Q3. Does this proposal have anything to do with ranges?

A3. No.  Erasure alters a container's size, so it can't be performed with just
iterators, even if they're packaged as ranges.  erase_if() is a container-based
algorithm, not a range-based algorithm.

Q4. I looked at the Standardese section, and my brain said,
"Too Long; Didn't Standardize".

A4. That's not a question.  But yes, the Standardese diff is bulky due to the
need to edit each synopsis.  Your brain will be happier looking at the
"namespace std { [...] }" block in the Implementation section.

Q5. I saw your "// production code would [...] avoid ADL" comment in the
Implementation section.  Should the Standardese depict erase_if() calling
remove_if() with full qualification?

A5. Nope.  See 17.6.1.1 [contents]/3: "Whenever a name x defined in the
standard library is mentioned, the name x is assumed to be fully qualified as
::std::x, unless explicitly described otherwise. For example, if the Effects
section for library function F is described as calling library function G,
the function ::std::G is meant."  There are some things in the Standard, like
qualified mentions of std::pair, that are unnecessary relics of the TR1 era.

Q6. Then do you know why the Standard likes to say std::move and std::forward?

A6. Nope.

Q7. Can you describe your editorial strategy for adding sections,
or not adding them?

A7. This is a small feature (one overload per container), so I'd like to avoid
adding a whole bunch of sections.  Non-member erase_if() is similar to
non-member swap(), which was the only inhabitant of sections like
23.3.6.6 "vector specialized algorithms" [vector.special].  However,
basic_string and the unordered containers were organized differently.

Q8. What's going on with this erase_nodes_if() helper?

A8. Repeating the erase() loop for the eight ordered/unordered associative
containers would be undesirable for editorial maintenance, so I've depicted an
"exposition only" helper.  I couldn't find a very good home for it (it's common
to both the ordered and unordered associative containers, but
23.2.4 [associative.reqmts] and 23.2.5 [unord.req] are separate sections),
so I chose the most expedient option of defining it where it's first needed
(in map) and then citing it later.  It could be moved elsewhere, or the loop
could simply be copy-pasted.

Q9. What's happening with these template parameter names?  You're saying:
erase_if(unordered_map<K, T, H, P, A>& c, Predicate pred)
but that's so concise and pretty, it's inconsistent with the rest of
the Standard.  I want to see the usual template parameter spam, like:
erase_if(unordered_map<Key, T, Hash, Pred, Allocator>& c, Predicate pred)

A9. This is purely editorial (names are sometimes Words Of Power, like
25.1 [algorithms.general]/5 says, but the names chosen here can't possibly
allow users to instantiate unordered_map/etc. with bogus arguments, that's
controlled by the class definition).  There is limited precedent for varying
names (the Standard switches between Allocator and Alloc, and
28.11.2 [re.alg.match] uses ST/SA for String Traits and String Allocator).
Here, I chose brevity, but I also wanted to avoid any confusion between an
unordered container's Pred (a binary predicate for key equality) and
erase_if()'s Predicate (a unary predicate given whole elements).

Q10. Instead of overloading erase_if() for each container, should you provide
a single erase_if(Container&, Predicate) function template that's specified
to do the right thing for each container?

A10. Such a general function template could be given user-defined containers.
There aren't any "container traits", so it's impossible to determine whether a
user-defined container is vector-like, list-like, map-like, or something else.
User-defined containers could simply be rejected, but then the general function
template wouldn't be doing anything differently than the set of specific
overloads being proposed here.  Note that an author of a user-defined container
can overload erase_if() for their container in their namespace.

Q11. Could this be added to the container "requirements" tables?

A11. Yes, but at what cost in sanity?  The vector-like and list-like sequence
containers need to do different things, basic_string lives in Clause 21, and
std::array is the sequence that is not a sequence.  The ordered and unordered
associative containers all use erase_nodes_if(), but they have separate tables.
Additionally, the tables currently don't cover non-member functions - for
example, swap(x, y) is specified for each container individually, even though
they're all the same (except for std::array).


V. Standardese

1. In 21.3 [string.classes], "Header <string> synopsis", between the
"// \ref{string.io}, inserters and extractors:" and
"// \tcode{basic_string} typedef names" chunks, add (LaTeX for the
convenience of the editors):

  // \ref{string.erasure}, erasure:
  template <class charT, class traits, class A, class Predicate>
    void erase_if(basic_string<charT, traits, A>& c, Predicate pred);

2. Add a new section "Erasure [string.erasure]", as a child of
21.4.8 [string.nonmembers], placed after 21.4.8.9 [string.io], containing:

template <class charT, class traits, class A, class Predicate>
  void erase_if(basic_string<charT, traits, A>& c, Predicate pred);
Effects: Equivalent to:
c.erase(remove_if(c.begin(), c.end(), pred), c.end());

3. In 23.3.1 [sequences.general], "Header <deque> synopsis", add after swap():

template <class T, class A, class Predicate>
  void erase_if(deque<T, A>& c, Predicate pred);

4. In 23.3.1 [sequences.general], "Header <forward_list> synopsis",
add after swap():

template <class T, class A, class Predicate>
  void erase_if(forward_list<T, A>& c, Predicate pred);

5. In 23.3.1 [sequences.general], "Header <list> synopsis", add after swap():

template <class T, class A, class Predicate>
  void erase_if(list<T, A>& c, Predicate pred);

6. In 23.3.1 [sequences.general], "Header <vector> synopsis", add after swap():

template <class T, class A, class Predicate>
  void erase_if(vector<T, A>& c, Predicate pred);

7. In 23.3.3.5 [deque.special], add a new paragraph after swap():

template <class T, class A, class Predicate>
  void erase_if(deque<T, A>& c, Predicate pred);
Effects: Equivalent to:
c.erase(remove_if(c.begin(), c.end(), pred), c.end());

8. In 23.3.4.7 [forwardlist.spec], add a new paragraph after swap():

template <class T, class A, class Predicate>
  void erase_if(forward_list<T, A>& c, Predicate pred);
Effects: Equivalent to:
c.remove_if(pred);

9. In 23.3.5.6 [list.special], add a new paragraph after swap():

template <class T, class A, class Predicate>
  void erase_if(list<T, A>& c, Predicate pred);
Effects: Equivalent to:
c.remove_if(pred);

10. In 23.3.6.6 [vector.special], add a new paragraph after swap():

template <class T, class A, class Predicate>
  void erase_if(vector<T, A>& c, Predicate pred);
Effects: Equivalent to:
c.erase(remove_if(c.begin(), c.end(), pred), c.end());

11. In 23.4.2 [associative.map.syn], add after swap(map&, map&):

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

12. In 23.4.2 [associative.map.syn], add after swap(multimap&, multimap&):

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

13. In 23.4.3 [associative.set.syn], add after swap(set&, set&):

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

14. In 23.4.3 [associative.set.syn], add after swap(multiset&, multiset&):

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

15. In 23.4.4.5 [map.special], add a new paragraph after swap():

template <class K, class T, class C, class A, class Predicate>
  void erase_if(map<K, T, C, A>& c, Predicate pred);
Effects: Given the following function template, described for exposition only:
template <class Container, class Predicate>
  void erase_nodes_if(Container& c, Predicate pred) { // exposition only
  for (auto i = c.begin(), last = c.end(); i != last; ) {
    if (pred(*i)) {
      i = c.erase(i);
    } else {
      ++i;
    }
  }
}
Equivalent to:
erase_nodes_if(c, pred);

16. In 23.4.5.4 [multimap.special], add a new paragraph after swap():
(Note to the editors: [map.special] should be a LaTeX citation.)

template <class K, class T, class C, class A, class Predicate>
  void erase_if(multimap<K, T, C, A>& c, Predicate pred);
Effects: Given the erase_nodes_if() function template described for
exposition only in [map.special], equivalent to:
erase_nodes_if(c, pred);

17. In 23.4.6.3 [set.special], add a new paragraph after swap():
(Note to the editors: [map.special] should be a LaTeX citation.)

template <class K, class C, class A, class Predicate>
  void erase_if(set<K, C, A>& c, Predicate pred);
Effects: Given the erase_nodes_if() function template described for
exposition only in [map.special], equivalent to:
erase_nodes_if(c, pred);

18. In 23.4.7.3 [multiset.special], add a new paragraph after swap():
(Note to the editors: [map.special] should be a LaTeX citation.)

template <class K, class C, class A, class Predicate>
  void erase_if(multiset<K, C, A>& c, Predicate pred);
Effects: Given the erase_nodes_if() function template described for
exposition only in [map.special], equivalent to:
erase_nodes_if(c, pred);

19. In 23.5.2 [unord.map.syn], between the swaps and comparisons, add:

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

20. In 23.5.3 [unord.set.syn], between the swaps and comparisons, add:

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

21. Add a new section "unordered_map erasure [unord.map.erasure]",
as a child of 23.5.4 [unord.map], placed after
23.5.4.5 [unord.map.swap], containing:
(Note to the editors: [map.special] should be a LaTeX citation.)

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);
Effects: Given the erase_nodes_if() function template described for
exposition only in [map.special], equivalent to:
erase_nodes_if(c, pred);

22. Add a new section "unordered_multimap erasure [unord.multimap.erasure]",
as a child of 23.5.5 [unord.multimap], placed after
23.5.5.4 [unord.multimap.swap], containing:
(Note to the editors: [map.special] should be a LaTeX citation.)

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);
Effects: Given the erase_nodes_if() function template described for
exposition only in [map.special], equivalent to:
erase_nodes_if(c, pred);

23. Add a new section "unordered_set erasure [unord.set.erasure]",
as a child of 23.5.6 [unord.set], placed after
23.5.6.3 [unord.set.swap], containing:
(Note to the editors: [map.special] should be a LaTeX citation.)

template <class K, class H, class P, class A, class Predicate>
  void erase_if(unordered_set<K, H, P, A>& c, Predicate pred);
Effects: Given the erase_nodes_if() function template described for
exposition only in [map.special], equivalent to:
erase_nodes_if(c, pred);

24. Add a new section "unordered_multiset erasure [unord.multiset.erasure]",
as a child of 23.5.7 [unord.multiset], placed after
23.5.7.3 [unord.multiset.swap], containing:
(Note to the editors: [map.special] should be a LaTeX citation.)

template <class K, class H, class P, class A, class Predicate>
  void erase_if(unordered_multiset<K, H, P, A>& c, Predicate pred);
Effects: Given the erase_nodes_if() function template described for
exposition only in [map.special], equivalent to:
erase_nodes_if(c, pred);


VI. Acknowledgements

Thanks to Bruce Dawson, David Cravey, Giovanni Dicanio, Herb Sutter,
Kate Gregory, Ken Sykes, Marshall Clow, Michael Goulding, Michael McLaughlin,
and Scott Meyers for reviewing this proposal.


VII. References

All of the Standardese citations in this proposal are to Working Paper N3936:
http://www.open-std.org/jtc1/sc22/wg21/prot/14882fdis/n3936.pdf

[1] N3820 "Working Draft, Technical Specification - Array Extensions"
edited by Lawrence Crowl:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3820.html


VIII. Implementation

Compiled with Visual C++ 2013 Update 2.

C:\Temp>type meow.cpp
#include <algorithm>
#include <deque>
#include <forward_list>
#include <list>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

namespace std { // production code would be _Ugly and would avoid ADL

template <class charT, class traits, class A, class Predicate>
  void erase_if(basic_string<charT, traits, A>& c, Predicate pred) {
  c.erase(remove_if(c.begin(), c.end(), pred), c.end());
}

template <class T, class A, class Predicate>
  void erase_if(deque<T, A>& c, Predicate pred) {
  c.erase(remove_if(c.begin(), c.end(), pred), c.end());
}

template <class T, class A, class Predicate>
  void erase_if(forward_list<T, A>& c, Predicate pred) {
  c.remove_if(pred);
}

template <class T, class A, class Predicate>
  void erase_if(list<T, A>& c, Predicate pred) {
  c.remove_if(pred);
}

template <class T, class A, class Predicate>
  void erase_if(vector<T, A>& c, Predicate pred) {
  c.erase(remove_if(c.begin(), c.end(), pred), c.end());
}

template <class Container, class Predicate>
  void erase_nodes_if(Container& c, Predicate pred) { // exposition only
  for (auto i = c.begin(), last = c.end(); i != last; ) {
    if (pred(*i)) {
      i = c.erase(i);
    } else {
      ++i;
    }
  }
}

template <class K, class T, class C, class A, class Predicate>
  void erase_if(map<K, T, C, A>& c, Predicate pred) {
  erase_nodes_if(c, pred);
}

template <class K, class T, class C, class A, class Predicate>
  void erase_if(multimap<K, T, C, A>& c, Predicate pred) {
  erase_nodes_if(c, pred);
}

template <class K, class C, class A, class Predicate>
  void erase_if(set<K, C, A>& c, Predicate pred) {
  erase_nodes_if(c, pred);
}

template <class K, class C, class A, class Predicate>
  void erase_if(multiset<K, C, A>& c, Predicate pred) {
  erase_nodes_if(c, pred);
}

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) {
  erase_nodes_if(c, 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) {
  erase_nodes_if(c, pred);
}

template <class K, class H, class P, class A, class Predicate>
  void erase_if(unordered_set<K, H, P, A>& c, Predicate pred) {
  erase_nodes_if(c, pred);
}

template <class K, class H, class P, class A, class Predicate>
  void erase_if(unordered_multiset<K, H, P, A>& c, Predicate pred) {
  erase_nodes_if(c, pred);
}

} // namespace std

#include <iostream>
#include <utility>
using namespace std;

template <typename T> void print_elem(const T& t) {
    cout << t;
}

template <typename A, typename B> void print_elem(const pair<A, B>& p) {
    cout << p.first << "/" << p.second;
}

template <typename C> void print(const string& s, const C& c) {
    cout << s << ": [";

    for (auto first = c.begin(), last = c.end(), i = first; i != last; ++i) {
        if (i != first) {
            cout << " ";
        }

        print_elem(*i);
    }

    cout << "]" << endl;
}

int main() {
    auto is_vowel = [](const char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    };

    auto is_odd = [](const int i) { return i % 2 != 0; };

    auto is_odd_pair = [](const pair<const int, string>& p) {
        return p.first % 2 != 0;
    };

    string str("cute fluffy kittens");
    cout << "string before: " << str << endl;
    erase_if(str, is_vowel);
    cout << "string  after: " << str << endl;

    deque<int> d = { 10, 11, 12, 14, 15, 17, 18, 19 };
    print("deque before", d);
    erase_if(d, is_odd);
    print("deque  after", d);

    forward_list<int> fl = { 10, 11, 12, 14, 15, 17, 18, 19 };
    print("forward_list before", fl);
    erase_if(fl, is_odd);
    print("forward_list  after", fl);

    list<int> l = { 10, 11, 12, 14, 15, 17, 18, 19 };
    print("list before", l);
    erase_if(l, is_odd);
    print("list  after", l);

    vector<int> v = { 10, 11, 12, 14, 15, 17, 18, 19 };
    print("vector before", v);
    erase_if(v, is_odd);
    print("vector  after", v);

    map<int, string> m = { { 10, "A" }, { 11, "B" }, { 12, "C" },
        { 14, "D" }, { 15, "E" }, { 17, "F" }, { 18, "G" }, { 19, "H" } };
    print("map before", m);
    erase_if(m, is_odd_pair);
    print("map  after", m);

    multimap<int, string> mm = { { 20, "S" }, { 21, "T" }, { 22, "U" },
        { 22, "V" }, { 23, "W" }, { 23, "X" }, { 24, "Y" }, { 25, "Z" } };
    print("multimap before", mm);
    erase_if(mm, is_odd_pair);
    print("multimap  after", mm);

    set<int> s = { 10, 11, 12, 14, 15, 17, 18, 19 };
    print("set before", s);
    erase_if(s, is_odd);
    print("set  after", s);

    multiset<int> ms = { 20, 21, 22, 22, 23, 23, 24, 25 };
    print("multiset before", ms);
    erase_if(ms, is_odd);
    print("multiset  after", ms);

    unordered_map<int, string> um = { { 10, "A" }, { 11, "B" }, { 12, "C" },
        { 14, "D" }, { 15, "E" }, { 17, "F" }, { 18, "G" }, { 19, "H" } };
    print("unordered_map before", um);
    erase_if(um, is_odd_pair);
    print("unordered_map  after", um);

    unordered_multimap<int, string> umm = { { 20, "S" }, { 21, "T" },
        { 22, "U" }, { 22, "V" }, { 23, "W" }, { 23, "X" }, { 24, "Y" },
        { 25, "Z" } };
    print("unordered_multimap before", umm);
    erase_if(umm, is_odd_pair);
    print("unordered_multimap  after", umm);

    unordered_set<int> us = { 10, 11, 12, 14, 15, 17, 18, 19 };
    print("unordered_set before", us);
    erase_if(us, is_odd);
    print("unordered_set  after", us);

    unordered_multiset<int> ums = { 20, 21, 22, 22, 23, 23, 24, 25 };
    print("unordered_multiset before", ums);
    erase_if(ums, is_odd);
    print("unordered_multiset  after", ums);

    v = { 17, 29, 1729 };
    print("vector before erasing everything", v);
    erase_if(v, is_odd);
    print("vector  after erasing everything", v);
    v = { 256, 512, 1024 };
    print("vector before erasing nothing", v);
    erase_if(v, is_odd);
    print("vector  after erasing nothing", v);
    v.clear();
    print("empty vector before", v);
    erase_if(v, is_odd);
    print("empty vector  after", v);

    l = { 17, 29, 1729 };
    print("list before erasing everything", l);
    erase_if(l, is_odd);
    print("list  after erasing everything", l);
    l = { 256, 512, 1024 };
    print("list before erasing nothing", l);
    erase_if(l, is_odd);
    print("list  after erasing nothing", l);
    l.clear();
    print("empty list before", l);
    erase_if(l, is_odd);
    print("empty list  after", l);

    s = { 17, 29, 1729 };
    print("set before erasing everything", s);
    erase_if(s, is_odd);
    print("set  after erasing everything", s);
    s = { 256, 512, 1024 };
    print("set before erasing nothing", s);
    erase_if(s, is_odd);
    print("set  after erasing nothing", s);
    s.clear();
    print("empty set before", s);
    erase_if(s, is_odd);
    print("empty set  after", s);

    cout << boolalpha;
    auto is_true = [](const bool b) { return b; };
    vector<bool> vb = { false, true, false, false, true, true, false, true };
    print("vector<bool> before", vb);
    erase_if(vb, is_true);
    print("vector<bool>  after", vb);
}

C:\Temp>cl /EHsc /nologo /W4 /MTd meow.cpp
meow.cpp

C:\Temp>meow
string before: cute fluffy kittens
string  after: ct flffy kttns
deque before: [10 11 12 14 15 17 18 19]
deque  after: [10 12 14 18]
forward_list before: [10 11 12 14 15 17 18 19]
forward_list  after: [10 12 14 18]
list before: [10 11 12 14 15 17 18 19]
list  after: [10 12 14 18]
vector before: [10 11 12 14 15 17 18 19]
vector  after: [10 12 14 18]
map before: [10/A 11/B 12/C 14/D 15/E 17/F 18/G 19/H]
map  after: [10/A 12/C 14/D 18/G]
multimap before: [20/S 21/T 22/U 22/V 23/W 23/X 24/Y 25/Z]
multimap  after: [20/S 22/U 22/V 24/Y]
set before: [10 11 12 14 15 17 18 19]
set  after: [10 12 14 18]
multiset before: [20 21 22 22 23 23 24 25]
multiset  after: [20 22 22 24]
unordered_map before: [18/G 10/A 19/H 11/B 12/C 14/D 15/E 17/F]
unordered_map  after: [18/G 10/A 12/C 14/D]
unordered_multimap before: [20/S 21/T 22/U 22/V 23/W 23/X 24/Y 25/Z]
unordered_multimap  after: [20/S 22/U 22/V 24/Y]
unordered_set before: [18 10 19 11 12 14 15 17]
unordered_set  after: [18 10 12 14]
unordered_multiset before: [20 21 22 22 23 23 24 25]
unordered_multiset  after: [20 22 22 24]
vector before erasing everything: [17 29 1729]
vector  after erasing everything: []
vector before erasing nothing: [256 512 1024]
vector  after erasing nothing: [256 512 1024]
empty vector before: []
empty vector  after: []
list before erasing everything: [17 29 1729]
list  after erasing everything: []
list before erasing nothing: [256 512 1024]
list  after erasing nothing: [256 512 1024]
empty list before: []
empty list  after: []
set before erasing everything: [17 29 1729]
set  after erasing everything: []
set before erasing nothing: [256 512 1024]
set  after erasing nothing: [256 512 1024]
empty set before: []
empty set  after: []
vector<bool> before: [false true false false true true false true]
vector<bool>  after: [false false false false]

(end)
