[ moderator's note: submitted to C++ Commitee. -sdc ]

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:
http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-closed.html#130

Frank Compagner



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]