Movatterモバイル変換

This page is a snapshot from the LWG issues list, see theLibrary Active Issues List for more information and the meaning ofC++14 status.

2005.unordered_map::insert(T&&) protection should apply tomap too

Section: 23.4.3.4[map.modifiers], 23.4.4.3[multimap.modifiers], 23.5.3.4[unord.map.modifiers], 23.5.4.3[unord.multimap.modifiers]Status:C++14Submitter: P.J. PlaugerOpened: 2010-10-14Last modified: 2016-01-28

Priority:Not Prioritized

View all otherissues in [map.modifiers].

View all issues withC++14 status.

Discussion:

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 unlessPis implicitly convertible tovalue_type.

The same is true forunordered_multimap.

But neithermap normultimap have this constraint, even though it is aGood Thing(TM) in those cases as well.

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

[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 Requiresand an Effects element; third, the reference totuple is incorrect (noticed by Paolo Carlini);fourth, it refers to some non-existingInputIterator parameter relevant for a completely differentoverload; 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 forthe corresponding unordered containers. Unfortunately it has some redundancy over Table 99, but I didnot remove the specification because of the more general template parameterP - the Table 99 requirements apply only for an argumentidentical tovalue_type.

Daniel's Proposed resolution (not current):

1. Change 23.4.3.4[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);

   1Requires:P shall be convertible tovalue_type is constructible fromstd::forward<P>(x)..

   IfP is instantiated as a reference type, then the argumentx is copied from. Otherwisex is consideredto be an rvalue as it is converted tovalue_type and inserted into the map. Specifically, insuch casesCopyConstructible is not required ofkey_type ormapped_type unless the conversionfromP specifically requires it (e.g., ifP is atuple<const key_type, mapped_type>, thenkey_typemust beCopyConstructible). The signature takingInputIterator parameters does not requireCopyConstructible of eitherkey_type ormapped_type if the dereferencedInputIterator returns anon-const rvaluepair<key_type,mapped_type>. OtherwiseCopyConstructible is required for bothkey_type andmapped_type.
   ?Effects: Insertsx converted tovalue_type if and only if there is no element in the container withkey equivalent to the key ofvalue_type(x). For the second form, the iteratorposition is a hint pointing to where thesearch should start.

   ?Returns: For the first form, thebool component of the returnedpair 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 ofvalue_type(x).

   ?Complexity: Logarithmic in general, but amortized constant ifx is inserted right beforeposition.

   ?Remarks: These signatures shall not participate in overload resolution unlessP is implicitly convertible tovalue_type.

2. Change 23.4.4.3[multimap.modifiers] around p. 1 as indicated:

   template <class P> iterator insert(P&& x);template <class P> iterator insert(const_iterator position, P&& x);

   1Requires:P shall be convertible tovalue_typeis constructible fromstd::forward<P>(x).

   IfP is instantiated as a reference type, then the argumentx is copied from. Otherwisex is considered to be an rvalue as it is converted tovalue_type and inserted into the map. Specifically, in such casesCopyConstructible is not required ofkey_type ormapped_type unless the conversion fromP specifically requires it (e.g., ifP is atuple<const key_type, mapped_type>, thenkey_type must beCopyConstructible). The signature takingInputIterator parameters does not requireCopyConstructible of eitherkey_type ormapped_type if the dereferencedInputIterator returns a non-const rvaluepair<key_type, mapped_type>. OtherwiseCopyConstructible is required for bothkey_type andmapped_type.
   ?Effects: Insertsx converted tovalue_type. For the second form, the iteratorposition is a hint pointing to where the search should start.

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

   ?Complexity: Logarithmic in general, but amortized constant ifx is inserted right beforeposition.

   ?Remarks: These signatures shall not participate in overload resolution unlessP is implicitly convertible tovalue_type.

[2010 Batavia:]

We needis_convertible, notis_constructible, both in ordered and unordered containers.

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

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

Unfortunately the template constraints expressed as "P is implicitly convertible tovalue_type"reject the intended effect to support move-only key types, which was the original intention whenthe library became move-enabled through the rvalue-reference proposals by Howard (This can clearly be deducedfrom existing carefully selected wording that emphasizes thatCopyConstructible is only requiredfor special situations involving lvalues or const rvalues as arguments). The root of the problem is basedon current core rules, where an "implicitly converted" value has copy-initialization semantics. Considera move-only key typeKM, some mapped typeT, and a source valuep of typeP equal tostd::pair<KM, T>, this is equivalent to:

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

Now 9.5[dcl.init] p16 b6 sb2 says that the effects of this heterogeneous copy-initialization (phas a different type thandest) are as-if a temporary of the target typestd::pair<const KM, T>is produced from the rvaluep of typeP (which is fine), and this temporary is used to initializedest. This second step cannot succeed, because we cannot move fromconst KM toconst KM. This means thatstd::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-initializationfromP tovalue_type, so imposing an implicit conversion is more than necessary. ThereforeI strongly recommend to reduce the "overload participation" constraint tostd::is_constructible<std::pair<const KM, T>, P>::value instead. This change is theonly change that has been performed to the previous proposed wording from Pablo shown below.

[2012, Kona]

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

[2012, Portland: applied to WP]

Proposed resolution:

1. Change 23.4.3.4[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);

   1Requires:P shall be convertible tovalue_type.

   IfP is instantiated as a reference type, then the argumentx is copied from. Otherwisex is consideredto be an rvalue as it is converted tovalue_type and inserted into the map. Specifically, insuch casesCopyConstructible is not required ofkey_type ormapped_type unless the conversionfromP specifically requires it (e.g., ifP is atuple<const key_type, mapped_type>, thenkey_typemust beCopyConstructible). The signature takingInputIterator parameters does not requireCopyConstructible of eitherkey_type ormapped_type if the dereferencedInputIterator returns anon-const rvaluepair<key_type,mapped_type>. OtherwiseCopyConstructible is required for bothkey_type andmapped_type.
   ?Effects: The first form is equivalent toreturn emplace(std::forward<P>(x)).The second form is equivalent toreturn emplace_hint(position, std::forward<P>(x)).

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

2. Change 23.4.4.3[multimap.modifiers] around p. 1 as indicated:

   template <class P> iterator insert(P&& x);template <class P> iterator insert(const_iterator position, P&& x);

   1Requires:P shall be convertible tovalue_type.

   IfP is instantiated as a reference type, then the argumentx is copied from. Otherwisex is considered to be an rvalue as it is converted tovalue_type and inserted into the map. Specifically, in such casesCopyConstructible is not required ofkey_type ormapped_type unless the conversion fromP specifically requires it (e.g., ifP is atuple<const key_type, mapped_type>, thenkey_type must beCopyConstructible). The signature takingInputIterator parameters does not requireCopyConstructible of eitherkey_type ormapped_type if the dereferencedInputIterator returns a non-const rvaluepair<key_type, mapped_type>. OtherwiseCopyConstructible is required for bothkey_type andmapped_type.
   ?Effects: The first form is equivalent toreturn emplace(std::forward<P>(x)).The second form is equivalent toreturn emplace_hint(position, std::forward<P>(x)).

   ?Remarks: These signatures shall not participate in overload resolution unlessstd::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);

   1Requires:value_type is constructible fromstd::forward<P>(obj).

   2Effects:equivalent toreturn emplace(std::forward<P>(obj)).Inserts obj converted tovalue_type if and only if there is no element in the container withkey equivalent to the key ofvalue_type(obj).

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

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

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

   template <class P>iterator insert(const_iterator hint, P&& obj);

   6Requires:value_type is constructible fromstd::forward<P>(obj).

   7?Effects:equivalent toreturn emplace_hint(hint, std::forward<P>(obj)).Inserts obj converted tovalue_type if and only if there is no element in the container withkey equivalent to the key ofvalue_type(obj). The iterator hint is a hint pointing to where thesearch should start.

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

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

   10?Remarks: This signature shall not participate in overload resolution unlessP is implicitly convertible tovalue_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);

   1Requires:value_type is constructible fromstd::forward<P>(obj).

   2Effects:equivalent toreturn emplace(std::forward<P>(obj)).Inserts obj converted tovalue_type.

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

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

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

   template <class P>iterator insert(const_iterator hint, P&& obj);

   6Requires:value_type is constructible fromstd::forward<P>(obj).

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

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

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

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