The requirements for multiset and multimap containers (23.1 [lib.containers.requirements], 23.1.2 [lib.associative.reqmnts], 23.3.2 [lib.multimap] and 23.3.4 [lib.multiset]) make no mention of the stability of the required (mutating) member functions. It appears the standard allows these functions to reorder equivalent elements of the container at will, yet the pervasive red-black tree implementation appears to provide stable behaviour.

This is of most concern when considering the behaviour of erase(). A stability requirement would guarantee the correct working of the following 'idiom' that removes elements based on a certain predicate function.

  multimap<int, int> m;
  multimap<int, int>::iterator i = m.begin();
  while (i != m.end()) {
      if (pred(i))
          m.erase (i++);
      else
          ++i;
  }

Although clause 23.1.2/8 guarantees that i remains a valid iterator througout this loop, absence of the stability requirement could potentially result in elements being skipped. This would make this code incorrect, and, furthermore, means that there is no way of erasing these elements without iterating first over the entire container, and second over the elements to be erased. This would be unfortunate, and have a negative impact on both performance and code simplicity.

If the stability requirement is intended, it should be made explicit (probably through an extra paragraph in clause 23.1.2).

If it turns out stability cannot be guaranteed, i'd argue that a remark or footnote is called for (also somewhere in clause 23.1.2) to warn against relying on stable behaviour (as demonstrated by the code above). If most implementations will display stable behaviour, any problems emerging on an implementation without stable behaviour will be hard to track down by users. This would also make the need for an erase_if() member function that much greater.

This issue is somewhat related to LWG issue 130.