This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of CD1 status.

518. Are insert and erase stable for unordered_multiset and unordered_multimap?

Section: 23.2.8 [unord.req], 99 [tr.unord.req] Status: CD1 Submitter: Matt Austern Opened: 2005-07-03 Last modified: 2016-01-28

Priority: Not Prioritized

View other active issues in [unord.req].

View all other issues in [unord.req].

View all issues with CD1 status.

Discussion:

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.

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

[ 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. ]

Proposed resolution:

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

Change 23.2.8 [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 23.2.8 [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.