2540. unordered_multimap::insert hint iterator

Section: 23.2.8 [unord.req] Status: C++17 Submitter: Isaac Hier Opened: 2015-09-16 Last modified: 2017-07-30

Priority: 3

View other active issues in [unord.req].

View all other issues in [unord.req].

View all issues with C++17 status.

Discussion:

I have been wondering about the C++ standard requirements regarding the hint iterator for insertion into an unordered_multimap (and I imagine a similar question could be asked of unordered_map, but I have not researched that topic). As far as I can tell, it seems perfectly valid for an implementation to allow only valid dereferencable iterators to be used as the hint argument for this member function. If that is correct, it means that one could not expect the end iterator to be used as a valid hint nor could one use the begin iterator of an empty unordered_multimap as the hint. However, this essentially precludes all uses of inserter on an empty unordered_multimap seeing as the inserter functor requires that a hint iterator be passed to its constructor.

Howard Hinnant:

The intent of the standard is that the iterator produced from container c by c.end() is a valid (but non-dereferenceable) iterator into container c. It is reachable by every other iterator into c.

It appears to me that you and the Bloomberg implementation have fallen victim to a type-o in the Unordered associative container requirements, Table 102. The row containing:

a.insert(q, t);

should read instead:

a.insert(p, t);

The distinction is that p is valid, and q is both valid and dereferenceable. The correction of this type-o would make unordered container insert consistent with unordered emplace_hint, associative insert, and associative emplace_hint.

[2016-08 - Chicago]

Thurs AM: Moved to Tentatively Ready

Proposed resolution:

Change the insert-with-hint row in Table 102 Unordered associative container requirements like so:

a.insert(qp, t);

iterator

Requires: If t is a non-const ...

Average Case ...