Rationale:

The LWG agrees that this guarantee is necessary for common user idioms to work, and that all existing implementations provide this property. Note that this resolution guarantees stability for multimap and multiset, not for all associative containers in general.

[ Mont Tremblant: Changed set and map to multiset and multimap. ]

[ Joe Gottman points out that the provided wording does not address multimap and multiset. N1780 also addresses this issue and suggests wording. ]

[ Lillehammer: Matt provided wording ]

Proposed resolution:

Add the following to the end of [associative.reqmts] paragraph 4: "For multiset and multimap, insertand erase are stable: they preserve the relative ordering of equivalent elements.

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.