Title
unordered_map::insert(T&&) protection should apply to map too
Status
c++14
Section
[map.modifiers][multimap.modifiers] [unord.map.modifiers][unord.multimap.modifiers]
Submitter
P.J. Plauger

Created on 2010-10-14.00:00:00 last changed 89 months ago

Messages

Date: 2012-11-03.04:16:46

Proposed resolution:

  1. Change [map.modifiers] around p. 1 as indicated:
    template <class P> pair<iterator, bool> insert(P&& x);
    template <class P> pair<iterator, bool> insert(const_iterator position, P&& x);
    
    1 Requires: P shall be convertible to value_type.

    If P is instantiated as a reference type, then the argument x is copied from. Otherwise x is considered to be an rvalue as it is converted to value_type and inserted into the map. Specifically, in such cases CopyConstructible is not required of key_type or mapped_type unless the conversion from P specifically requires it (e.g., if P is a tuple<const key_type, mapped_type>, then key_type must be CopyConstructible). The signature taking InputIterator parameters does not require CopyConstructible of either key_type or mapped_type if the dereferenced InputIterator returns a non-const rvalue pair<key_type,mapped_type>. Otherwise CopyConstructible is required for both key_type and mapped_type.
    ? Effects: The first form is equivalent to return emplace(std::forward<P>(x)). The second form is equivalent to return emplace_hint(position, std::forward<P>(x)).

    ? Remarks: These signatures shall not participate in overload resolution unless std::is_constructible<value_type, P&&>::value is true.

  2. Change [multimap.modifiers] around p. 1 as indicated:
    template <class P> iterator insert(P&& x);
    template <class P> iterator insert(const_iterator position, P&& x);
    
    1 Requires: P shall be convertible to value_type.

    If P is instantiated as a reference type, then the argument x is copied from. Otherwise x is considered to be an rvalue as it is converted to value_type and inserted into the map. Specifically, in such cases CopyConstructible is not required of key_type or mapped_type unless the conversion from P specifically requires it (e.g., if P is a tuple<const key_type, mapped_type>, then key_type must be CopyConstructible). The signature taking InputIterator parameters does not require CopyConstructible of either key_type or mapped_type if the dereferenced InputIterator returns a non-const rvalue pair<key_type, mapped_type>. Otherwise CopyConstructible is required for both key_type and mapped_type.
    ? Effects: The first form is equivalent to return emplace(std::forward<P>(x)). The second form is equivalent to return emplace_hint(position, std::forward<P>(x)).

    ? Remarks: These signatures shall not participate in overload resolution unless std::is_constructible<value_type, P&&>::value is true.

  3. Change [unord.map.modifers] around p. 1 as indicated:
    template <class P>
    pair<iterator, bool> insert(P&& obj);
    
    1 Requires: value_type is constructible from std::forward<P>(obj).

    2 Effects: equivalent to return emplace(std::forward<P>(obj)). Inserts obj converted to value_type if and only if there is no element in the container with key equivalent to the key of value_type(obj).

    3 Returns: The bool component of the returned pair object indicates whether the insertion took place and the iterator component points to the element with key equivalent to the key of value_type(obj).

    4 Complexity: Average case O(1), worst case O(size()).

    53 Remarks: This signature shall not participate in overload resolution unless P is implicitly convertible to value_typestd::is_constructible<value_type, P&&>::value is true.

    template <class P>
    iterator insert(const_iterator hint, P&& obj);
    
    6 Requires: value_type is constructible from std::forward<P>(obj).

    7? Effects: equivalent to return emplace_hint(hint, std::forward<P>(obj)). Inserts obj converted to value_type if and only if there is no element in the container with key equivalent to the key of value_type(obj). The iterator hint is a hint pointing to where the search should start.

    8 Returns: An iterator that points to the element with key equivalent to the key of value_type(obj).

    9 Complexity: Average case O(1), worst case O(size()).

    10? Remarks: This signature shall not participate in overload resolution unless P is implicitly convertible to value_typestd::is_constructible<value_type, P&&>::value is true.

  4. Change [unord.multimap.modifers] around p. 1 as indicated:
    template <class P>
    iterator insert(P&& obj);
    
    1 Requires: value_type is constructible from std::forward<P>(obj).

    2 Effects: equivalent to return emplace(std::forward<P>(obj)). Inserts obj converted to value_type.

    3 Returns: An iterator that points to the element with key equivalent to the key of value_type(obj).

    4 Complexity: Average case O(1), worst case O(size()).

    53 Remarks: This signature shall not participate in overload resolution unless P is implicitly convertible to value_typestd::is_constructible<value_type, P&&>::value is true.

    template <class P>
    iterator insert(const_iterator hint, P&& obj);
    
    6 Requires: value_type is constructible from std::forward<P>(obj).

    7? Effects: equivalent to return emplace_hint(hint, std::forward<P>(obj)). Inserts obj converted to value_type. The iterator hint is a hint pointing to where the search should start.

    8 Returns: An iterator that points to the element with key equivalent to the key of value_type(obj).

    9 Complexity: Average case O(1), worst case O(size()).

    10? Remarks: This signature shall not participate in overload resolution unless P is implicitly convertible to value_typestd::is_constructible<value_type, P&&>::value is true.

Date: 2012-11-03.04:16:46

[ 2012, Portland: applied to WP ]

Date: 2012-02-12.18:36:43

[ 2012, Kona ]

Moved to Tentatively Ready by the post-Kona issues processing subgroup, after much discussion on Daniel's analysis of Copy Initialization and move semantics, which we ultimately agreed with.

Date: 2011-10-02.00:00:00

[ 2011-10-02 Daniel comments and refines the proposed wording ]

Unfortunately the template constraints expressed as "P is implicitly convertible to value_type" reject the intended effect to support move-only key types, which was the original intention when the library became move-enabled through the rvalue-reference proposals by Howard (This can clearly be deduced from existing carefully selected wording that emphasizes that CopyConstructible is only required for special situations involving lvalues or const rvalues as arguments). The root of the problem is based on current core rules, where an "implicitly converted" value has copy-initialization semantics. Consider a move-only key type KM, some mapped type T, and a source value p of type P equal to std::pair<KM, T>, this is equivalent to:

std::pair<const KM, T> dest = std::move(p);

Now [dcl.init] p16 b6 sb2 says that the effects of this heterogeneous copy-initialization (p has a different type than dest) are as-if a temporary of the target type std::pair<const KM, T> is produced from the rvalue p of type P (which is fine), and this temporary is used to initialize dest. This second step cannot succeed, because we cannot move from const KM to const KM. This means that std::is_convertible<P, std::pair<const KM, T>>::value is false.

But the actual code that is required (with the default allocator) is simply a direct-initialization from P to value_type, so imposing an implicit conversion is more than necessary. Therefore I strongly recommend to reduce the "overload participation" constraint to std::is_constructible<std::pair<const KM, T>, P>::value instead. This change is the only change that has been performed to the previous proposed wording from Pablo shown below.

Date: 2011-08-18.17:55:31

[ 2011 Bloomington ]

The effects of these inserts can be concisely stated in terms of emplace(). Also, the correct term is "EmplaceConstructible", not "constructible".

New wording by Pablo, eliminating duplicate requirements already implied by the effects clause. Move to Review.

Date: 2010-11-13.23:03:59

[ 2010 Batavia: ]

We need is_convertible, not is_constructible, both in ordered and unordered containers.

Date: 2010-10-29.00:00:00

[ 2010-10-29 Daniel comments: ]

I believe both paragraphs need more cleanup: First, the current Requires element conflict with the Remark; second, it seems to me that the whole single Requires element is intended to be split into a Requires and an Effects element; third, the reference to tuple is incorrect (noticed by Paolo Carlini); fourth, it refers to some non-existing InputIterator parameter relevant for a completely different overload; sixth, the return type of the overload with hint is wrong. The following proposed resolution tries to solve these issues as well and uses similar wording as for the corresponding unordered containers. Unfortunately it has some redundancy over TableĀ 99, but I did not remove the specification because of the more general template parameter P - the TableĀ 99 requirements apply only for an argument identical to value_type.

Daniel's Proposed resolution (not current):

  1. Change [map.modifiers] around p. 1 as indicated:
    template <class P> pair<iterator, bool> insert(P&& x);
    template <class P> pair<iterator, bool> insert(const_iterator position, P&& x);
    

    1 Requires: P shall be convertible to value_type is constructible from std::forward<P>(x)..

    If P is instantiated as a reference type, then the argument x is copied from. Otherwise x is considered to be an rvalue as it is converted to value_type and inserted into the map. Specifically, in such cases CopyConstructible is not required of key_type or mapped_type unless the conversion from P specifically requires it (e.g., if P is a tuple<const key_type, mapped_type>, then key_type must be CopyConstructible). The signature taking InputIterator parameters does not require CopyConstructible of either key_type or mapped_type if the dereferenced InputIterator returns a non-const rvalue pair<key_type,mapped_type>. Otherwise CopyConstructible is required for both key_type and mapped_type.
    ? Effects: Inserts x converted to value_type if and only if there is no element in the container with key equivalent to the key of value_type(x). For the second form, the iterator position is a hint pointing to where the search should start.

    ? Returns: For the first form, the bool component of the returned pair object indicates whether the insertion took place and the iterator component - or for the second form the returned iterator - points to the element with key equivalent to the key of value_type(x).

    ? Complexity: Logarithmic in general, but amortized constant if x is inserted right before position.

    ? Remarks: These signatures shall not participate in overload resolution unless P is implicitly convertible to value_type.

  2. Change [multimap.modifiers] around p. 1 as indicated:
    template <class P> iterator insert(P&& x);
    template <class P> iterator insert(const_iterator position, P&& x);
    

    1 Requires: P shall be convertible to value_type is constructible from std::forward<P>(x).

    If P is instantiated as a reference type, then the argument x is copied from. Otherwise x is considered to be an rvalue as it is converted to value_type and inserted into the map. Specifically, in such cases CopyConstructible is not required of key_type or mapped_type unless the conversion from P specifically requires it (e.g., if P is a tuple<const key_type, mapped_type>, then key_type must be CopyConstructible). The signature taking InputIterator parameters does not require CopyConstructible of either key_type or mapped_type if the dereferenced InputIterator returns a non-const rvalue pair<key_type, mapped_type>. Otherwise CopyConstructible is required for both key_type and mapped_type.
    ? Effects: Inserts x converted to value_type. For the second form, the iterator position is a hint pointing to where the search should start.

    ? Returns: An iterator that points to the element with key equivalent to the key of value_type(x).

    ? Complexity: Logarithmic in general, but amortized constant if x is inserted right before position.

    ? Remarks: These signatures shall not participate in overload resolution unless P is implicitly convertible to value_type.

Date: 2010-10-29.22:58:00

[ The submitter suggests: Add the same Remarks clause to [map.modifiers] and [multimap.modifiers]. ]

Date: 2010-10-14.00:00:00

In [unord.map.modifiers], the signature:

template <class P>
    pair<iterator, bool> insert(P&& obj);

now has an added Remarks paragraph:

Remarks: This signature shall not participate in overload resolution unless P is implicitly convertible to value_type.

The same is true for unordered_multimap.

But neither map nor multimap have this constraint, even though it is a Good Thing(TM) in those cases as well.

History
Date User Action Args
2014-02-20 13:20:35adminsetstatus: wp -> c++14
2012-11-03 04:16:46adminsetmessages: + msg6258
2012-10-25 12:46:45adminsetstatus: voting -> wp
2012-10-16 15:35:12adminsetstatus: ready -> voting
2012-02-12 18:36:43adminsetmessages: + msg5993
2012-02-12 18:36:43adminsetstatus: review -> ready
2011-11-25 22:10:58adminsetmessages: + msg5903
2011-08-18 17:19:16adminsetstatus: open -> review
2011-08-16 23:35:18adminsetmessages: + msg5845
2011-08-16 23:35:18adminsetstatus: review -> open
2011-03-24 16:58:37adminsetstatus: open -> review
2010-11-13 23:03:59adminsetmessages: + msg5361
2010-11-13 23:03:59adminsetstatus: new -> open
2010-10-29 22:58:00adminsetmessages: + msg5198
2010-10-29 22:58:00adminsetmessages: + msg5197
2010-10-29 14:46:33adminsetmessages: + msg5193
2010-10-14 00:00:00admincreate