Reapply "[libc++] Refactor key extraction for __hash_table and __tree (#154512)" #155565
+309
−352
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
…llvm#154512)" This reverts commit 72c04bb.
|
@llvm/pr-subscribers-libcxx @llvm/pr-subscribers-lldb Author: Nikolas Klauser (philnik777) ChangesThis reverts commit 72c04bb. Patch is 45.64 KiB, truncated to 20.00 KiB below, full version: https://github.com/llvm/llvm-project/pull/155565.diff 16 Files Affected:
diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt
index c6b87a34a43e9..6fd16419f0c49 100644
--- a/libcxx/include/CMakeLists.txt
+++ b/libcxx/include/CMakeLists.txt
@@ -792,7 +792,6 @@ set(files
__type_traits/aligned_storage.h
__type_traits/aligned_union.h
__type_traits/alignment_of.h
- __type_traits/can_extract_key.h
__type_traits/common_reference.h
__type_traits/common_type.h
__type_traits/conditional.h
@@ -933,6 +932,7 @@ set(files
__utility/small_buffer.h
__utility/swap.h
__utility/to_underlying.h
+ __utility/try_key_extraction.h
__utility/unreachable.h
__variant/monostate.h
__vector/comparison.h
diff --git a/libcxx/include/__fwd/tuple.h b/libcxx/include/__fwd/tuple.h
index 39ed94d9806e5..b3cac4e2a633d 100644
--- a/libcxx/include/__fwd/tuple.h
+++ b/libcxx/include/__fwd/tuple.h
@@ -26,6 +26,12 @@ struct tuple_element;
template <class...>
class tuple;
+template <class>
+inline const bool __is_tuple_v = false;
+
+template <class... _Tp>
+inline const bool __is_tuple_v<tuple<_Tp...>> = true;
+
template <size_t _Ip, class... _Tp>
struct tuple_element<_Ip, tuple<_Tp...> > {
using type _LIBCPP_NODEBUG = __type_pack_element<_Ip, _Tp...>;
diff --git a/libcxx/include/__hash_table b/libcxx/include/__hash_table
index f0f335a4d5cab..91f660d3491e8 100644
--- a/libcxx/include/__hash_table
+++ b/libcxx/include/__hash_table
@@ -29,7 +29,6 @@
#include <__memory/swap_allocator.h>
#include <__memory/unique_ptr.h>
#include <__new/launder.h>
-#include <__type_traits/can_extract_key.h>
#include <__type_traits/copy_cvref.h>
#include <__type_traits/enable_if.h>
#include <__type_traits/invoke.h>
@@ -46,6 +45,7 @@
#include <__utility/move.h>
#include <__utility/pair.h>
#include <__utility/swap.h>
+#include <__utility/try_key_extraction.h>
#include <limits>
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
@@ -797,40 +797,66 @@ public:
_LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(__node_pointer __nd);
_LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(const_iterator __p, __node_pointer __nd);
- template <class _Key, class... _Args>
- _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_key_args(_Key const& __k, _Args&&... __args);
-
- template <class... _Args>
- _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_impl(_Args&&... __args);
-
- template <class _Pp>
- _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Pp&& __x) {
- return __emplace_unique_extract_key(std::forward<_Pp>(__x), __can_extract_key<_Pp, key_type>());
- }
-
- template <class _First,
- class _Second,
- __enable_if_t<__can_extract_map_key<_First, key_type, value_type>::value, int> = 0>
- _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_First&& __f, _Second&& __s) {
- return __emplace_unique_key_args(__f, std::forward<_First>(__f), std::forward<_Second>(__s));
- }
-
template <class... _Args>
_LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Args&&... __args) {
- return __emplace_unique_impl(std::forward<_Args>(__args)...);
- }
-
- template <class _Pp>
- _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) {
- return __emplace_unique_impl(std::forward<_Pp>(__x));
- }
- template <class _Pp>
- _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) {
- return __emplace_unique_key_args(__x, std::forward<_Pp>(__x));
- }
- template <class _Pp>
- _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) {
- return __emplace_unique_key_args(__x.first, std::forward<_Pp>(__x));
+ return std::__try_key_extraction<key_type>(
+ [this](const key_type& __key, _Args&&... __args2) {
+ size_t __hash = hash_function()(__key);
+ size_type __bc = bucket_count();
+ bool __inserted = false;
+ __next_pointer __nd;
+ size_t __chash;
+ if (__bc != 0) {
+ __chash = std::__constrain_hash(__hash, __bc);
+ __nd = __bucket_list_[__chash];
+ if (__nd != nullptr) {
+ for (__nd = __nd->__next_;
+ __nd != nullptr &&
+ (__nd->__hash() == __hash || std::__constrain_hash(__nd->__hash(), __bc) == __chash);
+ __nd = __nd->__next_) {
+ if ((__nd->__hash() == __hash) && key_eq()(__nd->__upcast()->__get_value(), __key))
+ goto __done;
+ }
+ }
+ }
+ {
+ __node_holder __h = __construct_node_hash(__hash, std::forward<_Args>(__args2)...);
+ if (size() + 1 > __bc * max_load_factor() || __bc == 0) {
+ __rehash_unique(std::max<size_type>(2 * __bc + !std::__is_hash_power2(__bc),
+ size_type(__math::ceil(float(size() + 1) / max_load_factor()))));
+ __bc = bucket_count();
+ __chash = std::__constrain_hash(__hash, __bc);
+ }
+ // insert_after __bucket_list_[__chash], or __first_node if bucket is null
+ __next_pointer __pn = __bucket_list_[__chash];
+ if (__pn == nullptr) {
+ __pn = __first_node_.__ptr();
+ __h->__next_ = __pn->__next_;
+ __pn->__next_ = __h.get()->__ptr();
+ // fix up __bucket_list_
+ __bucket_list_[__chash] = __pn;
+ if (__h->__next_ != nullptr)
+ __bucket_list_[std::__constrain_hash(__h->__next_->__hash(), __bc)] = __h.get()->__ptr();
+ } else {
+ __h->__next_ = __pn->__next_;
+ __pn->__next_ = static_cast<__next_pointer>(__h.get());
+ }
+ __nd = static_cast<__next_pointer>(__h.release());
+ // increment size
+ ++size();
+ __inserted = true;
+ }
+ __done:
+ return pair<iterator, bool>(iterator(__nd), __inserted);
+ },
+ [this](_Args&&... __args2) {
+ __node_holder __h = __construct_node(std::forward<_Args>(__args2)...);
+ pair<iterator, bool> __r = __node_insert_unique(__h.get());
+ if (__r.second)
+ __h.release();
+ return __r;
+ },
+ std::forward<_Args>(__args)...);
}
template <class... _Args>
@@ -999,8 +1025,8 @@ private:
template <class... _Args>
_LIBCPP_HIDE_FROM_ABI __node_holder __construct_node(_Args&&... __args);
- template <class _First, class... _Rest>
- _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_hash(size_t __hash, _First&& __f, _Rest&&... __rest);
+ template <class... _Args>
+ _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_hash(size_t __hash, _Args&&... __args);
_LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __hash_table& __u) {
__copy_assign_alloc(__u, integral_constant<bool, __node_traits::propagate_on_container_copy_assignment::value>());
@@ -1614,69 +1640,6 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(const_iterator __p
return __node_insert_multi(__cp);
}
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-template <class _Key, class... _Args>
-pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args) {
- size_t __hash = hash_function()(__k);
- size_type __bc = bucket_count();
- bool __inserted = false;
- __next_pointer __nd;
- size_t __chash;
- if (__bc != 0) {
- __chash = std::__constrain_hash(__hash, __bc);
- __nd = __bucket_list_[__chash];
- if (__nd != nullptr) {
- for (__nd = __nd->__next_;
- __nd != nullptr && (__nd->__hash() == __hash || std::__constrain_hash(__nd->__hash(), __bc) == __chash);
- __nd = __nd->__next_) {
- if ((__nd->__hash() == __hash) && key_eq()(__nd->__upcast()->__get_value(), __k))
- goto __done;
- }
- }
- }
- {
- __node_holder __h = __construct_node_hash(__hash, std::forward<_Args>(__args)...);
- if (size() + 1 > __bc * max_load_factor() || __bc == 0) {
- __rehash_unique(std::max<size_type>(
- 2 * __bc + !std::__is_hash_power2(__bc), size_type(__math::ceil(float(size() + 1) / max_load_factor()))));
- __bc = bucket_count();
- __chash = std::__constrain_hash(__hash, __bc);
- }
- // insert_after __bucket_list_[__chash], or __first_node if bucket is null
- __next_pointer __pn = __bucket_list_[__chash];
- if (__pn == nullptr) {
- __pn = __first_node_.__ptr();
- __h->__next_ = __pn->__next_;
- __pn->__next_ = __h.get()->__ptr();
- // fix up __bucket_list_
- __bucket_list_[__chash] = __pn;
- if (__h->__next_ != nullptr)
- __bucket_list_[std::__constrain_hash(__h->__next_->__hash(), __bc)] = __h.get()->__ptr();
- } else {
- __h->__next_ = __pn->__next_;
- __pn->__next_ = static_cast<__next_pointer>(__h.get());
- }
- __nd = static_cast<__next_pointer>(__h.release());
- // increment size
- ++size();
- __inserted = true;
- }
-__done:
- return pair<iterator, bool>(iterator(__nd), __inserted);
-}
-
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-template <class... _Args>
-pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_impl(_Args&&... __args) {
- __node_holder __h = __construct_node(std::forward<_Args>(__args)...);
- pair<iterator, bool> __r = __node_insert_unique(__h.get());
- if (__r.second)
- __h.release();
- return __r;
-}
-
template <class _Tp, class _Hash, class _Equal, class _Alloc>
template <class... _Args>
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
@@ -1928,15 +1891,14 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&&... __args) {
}
template <class _Tp, class _Hash, class _Equal, class _Alloc>
-template <class _First, class... _Rest>
+template <class... _Args>
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(size_t __hash, _First&& __f, _Rest&&... __rest) {
- static_assert(!__is_hash_value_type<_First, _Rest...>::value, "Construct cannot be called with a hash value type");
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(size_t __hash, _Args&&... __args) {
+ static_assert(!__is_hash_value_type<_Args...>::value, "Construct cannot be called with a hash value type");
__node_allocator& __na = __node_alloc();
__node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
std::__construct_at(std::addressof(*__h), /* next = */ nullptr, /* hash = */ __hash);
- __node_traits::construct(
- __na, std::addressof(__h->__get_value()), std::forward<_First>(__f), std::forward<_Rest>(__rest)...);
+ __node_traits::construct(__na, std::addressof(__h->__get_value()), std::forward<_Args>(__args)...);
__h.get_deleter().__value_constructed = true;
return __h;
}
diff --git a/libcxx/include/__tree b/libcxx/include/__tree
index 0f3640ef6a834..3ad2129ba9ddf 100644
--- a/libcxx/include/__tree
+++ b/libcxx/include/__tree
@@ -23,7 +23,6 @@
#include <__memory/pointer_traits.h>
#include <__memory/swap_allocator.h>
#include <__memory/unique_ptr.h>
-#include <__type_traits/can_extract_key.h>
#include <__type_traits/copy_cvref.h>
#include <__type_traits/enable_if.h>
#include <__type_traits/invoke.h>
@@ -38,6 +37,7 @@
#include <__utility/move.h>
#include <__utility/pair.h>
#include <__utility/swap.h>
+#include <__utility/try_key_extraction.h>
#include <limits>
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
@@ -900,88 +900,74 @@ public:
_NOEXCEPT_(__is_nothrow_swappable_v<value_compare>);
#endif
- template <class _Key, class... _Args>
- _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_key_args(_Key const&, _Args&&... __args);
- template <class _Key, class... _Args>
- _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_hint_unique_key_args(const_iterator, _Key const&, _Args&&...);
-
- template <class... _Args>
- _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_impl(_Args&&... __args);
-
- template <class... _Args>
- _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique_impl(const_iterator __p, _Args&&... __args);
-
template <class... _Args>
_LIBCPP_HIDE_FROM_ABI iterator __emplace_multi(_Args&&... __args);
template <class... _Args>
_LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);
- template <class _Pp>
- _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Pp&& __x) {
- return __emplace_unique_extract_key(std::forward<_Pp>(__x), __can_extract_key<_Pp, key_type>());
- }
-
- template <class _First,
- class _Second,
- __enable_if_t<__can_extract_map_key<_First, key_type, value_type>::value, int> = 0>
- _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_First&& __f, _Second&& __s) {
- return __emplace_unique_key_args(__f, std::forward<_First>(__f), std::forward<_Second>(__s));
- }
-
template <class... _Args>
_LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Args&&... __args) {
- return __emplace_unique_impl(std::forward<_Args>(__args)...);
- }
-
- template <class _Pp>
- _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) {
- return __emplace_unique_impl(std::forward<_Pp>(__x));
- }
-
- template <class _Pp>
- _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) {
- return __emplace_unique_key_args(__x, std::forward<_Pp>(__x));
- }
-
- template <class _Pp>
- _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) {
- return __emplace_unique_key_args(__x.first, std::forward<_Pp>(__x));
- }
-
- template <class _Pp>
- _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique(const_iterator __p, _Pp&& __x) {
- return __emplace_hint_unique_extract_key(__p, std::forward<_Pp>(__x), __can_extract_key<_Pp, key_type>());
- }
-
- template <class _First,
- class _Second,
- __enable_if_t<__can_extract_map_key<_First, key_type, value_type>::value, int> = 0>
- _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique(const_iterator __p, _First&& __f, _Second&& __s) {
- return __emplace_hint_unique_key_args(__p, __f, std::forward<_First>(__f), std::forward<_Second>(__s)).first;
+ return std::__try_key_extraction<key_type>(
+ [this](const key_type& __key, _Args&&... __args2) {
+ __end_node_pointer __parent;
+ __node_base_pointer& __child = __find_equal(__parent, __key);
+ __node_pointer __r = static_cast<__node_pointer>(__child);
+ bool __inserted = false;
+ if (__child == nullptr) {
+ __node_holder __h = __construct_node(std::forward<_Args>(__args2)...);
+ __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
+ __r = __h.release();
+ __inserted = true;
+ }
+ return pair<iterator, bool>(iterator(__r), __inserted);
+ },
+ [this](_Args&&... __args2) {
+ __node_holder __h = __construct_node(std::forward<_Args>(__args2)...);
+ __end_node_pointer __parent;
+ __node_base_pointer& __child = __find_equal(__parent, __h->__get_value());
+ __node_pointer __r = static_cast<__node_pointer>(__child);
+ bool __inserted = false;
+ if (__child == nullptr) {
+ __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
+ __r = __h.release();
+ __inserted = true;
+ }
+ return pair<iterator, bool>(iterator(__r), __inserted);
+ },
+ std::forward<_Args>(__args)...);
}
template <class... _Args>
- _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique(const_iterator __p, _Args&&... __args) {
- return __emplace_hint_unique_impl(__p, std::forward<_Args>(__args)...);
- }
-
- template <class _Pp>
- _LIBCPP_HIDE_FROM_ABI iterator
- __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_fail_tag) {
- return __emplace_hint_unique_impl(__p, std::forward<_Pp>(__x));
- }
-
- template <class _Pp>
- _LIBCPP_HIDE_FROM_ABI iterator
- __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_self_tag) {
- return __emplace_hint_unique_key_args(__p, __x, std::forward<_Pp>(__x)).first;
- }
-
- template <class _Pp>
- _LIBCPP_HIDE_FROM_ABI iterator
- __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_first_tag) {
- return __emplace_hint_unique_key_args(__p, __x.first, std::forward<_Pp>(__x)).first;
+ _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_hint_unique(const_iterator __p, _Args&&... __args) {
+ return std::__try_key_extraction<key_type>(
+ [this, __p](const key_type& __key, _Args&&... __args2) {
+ __end_node_pointer __parent;
+ __node_base_pointer __dummy;
+ __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __key);
+ __node_pointer __r = static_cast<__node_pointer>(__child);
+ bool __inserted = false;
+ if (__child == nullptr) {
+ __node_holder __h = __construct_node(std::forward<_Args>(__args2)...);
+ __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
+ __r = __h.release();
+ __inserted = true;
+ }
+ return pair<iterator, bool>(iterator(__r), __inserted);
+ },
+ [this, __p](_Args&&... __args2) {
+ __node_holder __h = __construct_node(std::forward<_Args>(__args2)...);
+ __end_node_pointer __parent;
+ __node_base_pointer __dummy;
+ __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __h->__get_value());
+ __node_pointer __r = static_cast<__node_pointer>(__child);
+ if (__child == nullptr) {
+ __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
+ __r = __h.release();
+ }
+ return pair<iterator, bool>(iterator(__r), __child == nullptr);
+ },
+ std::forward<_Args>(__args)...);
}
template <class _ValueT = _Tp, __enable_if_t<__is_tree_value_type_v<_ValueT>, int> = 0>
@@ -1801,42 +1787,6 @@ void __tree<_Tp, _Compare, _Allocator>::__insert_node_at(
++__size_;
}
-template <class _Tp, class _Compare, class _Allocator>
-template <class _Key, class... _Args>
-pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
-__tree<_Tp, _Compare, _Allocator>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args) {
- __end_node_pointer __parent;
- __node_base_pointer& __child = __find_equal(__parent, __k);
- __node_pointer __r = static_cast<__node_pointer>(__child);
- bool __inserted = false;
- if (__child == nullptr) {
- __node_holder __h = __construct_node(std::forward<_Args>(__args)...);
- __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
- __r = __h.release();
- __inserted = true;
- }
- return pair<iterator, bool>(iterator(__r), __inserted);
-}
-
-template <class _Tp, class _Compare, class _Allocator>
-template <class _Key, class... _Args>
-pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
-__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_key_args(
- const_iterator __p, _Key const& __k, _Args&&... __args) {
- __end_node_pointer __parent;
- __node_base_pointer __dummy;
- __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __k);
- __node_pointer __r = static_cast<__node_pointer>(__child);
- bool __inserted = false;
- if (__child == nullptr) {
- __node_holder __h = __construct_node(std::forward<_Args>(__args)...);
- __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
- __r = __h.rele...
[truncated]
|
|
LLVM Buildbot has detected a new failure on builder Full details are available at: https://lab.llvm.org/buildbot/#/builders/169/builds/14440 Here is the relevant piece of the build log for the reference |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
The original PR has been reverted because of an LLDB test failure. This patch now works around the test failure by simply allowing the new symbols to show up in a stack trace.
This reverts commit 72c04bb.
Original commit message:
This patch replaces
__can_extract_keywith an overload set to try to extract the key. This simplifies the code, since we don't need to have separate overload sets for the unordered and associative containers. It also allows extending the set of extraction cases more easily, since we have a single place to define how the key is extracted.