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.
operator[]
for map
and unordered_map
Section: 24.4.4.3 [map.access], 24.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
.
T& operator[](const key_type& x);
Requires: key_type
shall be CopyInsertable
and mapped_type
shall be DefaultInsertable
into *this
.
24.4.4.3 [map.access] p6: // T& operator[](key_type&& x)
Requires: mapped_type
shall be DefaultInsertable
into *this
.
24.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: 24.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 24.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 theallocator_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.
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(i).
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(i). In particular it is important to realize that the wording form
value_type
shall beEmplaceConstructible
intomap
frompiecewise_construct
,forward_as_tuple(k)
,forward_as_tuple(forward<Args>(args)...)
degenerates for the empty pack expansion args
to:
value_type
shall beEmplaceConstructible
intomap
frompiecewise_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(i) and define
operator[]
as follows (This would also address issue 2274(i)):
Change 24.4.4.3 [map.access] as indicated:
T& operator[](const key_type& x);-1- Effects:
[…]If there is no key equivalent toEquivalent to:x
in the map, insertsvalue_type(x, T())
into the maptry_emplace(x).first->second
.T& operator[](key_type&& x);-5- Effects:
If there is no key equivalent toEquivalent to:x
in the map, insertsvalue_type(std::move(x), T())
into the maptry_emplace(move(x)).first->second
.Change 24.5.4.3 [unord.map.elem] as indicated:
mapped_type& operator[](const key_type& k); mapped_type& operator[](key_type&& k);[…]
-2- Effects:If theFor the first operator, equivalent to:unordered_map
does not already contain an element whose key is equivalent tok
, the first operator inserts the valuevalue_type(k, mapped_type())
and the second operator inserts the valuevalue_type(std::move(k), mapped_type())
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(i) and define
operator[]
as follows (This would also address issue 2274(i)):
Change 24.4.4.3 [map.access] as indicated:
T& operator[](const key_type& x);-1- Effects:
If there is no key equivalent toEquivalent to:x
in the map, insertsvalue_type(x, T())
into the map.return try_emplace(x).first->second;
-2- Requires:key_type
shall beCopyInsertable
andmapped_type
shall beDefaultInsertable
into*this
.-3- Returns: A reference to themapped_type
corresponding tox
in*this
.-4- Complexity: Logarithmic.T& operator[](key_type&& x);-5- Effects:
If there is no key equivalent toEquivalent to:x
in the map, insertsvalue_type(std::move(x), T())
into the map.return try_emplace(move(x)).first->second;
-6- Requires:mapped_type
shall beDefaultInsertable
into*this
.-7- Returns: A reference to themapped_type
corresponding tox
in*this
.-8- Complexity: Logarithmic.Change 24.5.4.3 [unord.map.elem] as indicated:
mapped_type& operator[](const key_type& k); mapped_type& operator[](key_type&& k);-2- Effects:
-1- Requires:mapped_type
shall beDefaultInsertable
into*this
. For the first operator,key_type
shall beCopyInsertable
into*this
. For the second operator,key_type
shall beMoveConstructible
.If theFor the first operator, equivalent to:unordered_map
does not already contain an element whose key is equivalent tok
, the first operator inserts the valuevalue_type(k, mapped_type())
and the second operator inserts the valuevalue_type(std::move(k), mapped_type())
return try_emplace(k).first->second;for the second operator, equivalent to:
return try_emplace(move(k)).first->second;
-3- Returns: A reference tox.second
, wherex
is the (unique) element whose key is equivalent tok
.-4- Complexity: Average case 𝒪(1
), worst case 𝒪(size()
).
Proposed resolution:
This wording is relative to N4431.
Accept resolution of the issue issue 2464(i) and define operator[]
as follows
(This would also address issue 2274(i)):
Change 24.4.4.3 [map.access] as indicated:
T& operator[](const key_type& x);-1- Effects:
If there is no key equivalent toEquivalent to:x
in the map, insertsvalue_type(x, T())
into the map.return try_emplace(x).first->second;
-2- Requires:key_type
shall beCopyInsertable
andmapped_type
shall beDefaultInsertable
into*this
.-3- Returns: A reference to themapped_type
corresponding tox
in*this
.-4- Complexity: Logarithmic.T& operator[](key_type&& x);-5- Effects:
If there is no key equivalent toEquivalent to:x
in the map, insertsvalue_type(std::move(x), T())
into the map.return try_emplace(move(x)).first->second;
-6- Requires:mapped_type
shall beDefaultInsertable
into*this
.-7- Returns: A reference to themapped_type
corresponding tox
in*this
.-8- Complexity: Logarithmic.
Change 24.5.4.3 [unord.map.elem] as indicated:
mapped_type& operator[](const key_type& k);mapped_type& operator[](key_type&& k);-2- Effects: Equivalent to
-1- Requires:mapped_type
shall beDefaultInsertable
into*this
. For the first operator,key_type
shall beCopyInsertable
into*this
. For the second operator,key_type
shall beMoveConstructible
.return try_emplace(k).first->second;
If theunordered_map
does not already contain an element whose key is equivalent tok
, the first operator inserts the valuevalue_type(k, mapped_type())
and the second operator inserts the valuevalue_type(std::move(k), mapped_type())
-3- Returns: A reference tox.second
, wherex
is the (unique) element whose key is equivalent tok
.-4- Complexity: Average case 𝒪(1
), worst case 𝒪(size()
).mapped_type& operator[](key_type&& k);-?- Effects: Equivalent to
return try_emplace(move(k)).first->second;