2469. Wrong specification of Requires clause of operator[] for map and unordered_map

Section: 23.4.3.3 [map.access], 23.5.3.3 [unord.map.elem] Status: C++17 Submitter: Tomasz Kamiński Opened: 2015-01-21 Last modified: 2017-07-30

Priority: 3

View all other issues in [map.access].

View all issues with C++17 status.

Discussion:

The "Requires:" clause for the operator[] for the unordered_map and map, are defining separate requirements for insertability into container of mapped_type and key_type.

23.4.3.3 [map.access] p2: // T& operator[](const key_type& x);

Requires: key_type shall be CopyInsertable and mapped_type shall be DefaultInsertable into *this.

23.4.3.3 [map.access] p6: // T& operator[](key_type&& x)

Requires: mapped_type shall be DefaultInsertable into *this.

23.5.3.3 [unord.map.elem] p1: // mapped_type& operator[](const key_type& k); mapped_type& operator[](key_type&& k);

Requires: mapped_type shall be DefaultInsertable into *this. For the first operator, key_type shall be CopyInsertable into *this. For the second operator, key_type shall be MoveConstructible.

Definition of the appropriate requirements: 23.2.2 [container.requirements.general] p15.

T is DefaultInsertable into X means that the following expression is well-formed: //p15.1

allocator_traits<A>::construct(m, p)

T is MoveInsertable into X means that the following expression is well-formed: //p15.3

allocator_traits<A>::construct(m, p, rv)

T is CopyInsertable into X means that, in addition to T being MoveInsertable into X, the following expression is well-formed: //p15.4

allocator_traits<A>::construct(m, p, v)

In the context of above definition the requirement "key_type shall be CopyInsertable into *this" would mean that the key element of the pair<const key_type, mapped_type> (value_type of the map) should be constructed using separate call to the construct method, the same applies for the mapped_type. Such behavior is explicitly prohibited by 23.2.2 [container.requirements.general] p3.

For the components affected by this sub-clause that declare an allocator_type, objects stored in these components shall be constructed using the allocator_traits<allocator_type>::construct function and destroyed using the allocator_traits<allocator_type>::destroy function (20.7.8.2). These functions are called only for the container's element type, not for internal types used by the container.

It clearly states that element_type of the map, must be constructed using allocator for value type, which disallows using of separate construction of first and second element, regardless of the fact if it can be actually performed without causing undefined behavior.

That means that the MoveInsertable and similar requirements may only be expressed in terms of value_type, not its members types.

[2015-02 Cologne]

This issue is related to 2464.

GR: Effects should say "returns ...". DK: Or just have a Returns clause? MC: A Returns clause is a directive to implementers.

TK/DK: This PR fails to address the requirements about which it complained in the first place. DK: I can reword this. TK can help.

[2015-03-29, Daniel provides improved wording]

The revised wording fixes the proper usage of the magic "Equivalent to" wording, which automatically induces Requires:, Returns:, and Complexity: elements (and possibly more). This allows us to strike all the remaining elements, because they fall out from the semantics of the wording defined by 2464. In particular it is important to realize that the wording form

value_type shall be EmplaceConstructible into map from piecewise_construct, forward_as_tuple(k), forward_as_tuple(forward<Args>(args)...)

degenerates for the empty pack expansion args to:

value_type shall be EmplaceConstructible into map from piecewise_construct, forward_as_tuple(k), forward_as_tuple()

which again means that such a pair construction (assuming std::allocator) would copy k into member first and would value-initialize member second.

Previous resolution [SUPERSEDED]:

This wording is relative to N4296.

Accept resolution of the issue issue 2464 and define operator[] as follows (This would also address issue 2274):

1. Change 23.4.3.3 [map.access] as indicated:

   T& operator[](const key_type& x);
   

   -1- Effects: If there is no key equivalent to x in the map, inserts value_type(x, T()) into the mapEquivalent to: try_emplace(x).first->second.

   […]

   T& operator[](key_type&& x);
   

   -5- Effects: If there is no key equivalent to x in the map, inserts value_type(std::move(x), T()) into the mapEquivalent to: try_emplace(move(x)).first->second.

2. Change 23.5.3.3 [unord.map.elem] as indicated:

   mapped_type& operator[](const key_type& k);
   mapped_type& operator[](key_type&& k);
   

   […]

   -2- Effects: If the unordered_map does not already contain an element whose key is equivalent to k, the first operator inserts the value value_type(k, mapped_type()) and the second operator inserts the value value_type(std::move(k), mapped_type())For the first operator, equivalent to: try_emplace(k).first->second; for the second operator, equivalent to: try_emplace(move(k)).first->second.

Previous resolution [SUPERSEDED]:

This wording is relative to N4296.

Accept resolution of the issue issue 2464 and define operator[] as follows (This would also address issue 2274):

1. Change 23.4.3.3 [map.access] as indicated:

   T& operator[](const key_type& x);
   

   -1- Effects: If there is no key equivalent to x in the map, inserts value_type(x, T()) into the map.Equivalent to: return try_emplace(x).first->second;

   -2- Requires: key_type shall be CopyInsertable and mapped_type shall be DefaultInsertable into *this.

   -3- Returns: A reference to the mapped_type corresponding to x in *this.

   -4- Complexity: Logarithmic.

   T& operator[](key_type&& x);
   

   -5- Effects: If there is no key equivalent to x in the map, inserts value_type(std::move(x), T()) into the map.Equivalent to: return try_emplace(move(x)).first->second;

   -6- Requires: mapped_type shall be DefaultInsertable into *this.

   -7- Returns: A reference to the mapped_type corresponding to x in *this.

   -8- Complexity: Logarithmic.

2. Change 23.5.3.3 [unord.map.elem] as indicated:

   mapped_type& operator[](const key_type& k);
   mapped_type& operator[](key_type&& k);
   

   -1- Requires: mapped_type shall be DefaultInsertable into *this. For the first operator, key_type shall be CopyInsertable into *this. For the second operator, key_type shall be MoveConstructible.

   -2- Effects: If the unordered_map does not already contain an element whose key is equivalent to k, the first operator inserts the value value_type(k, mapped_type()) and the second operator inserts the value value_type(std::move(k), mapped_type())For the first operator, equivalent to:

    
   return try_emplace(k).first->second;
   

   for the second operator, equivalent to:

   return try_emplace(move(k)).first->second;
   

   -3- Returns: A reference to x.second, where x is the (unique) element whose key is equivalent to k.

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

Proposed resolution:

This wording is relative to N4431.

Accept resolution of the issue issue 2464 and define operator[] as follows (This would also address issue 2274):

1. Change 23.4.3.3 [map.access] as indicated:

   T& operator[](const key_type& x);
   

   -1- Effects: If there is no key equivalent to x in the map, inserts value_type(x, T()) into the map.Equivalent to: return try_emplace(x).first->second;

   -2- Requires: key_type shall be CopyInsertable and mapped_type shall be DefaultInsertable into *this.

   -3- Returns: A reference to the mapped_type corresponding to x in *this.

   -4- Complexity: Logarithmic.

   T& operator[](key_type&& x);
   

   -5- Effects: If there is no key equivalent to x in the map, inserts value_type(std::move(x), T()) into the map.Equivalent to: return try_emplace(move(x)).first->second;

   -6- Requires: mapped_type shall be DefaultInsertable into *this.

   -7- Returns: A reference to the mapped_type corresponding to x in *this.

   -8- Complexity: Logarithmic.

2. Change 23.5.3.3 [unord.map.elem] as indicated:

   mapped_type& operator[](const key_type& k);
   mapped_type& operator[](key_type&& k);
   

   -1- Requires: mapped_type shall be DefaultInsertable into *this. For the first operator, key_type shall be CopyInsertable into *this. For the second operator, key_type shall be MoveConstructible.

   -2- Effects: Equivalent to return try_emplace(k).first->second;If the unordered_map does not already contain an element whose key is equivalent to k, the first operator inserts the value value_type(k, mapped_type()) and the second operator inserts the value value_type(std::move(k), mapped_type())

   -3- Returns: A reference to x.second, where x is the (unique) element whose key is equivalent to k.

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

   mapped_type& operator[](key_type&& k);
   

   -?- Effects: Equivalent to return try_emplace(move(k)).first->second;