Is std::multimap "stable" ?

[melfar]

Hello.

[lib.associative.reqmts] 9 says:

'' The fundamental property of iterators of associative containers is
that they iterate through the containers in the non-descending order of
keys where non-descending is defined by the comparison that was used to
construct them. ''

Does it mean that if I insert values into a multimap with equal keys, I
am guaranteed to receive them back with find() and equal_range() in the
same order I inserted them?

Thanks,
melfar

[Howard Hinnant]

In article <11*********************@t31g2000cwb.googlegroups. com>,
"me****@gmail.com" <me****@gmail.com> wrote:

Hello.

[lib.associative.reqmts] 9 says:

'' The fundamental property of iterators of associative containers is
that they iterate through the containers in the non-descending order of
keys where non-descending is defined by the comparison that was used to
construct them. ''

Does it mean that if I insert values into a multimap with equal keys, I
am guaranteed to receive them back with find() and equal_range() in the
same order I inserted them?

Thanks,
melfar

No, not according to the standard. However there are several issues of
interest.

First, see:

http://www.open-std.org/jtc1/sc22/wg...ctive.html#371

This LWG issue is in the working draft for C++0X (voted in just two
weeks ago). It states that once your equal keys are in the multimap,
they won't change order as the multimap rebalances due to further
inserts and erases. But it doesn't guarantee that the keys are placed
in any particular order related to the order in which they were inserted.

However, also see:

http://www.open-std.org/jtc1/sc22/wg...ctive.html#233

and a related paper:

http://www.open-std.org/jtc1/sc22/wg...005/n1780.html

If N1780 is accepted as the proposed resolution to 233, then your equal
keys will be in the order you inserted them, or as otherwise directed by
the optional "hint" parameter. That still doesn't mean that find()
would find the keys in that order, but it does mean that equal_range,
lower/upper_bound would find them in the expected order.

N1780 is still controversial on the committee, but does have support.
N1780 also points out that all existing implementations currently
interpret "insert without hint" as "insert at upper bound" (equal keys
will be in the order you inserted them). So there is also a second
answer to your original question:

Yes, all implementations will keep your inserted equal keys in the order
you inserted them. Use lower_bound or equal_range, not find, to find
them in that order.

Sorry the answer is so complicated.

-Howard