This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of C++17 status.

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

Section: 22.4.4.3 [map.access], 22.5.4.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`.

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

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

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

Requires: `mapped_type` shall be `DefaultInsertable` into `*this`.

22.5.4.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: 22.2.1 [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 22.2.1 [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 22.4.4.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: `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 map Equivalent to: `try_emplace(move(x)).first->second`.

> 2. Change 22.5.4.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 22.4.4.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 22.5.4.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 22.4.4.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 22.5.4.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;`