P2077R3
Heterogeneous erasure overloads for associative containers

1. Motivation

[N3657] and [P0919R0] introduced heterogeneous lookup support for ordered and unordered associative containers in C++ Standard Library. 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 no heterogeneous erase and extract overloads.

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
    // some other actions with iterator
    m.erase(lookup_str); // causes implicit conversion
}

Function foo accepts a reference to the std::map<std::string, int> object. A comparator for the map is std::less<void>, which provides is_transparent valid qualified-id, so the std::map allows using heterogeneous overloads with Key template parameter for lookup functions, such as find, upped_bound, equal_range, etc.

In the example above, the m.find(lookup_str) call does not create a temporary object of the std::string to perform a lookup. But the m.erase(lookup_str) call causes implicit conversion from const char* to std::string. The allocation and construction (as well as subsequent destruction and deallocation) of the temporary object of std::string or any custom object can be quite expensive and reduce the program performance.

Erasure from the STL associative containers with the key instance of the type that is different from key_type is possible with the following code snippet:

auto eq_range = container.equal_range(key);
auto previous_size = container.size();
container.erase(eq_range.first, eq_range.second);
auto erased_count = container.size() - previous_size;

where std::is_same_v<decltype(key), key_type> is false.

erased_count determines the count of erased items and container is either:

• An ordered associative container in which key_compare::is_transparent is a valid qualified-id.

• An unordered associative container in which hasher::is_transparent and key_equal::is_transparent are valid qualified-ids.

The code above is a valid alternative for the heterogeneous erase overload. But heterogeneous erase would allow to do the same things more efficiently, without traversing the interval [eq_range.first, eq_range.second) twice (the first time to determine the equal range and the second time for erasure). It adds a performance penalty for the containers with non-unique keys (like std::multimap, std::multiset, etc.) where the number of elements with the same key can be quite large.

Note: § 1 Motivation, § 3.1 Why K&& rather than const K& and § 4 Performance evaluation contain examples for the erase method. But the problems and benefits are similar for both erase and extract member functions.

2. Prior Work

Possibility to add heterogeneous erase overload was reviewed in the [N3465]. But it was found that heterogeneous erase brakes backward compatibility and causes wrong overload resolution for the case when an iterator is passed as the argument. The iterator type is implicitly converted into const_iterator and the following overload of the erase method is called:

iterator erase( const_iterator pos )

If there was the following heterogeneous overload of the erase method:

template <class K>
size_type erase( const K& x );

template overload would be chosen in C++14 when an iterator object passed as the argument. So, it can cause the wrong effect or compilation error for legacy code.

C++17 introduces a new overload for erase method, which accepts exactly an object of iterator type as an argument:

iterator erase( iterator pos )

This change intended to fix the ambiguity issue [LWG2059] in the erase method overloads (for key_type and for const_iterator) when a key_type object can be constructed from the iterator.

Adding the overload with the iterator argument solves the problem described above but overload with template K parameter still will be chosen when passing an object of a type, which is implicitly convertible to either iterator or const_iterator that is not what user might expect.

3. Proposal overview

We analyzed the prior work and basing on that we propose to add heterogeneous overloads for erase and extract methods in std::map, std::multimap, std::set, std::multiset, std::unordered_map, std::unordered_multimap, std::unordered_set and std::unordered_multiset:

template <class K>
size_type erase( K&& x );

and

template <class K>
node_type extract( K&& x );

To maintain backward compatibility and avoid wrong overload resolution or compilation errors these overloads should impose extra restrictions on the type K.

For ordered associative containers these overloads should participate in overload resolution only if all the following statements are true:

1. Qualified-id Compare::is_transparent is valid and denotes a type.

2. The type K&& is not convertible to the iterator.

3. The type K&& is not convertible to the const_iterator.

where Compare is a type of comparator passed to an ordered container.

For unordered associative containers these overloads should participate in overload resolution if all the following statements are true:

1. Qualified-id Hash::is_transparent is valid and denotes a type.

2. Qualified-id Pred::is_transparent is valid and denotes a type.

3. The type K&& is not convertible to the iterator.

4. The type K&& is not convertible to the const_iterator.

where Hash and Pred are types of hash function and key equality predicate passed to an unordered container respectively.

3.1. Why K&& rather than const K&

Initially we considered making an interface for heterogeneous erasure methods consistent with heterogeneous lookup:

template <class K>
size_type erase( const K& x );

and adding the following constraints:

• For ordered associative containers: qualified-id Compare::is_transparent is valid and denotes a type.
  For unordered associative containers: qualified-ids Hash::is_transparent and Pred::is_transparent are valid and denote types and

• The type K is not convertible to the iterator and

• The type K is not convertible to the const_iterator.

The feedback from LEWG was to investigate convertability of all value categories of K (K&, const K&, K&&, const K&&) to iterator or const_iterator, similar to what std::optional does for constructors.

During the investigation we defined the heterogeneous erasuse with the const K& function parameter:

template <class K>
size_type erase( const K& x );

with the following constraints:

• For ordered associative containers: qualified-id Compare::is_transparent is valid and denotes a type.
  For unordered associative containers: qualified-ids Hash::is_transparent and Pred::is_transparent are valid and denote types and

• The type K& is not convertible to either iterator and const_iterator and

• The type const K& is not convertible to either iterator and const_iterator and

• The type K&& is not convertible to either iterator and const_iterator and

• The type const K&& is not convertible to either iterator and const_iterator.

Unfortunately, with that definition we discovered the following issue.

Consider map_type as std::map for which Compare::is_transparent is valid and denotes a type.

struct HeterogeneousKey {
    HeterogeneousKey() { /*...*/ }
    operator map_type::iterator() && { /*Some conversion logic*/ }

    // Comparison operations with map_type::key_type
};

void foo() {
    map_type m;
    HeterogeneousKey key;

    m.erase(key);
}

The code above fails to compile because:

1. For heterogeneous erasure overload, the type K is deduced as HeterogeneousKey, for which std::is_convertible_v<HeterogeneousKey&&, iterator> is true and hence the heterogeneous erasure does not participate in overload resolution.

2. An object key passed to erase method cannot be converted to the iterator due to rvalue ref-qualifier for the conversion operator.

Therefore, the matching overload for the call m.erase(key) is not found.

The heterogeneous erasure overload should participate in overload resolution when non-template overloads is not matched. With the current API we lose the information about the value category of K due to template argument deduction from const K& function parameter. Therefore, we cannot define constraints over K for the arbitrary case.

To propagate the information about the value category of K we define the function parameter for heterogeneous erasure as forwarding reference. The interface is

template <class K>
size_type erase( K&& x );

with the following constraints:

• For ordered associative containers: qualified-id Compare::is_transparent is valid and denotes a type.
  For unordered associative containers: qualified-ids Hash::is_transparent and Pred::is_transparent are valid and denote types and

• The type K&& is not convertible to the iterator.

• The type K&& is not convertible to the const_iterator.

This overload does not participate in overload resolution only if the function argument of the particular value category is convertible to the iterator or const_iterator. The example above is compiled and the heterogeneous erase overload is called for m.erase(key) line.

Note: the example is shown for std::map but the issue is relevant for all associative containers.

4. Performance evaluation

We estimated the performance impact on two synthetic benchmarks:

• Erase all elements consistently from the std::unordered_map<std::string, int>, filled by 10000 values with unique keys. Size of each std::string key is 1000.

• Erase all elements from the std::unordered_multimap<std::string, int> filled by 10000 values with duplicated keys. Size of each std::string key is 1000.

To do that we have implemented heterogeneous erase method for std::unordered_map and std::unordered_multimap on the base of LLVM Standard Library implementation.

We have compared the performance of three possible erasure algorithms:

• Erasure by key_type object.

• Erasure by the pair of iterators, obtained by the heterogeneous equal_range.

• Heterogeneous erasure with the std::string_view as an argument.

The benchmark for std::unordered_map shows that the erasure by the pair of iterators (as well as heterogeneous erasure) increases performance by ~20%.

The benchmark for std::unordered_multimap shows the same performance increase for erasure by the pair of iterators and an additional performance increase by ~10% for heterogeneous erasure (due to double traversal of equal_range).

To do the additional analysis with different memory allocation source we took an open-source application pmemkv. It is an embedded key/value data storage designed for emergent persistent memory. pmemkv has several storage engines optimized for different use cases. For the analysis we chose vsmap engine that is built on std::map data structure with allocator for persistent memory from the memkind library. std::basic_string with the memkind allocator was used as a key and value type.

using storage_type = std::basic_string<char, std::char_traits<char>,
                                       libmemkind::pmem::allocator<char>>;
using key_type = storage_type;
using mapped_type = storage_type;
using map_allocator_type = libmemkind::pmem::allocator<std::pair<const key_type,
                                                                 mapped_type>>;
using map_type = std::map<key_type, mapped_type, std::less<void>,
                          std::scoped_allocator_adaptor<map_allocator_type>>;

Initial implementation of remove method of vsmap engine was the following:

status vsmap::remove( std::string_view key ) {
    std::size_t erased = c.erase(key_type(key.data(), key.size(), a));
    return (erased == 1) ? status::OK : status::NOT_FOUND;
}

The initial implementation explicitly creates temporary object of key_type when erase method is called. To estimate performance impact of the heterogeneous erase overload we re-designed remove operation of the vsmap engine in the following way:

status vsmap::remove( std::string_view key ) {
    auto it = c.find(key);
    if (it != c.end()) {
        c.erase(it);
        return status::OK;
    }
    return status::NOT_FOUND;
}

To understand the performance impact we used pmemkv utility. We run deleterandom benchmark on prefilled storage and measured throughput as a number of operations per second. We executed the test with different key sizes (16 bytes, 200 bytes, 1024 bytes). The chart below shows performance increase, comparing to initial implementation, for all tests. The throughput of the remove operation increased up to 9x for the 1024 bytes key.

5. Formal wording

Below, substitute the � character with a number the editor finds appropriate for the table, paragraph, section or sub-section.

5.1. Modify paragraph � in [associative.reqmts.general]

[...]

�  In Table �,

[...]

�    — ke is a value such that a is partitioned with respect to c(r, ke) and !c(ke, r),
        with c(r, ke) implying !c(ke, r).

�    — kx is a value such that
        — a is partitioned with respect to c(r, rx) and !c(kx, r),
          with c(r, kx) implying !c(kx, r)
        — kx is not convertible to either iterator or const_iterator

[...]

5.2. Modify [tab:container.assoc.req]

Table �: Associative container requirements (in addition to container) [tab:container.assoc.req]

Expression	Return type	Assertion/ note/ pre-/ post-condition	Complexity
[...]
a.extract(k)	node_type	Effects: Removes the first element in the container with key equivalent to k. Returns: A node_type owning the element if found, otherwise an empty node_type.	log(a.size())
a_tran.extract(kx)	node_type	Effects: Removes the first element in the container with key r such that !c(r, kx) && !c(kx, r). Returns: A node_type owning the element if found, otherwise an empty node_type.	log(a_tran.size())
[...]
a.erase(k)	size_type	Effects: Erases all elements in the container with key equivalent to k. Returns: The number of erased elements.	log(a.size()) + a.count(k)
a_tran.erase(kx)	size_type	Effects: Erases all elements in the container with key r such that !c(r, kx) && !c(kx, r). Returns: The number of erased elements.	log(a_tran.size()) + a_tran.count(kx)
[...]

5.3. Modify paragraph � in [associative.reqmts.general]

[...]

The member function templates find, count, contains, lower_bound, upper_bound, and equal_range , erase, and extract shall not participate in overload resolution unless the qualified-id Compare::is_transparent is valid and denotes a type (�). Additionally, the member function templates erase and extract shall not participate in overload resolution if is_convertible_v<K&&, iterator> || is_convertible_v<K&&, const_iterator> is true, where K is the type substituted as the first template argument.

[...]

5.4. Modify class template map synopsis [map.overview]

[...]

node_type extract(const_iterator position);
node_type extract(const key_type& x);

template<class K> node_type extract(K&& x);

[...]

iterator erase(iterator position);
iterator erase(const_iterator position);
size_type erase(const key_type& x);

template<class K> size_type erase(K&& x);

[...]

5.5. Modify class template multimap synopsis [multimap.overview]

[...]

node_type extract(const_iterator position);
node_type extract(const key_type& x);

template <class K> node_type extract(K&& x);

[...]

iterator erase(iterator position);
iterator erase(const_iterator position);
size_type erase(const key_type& x);

template <class K> size_type erase(K&& x);

[...]

5.6. Modify class template set synopsis [set.overview]

[...]

node_type extract(const_iterator position);
node_type extract(const key_type& x);

template <class K> node_type extract(K&& x);

[...]

iterator erase(iterator position);
iterator erase(const_iterator position);
size_type erase(const key_type& x);

template <class K> size_type erase(K&& x);

[...]

5.7. Modify class template multiset synopsis [multiset.overview]

[...]

node_type extract(const_iterator position);
node_type extract(const key_type& x);

template <class K> node_type extract(K&& x);

[...]

iterator erase(iterator position);
iterator erase(const_iterator position);
size_type erase(const key_type& x);

template <class K> size_type erase(K&& x);

[...]

5.8. Modify paragraph � in [unord.req.general]

[...]

�  In Table �,

[...]

�  — ke is a value such that
�      — eq(r1, ke) == eq(ke, r1)
�      — hf(r1) == hf(ke) if eq(r1, ke) is true, and
�      — (eq(r1, ke) && eq(r1, r2)) == eq(r2, ke)
      where r1 and r2 are keys of elements in a_tran,

�  — kx is a value such that
�      — eq(r1, kx) == eq(kx, r1)
�      — hf(r1) == hf(kx) if eq(r1, kx) is true
�      — (eq(r1, kx) && eq(r1, r2)) == eq(r2, kx), and
�      — kx is not convertible to either iterator or const_iterator
      where r1 and r2 are keys of elements in a_tran,

[...]

5.9. Modify [tab:container.hash.req]

Table �: Unordered associative container requirements (in addition to container) [tab:container.hash.req]

Expression	Return type	Assertion/ note/ pre-/ post-condition	Complexity
[...]
a.extract(k)	node_type	Effects: Removes an element in the container with key equivalent to k. Returns: A node_type owning the element if found, otherwise an empty node_type.	Average case O(1), worst case O(a.size()).
a_tran.extract(kx)	node_type	Effects: Removes an element in the container with key equivalent to kx. Returns: A node_type owning the element if found, otherwise an empty node_type.	Average case O(1), worst case O(a_tran.size()).
[...]
a.erase(k)	size_type	Effects: Erases all elements with key equivalent to k. Returns: The number of elements erased.	Average case O(a.count(k)), worst case O(a.size()).
a_tran.erase(kx)	size_type	Effects: Erases all elements with key equivalent to kx. Returns: The number of elements erased.	Average case O(a_tran.count(kx)), worst case O(a_tran.size()).
[...]

5.10. Modify paragraph � in [unord.req.general]

[...]

The member function templates find, count, equal_range, and contains , erase, and extract shall not participate in overload resolution unless the qualified-ids Pred::is_transparent and Hash::is_transparent are both valid and denote types (�). Additionally, the member function templates erase and extract shall not participate in overload resolution if is_convertible_v<K&&, iterator> || is_convertible_v<K&&, const_iterator> is true, where K is the type substituted as the first template argument.

[...]

5.11. Modify class template unordered_map synopsis [unord.map.overview]

[...]

node_type extract(const_iterator position);
node_type extract(const key_type& x);

template <class K> node_type extract(K&& x);

[...]

iterator erase(iterator position);
iterator erase(const_iterator position);
size_type erase(const key_type& x);

template <class K> size_type erase(K&& x);

[...]

5.12. Modify class template unordered_multimap synopsis [unord.multimap.overview]

[...]

node_type extract(const_iterator position);
node_type extract(const key_type& x);

template <class K> node_type extract(K&& x);

[...]

iterator erase(iterator position);
iterator erase(const_iterator position);
size_type erase(const key_type& x);

template <class K> size_type erase(K&& x);

[...]

5.13. Modify [unord.set.overview] class template unordered_set synopsis

[...]

node_type extract(const_iterator position);
node_type extract(const key_type& x);

template <class K> node_type extract(K&& x);

[...]

iterator erase(iterator position);
iterator erase(const_iterator position);
size_type erase(const key_type& x);

template <class K> size_type erase(K&& x);

[...]

5.14. Modify class template unordered_multiset synopsis [unord.multiset.overview]

[...]

node_type extract(const_iterator position);
node_type extract(const key_type& x);

template <class K> node_type extract(K&& x);

[...]

iterator erase(iterator position);
iterator erase(const_iterator position);
size_type erase(const key_type& x);

template <class K> size_type erase(K&& x);

[...]

5.15. Add feature test macro to [version.syn]

[...]

#define __cpp_lib_as_const                             20����L  // also in utility>

#define __cpp_lib_associative_heterogeneous_erasure    20����L
   // also in <map>, <set>, <unordered_map>, unordered_set>

#define __cpp_lib_assume_aligned                       20����L  // also in memory>

[...]

5.16. Add paragraph � into [diff.cpp20]

[...]

  C.�        C++ and ISO C++ 2020

[...]

 C.�.�      [containers]: containers library                [diff.cpp20.containers]

�  Affected subclauses: [associative.reqmts], [unord.req]

    Change: Heterogeneous erase and extract overloads for associative containers.

    Rationale: Improve efficiency of erasing elements from associative containers

    Effect on original feature: Valid C++ 2020 code may fail to compile in
this revision of C++:
       
       struct B {
           auto operator<=>(const B&) const = default;
       };

       struct D : private B {
           void f(std::set<B, std::less<>>& s) {
               s.erase(*this); // ill formed; previously well-formed
           }
       };
       

[...]

6. Revision history

6.1. R2 ➡ R3

Changed wording to apply feedback from LWG (2021-06-25).

6.2. R1 ➡ R2

• Changed interface of heterogeneous erasure overloads from const K& to K&&. For more information see § 3.1 Why K&& rather than const K&.

• Aligned wording with the standard (fonts, capital letters, etc.)

6.3. R0 ➡ R1

Addressed feedback from the presentation on LEWG-I to align wording and approach with [P1690R1].