From Cppwiki

C++ provides several easy ways to find and erase from an arbitrary container c all elements e for which some boolean predicate pr(e) is true.

Erase-remove idiom

The erase-remove idiom is a two-step procedure that brings all but the "removed" items to the front of the container and then "erases" the rest.

This algorithm runs in O(n) worst-case time for all containers and cannot be used on containers with immutable keys (map, set, multimap, and multiset).

c.erase(remove_if(c.begin(), c.end(), pr), c.end());

If you simply want to erase all instances of some element x:

c.erase(remove(c.begin(), c.end(), x), c.end());

Find-and-erase loop

The following is approximately the same algorithm as list member remove_if(). It works on any container. For random-access containers, it runs in worst-case O(n²) but average-case O(kn) where k is the number of elements removed. For DAG-based containers, it runs in O(n) in the worst case but with less overhead per element than the erase-remove idiom, especially if the elements are expensive to copy.

for (iterator i = c.begin(); i != c.end(); false) {
  if (pr(*i)) c.erase(i++); else ++i;
}

This is functionally equivalent:

for (iterator i = c.begin(); i != c.end(); false) {
  iterator cur = i++;
  if (pr(*cur)) c.erase(cur);
}

NOTE: The following code elicits undefined behaviour and is likely to crash your program because iterators are invalidated upon erasure:

for (iterator i = c.begin(); i != c.end(); ++i) {
  if (pr(c)) c.erase(i); // BAD
}

Combined

erase_if is a demonstration on automatically using the correct algorithm for the container.

Erase key from sorted container

Removing a key from a sorted container can be done in O(log n) time in most cases.

If you want to remove a particular element from a map, set, multimap, or multiset, you should use their member erase(x).

If you want to remove some item x from any sorted container c:

pair<iterator, iterator> p = equal_range(c.begin(), c.end(), x);
c.erase(p.first, p.second);