1. Motivation
[N3657] and [P0919R0] introduced heterogeneous lookup support for ordered and unordered
associative containers in C++ Standard Library. [P2077R2] proposed heterogeneous erasure overloads.
As a result, a temporary key object is not created when a different (but comparable) type is provided as a key to the member function.
But there are still no heterogeneous overloads for methods such as
,
and others.
Consider the following example:
void foo ( std :: map < std :: string , int , std :: less < void >>& m ) { const char * lookup_str = "Lookup_str" ; auto it = m . find ( lookup_str ); // matches to template overload // ... auto result = m . insert_or_assign ( lookup_str , 1 ); // no heterogeneous alternative }
Function
accepts a reference to the
object. A
comparator for the map is
, which provides
valid
qualified-id, so the
allows using heterogeneous overloads with
template
parameter for lookup functions, such as
,
,
, etc.
In the example above, the
call does not create a temporary object of
the
to perform a lookup. But the
call causes implicit
conversion from
to
even if the insertion will not take place.
The allocation and construction (as well as subsequent destruction and deallocation) of the temporary object of
or any custom object might be quite expensive and reduce the program performance.
All the proposed APIs in this paper allow to avoid mentioned performance penalty.
2. Prior work
Heterogeneous lookup overloads for ordered and unordered associative containers were added into C++ standard. For example:
template < typename K > iterator find ( const K & x );
The corresponding overloads were added for
,
,
,
and
member functions.
[P2077R2] proposed heterogeneous erasure overloads for ordered and unordered associative containers:
template < typename K > size_type erase ( K && x ); template < typename K > node_type extract ( K && x );
Constraints:
-
qualified-id
is valid and denotes a type for ordered associative containersCompare :: is_transparent -
qualified-ids
andHash :: is_transparent
are valid and denote types for unordered associative containersPred :: is_transparent
where
is a type of comparator passed to an ordered container,
and
are types of hash function and key equality
predicate passed to an unordered container respectively.
3. Proposal overview
We propose to add heterogeneous overloads for the following member functions:
-
ininsert
andstd :: set std :: unordered_set -
,insert_or_assign
,try_emplace
,operator []
inat
andstd :: map std :: unordered_map -
inbucket
,std :: unordered_set
,std :: unordered_map
andstd :: unordered_multiset std :: unordered_multimap
3.1. try_emplace
We propose the following API (
and
):
template < typename K , typename ... Args > std :: pair < iterator , bool > try_emplace ( K && k , Args && ... args ); template < typename K , typename ... Args > iterator try_emplace ( const_iterator hint , K && k , Args && ... args );
Effects: If the map already contains an element whose key compares equivalent with
, there is no effect. Otherwise,
inserts an object of type
constructed with
.
Constraints:
-
For ordered associative containers: qualified-id
is valid and denotes a type For unordered associative containers: qualified-idsCompare :: is_transparent
andHash :: is_transparent
are valid and denote typesPred :: is_transparent -
isstd :: is_constructible_v < value_type , std :: piecewise_construct_t , std :: tuple < K &&> , std :: tuple < Args && ... >> true
. -
andstd :: is_convertible_v < K && , const_iterator >
are bothstd :: is_convertible_v < K && , iterator > false
.
Constraints 2 and 3 are introduced to maintain backward compatibility.
Constraint 2 makes homogeneous overload to be called when
is convertible to
but
is not constructible from
.
Constraint 3 makes homogeneous overload to be called when
is convertible to
or to
.
3.2. insert_or_assign
We propose the following API (
and
):
template < typename K , typename M > std :: pair < iterator , bool > insert_or_assign ( K && k , M && obj ); template < typename K , typename M > iterator insert_or_assign ( const_iterator hint , K && k , M && obj );
Effects: If the map already contains an element
whose key compares equivalent with
, assigns
to
.
Otherwise, inserts an object of type
constructed with
.
Constraints:
-
For ordered associative containers: qualified-id
is valid and denotes a type For unordered associative containers: qualified-idsCompare :: is_transparent
andHash :: is_transparent
are valid and denote typesPred :: is_transparent -
isstd :: is_constructible_v < value_type , K && , M &&> true
.
Backward compatibility problem in case of
convertibility to
or
will not take place
because the number of arguments is fixed - call with three arguments would always consider the overloads with
only.
3.3. operator []
We propose the following API (
and
):
template < typename K > mapped_type & operator []( K && k );
Effects: Equivalent to:
.
Constraints:
-
For ordered associative containers: qualified-id
is valid and denotes a type For unordered associative containers: qualified-idsCompare :: is_transparent
andHash :: is_transparent
are valid and denote typesPred :: is_transparent
We do not introduce the following constraint:
because
is used as an argument for
constructor anyway. We do not
consider the use-case when the
is convertible to
, but
is not constructible from
as important to maintain.
3.4. bucket
We propose the following API (
,
,
and
):
template < typename K > size_type bucket ( const K & k ) const ;
Returns: The index of the bucket in which elements with keys compared equivalent with
would be found, if any such element
existed.
Constraints:
-
For ordered associative containers: qualified-id
is valid and denotes a type For unordered associative containers: qualified-idsCompare :: is_transparent
andHash :: is_transparent
are valid and denote typesPred :: is_transparent
3.5. at
We propose the following API (
and
):
template < typename K > mapped_type & at ( const K & k ); template < typename K > const mapped_type & at ( const K & k ) const ;
Returns: A reference to the
corresponding to
in
.
Throws: An exception object of type
if no such element is present.
Constraints:
-
For ordered associative containers: qualified-id
is valid and denotes a type For unordered associative containers: qualified-idsCompare :: is_transparent
andHash :: is_transparent
are valid and denote typesPred :: is_transparent
3.6. insert
We considered to add heterogeneous overloads of
for all associative containers, but found the applicability only for
and
with the following API:
template < typename K > std :: pair < iterator , bool > insert ( K && k ); template < typename K > iterator insert ( const_iterator hint , K && k );
Effects: If the set already contains an element which compares equivalent with
, there is no effect. Otherwise,
inserts an object constructed with
into the set.
Constraints:
-
For ordered associative containers: qualified-id
is valid and denotes a type For unordered associative containers: qualified-idsCompare :: is_transparent
andHash :: is_transparent
are valid and denote typesPred :: is_transparent
We do not introduce the following constraint:
. because
is used as an argument for
constructor anyway. We do not
consider the use-case when the
is convertible to
, but
is not constructible from
as important to maintain.
Adding heterogeneous
overload makes no sence for associative containers with non-unique keys (
,
,
and
)
because the insertion will be successful in any case and the key would be always constracted. All additional overheads introduced by
can be mitigated by using
.
For
and
, heterogeneous insertion also makes no sence because
heterogeneous
covers the relevant use cases.
3.7. Proposed API summary
The proposed heterogeneous overloads for various methos are summarized in the table below:
Member function std::set std::multiset std::map std::multimap std::unordered_set std::unordered_multiset std::unordered_map std::unordered_multimap insert K&& Not applicable Not applicable Not applicable K&& Not applicable Not applicable Not applicable insert_or_assign Not available Not available K&& Not available Not available Not available K&& Not available try_emplace Not available Not available K&& Not available Not available Not available K&& Not available operator[] Not available Not available K&& Not available Not available Not available K&& Not available bucket Not available Not available Not available Not available const K& const K& const K& const K& at Not available Not available const K& Not available Not available Not available const K& const K&
4. Plans
-
Provide implementation experience results
-
Provide performance measurements
-
Prepare the wording