In a comparison of STL with the Smalltalk 80 collection classes, STL
seemed to be missing the following:

for_each_if(first, last, func, pred)

 Applies func to each element in the range [first, last) for
 which pred(*i) == true.  (This is comparable to the Smalltalk
 select method.)

multiset::insert(x, n)

 Inserts n copies of x.  (For compatibility with
 sequences and ST80 Bag class.)

{multi}map::find_value(first, last, value)

 Returns the first iterator i in the range [first, last) for
 which (*i).second == value.

const {multi}map::operator[](key) const

 Returns a reference to the value associated with key, without
 inserting a new element if key is not found.  This would
 probably have to return a null reference for a not-found
 condition, which may be politically incorrect, but I find
 the current behavior of operator[] counter-intuitive.  Besides,
 not having a const operator[] violates one of Scott Meyers' rules.

It would be useful to have iterator adaptors that could extract just
the key or just the value from a {multi}map.

It might also be useful to support relational composition (like Smalltalk
MappedCollection):
 template <class MappedContainer1, class MappedContainer2>
 class composed_map {
          public:
            composed_map(MappedContainer1& mapa, MappedContainer2& mapb);
            reference operator[](const key_type& x)
                { return mapb[mapa[x]]; }
        };
(I would have preferred to show a non-template class inheriting from a base
class also common to map and multimap.)

Also, it seems to me that remove_copy() would be more appropriately called
copy_if(), since it does not actually remove elements (as does remove()),
and it takes a predicate. This would require the behavior to be changed
from copying elements that fail the predicate to copying elements that
satisfy the predicate.