2977. unordered_meow::merge() has incorrect Throws: clause

Section: 23.2.8 [unord.req] Status: C++20 Submitter: Tim Song Opened: 2017-06-14 Last modified: 2021-02-25

Priority: 0

View other active issues in [unord.req].

View all other issues in [unord.req].

View all issues with C++20 status.

Discussion:

As pointed out in this StackOverflow question, unordered_{map,multimap,set,multiset}::merge() may need to rehash to maintain its max_load_factor invariant, which may require allocation, which may throw.

[2017-07 Toronto Monday issue prioritization]

Priority 0; move to Ready

Proposed resolution:

This wording is relative to N4659.

  1. In 23.2.8 [unord.req], edit Table 91 "Unordered associative container requirements" as indicated:

    Table 91 — Unordered associative container requirements (in addition to container)
    Expression Return type Assertion/note
    pre-/post-condition    		 Complexity
    …
    a.merge(a2) void Requires: a.get_allocator() == a2.get_allocator().
    Attempts to extract each element in a2 and insert it into a using the hash function and key equality predicate of a. In containers with unique keys, if there is an element in a with key equivalent to the key of an element from a2, then that element is not extracted from a2.
    Postconditions: Pointers and references to the transferred elements of a2 refer to those same elements but as members of a. Iterators referring to the transferred elements and all iterators referring to a will be invalidated, but iterators to elements remaining in a2 will remain valid.
    Throws: Nothing unless the hash function or key equality predicate throws.     		Average case 𝒪(N), where N is a2.size().
    Worst case 𝒪(N*a.size()+N).
    …