Are insert and erase stable for unordered_multiset and unordered_multimap?
Matt Austern

Created on 2005-07-03.00:00:00 last changed 165 months ago


Date: 2010-10-21.18:28:33

Proposed resolution:

Wording for the proposed resolution is taken from the equivalent text for associative containers.

Change [unord.req], Unordered associative containers, paragraph 6 to:

An unordered associative container supports unique keys if it may contain at most one element for each key. Otherwise, it supports equivalent keys. unordered_set and unordered_map support unique keys. unordered_multiset and unordered_multimap support equivalent keys. In containers that support equivalent keys, elements with equivalent keys are adjacent to each other. For unordered_multiset and unordered_multimap, insert and erase preserve the relative ordering of equivalent elements.

Change [unord.req], Unordered associative containers, paragraph 8 to:

The elements of an unordered associative container are organized into buckets. Keys with the same hash code appear in the same bucket. The number of buckets is automatically increased as elements are added to an unordered associative container, so that the average number of elements per bucket is kept below a bound. Rehashing invalidates iterators, changes ordering between elements, and changes which buckets elements appear in, but does not invalidate pointers or references to elements. For unordered_multiset and unordered_multimap, rehashing preserves the relative ordering of equivalent elements.

Date: 2010-10-21.18:28:33

[ Toronto: We have a resolution now. Moved to Review. Some concern was noted as to whether this conflicted with existing practice or not. An additional concern was in specifying (partial) ordering for an unordered container. ]

Date: 2010-10-21.18:28:33

[ Moved to open (from review): There is no resolution. ]

Date: 2005-07-03.00:00:00

Issue 371 deals with stability of multiset/multimap under insert and erase (i.e. do they preserve the relative order in ranges of equal elements). The same issue applies to unordered_multiset and unordered_multimap.

Date User Action Args
2010-10-21 18:28:33adminsetmessages: + msg2921
2010-10-21 18:28:33adminsetmessages: + msg2920
2010-10-21 18:28:33adminsetmessages: + msg2919
2005-07-03 00:00:00admincreate