Index: include/__hash_table =================================================================== --- include/__hash_table +++ include/__hash_table @@ -31,6 +31,17 @@ _LIBCPP_BEGIN_NAMESPACE_STD + +template +struct __key_equal { + using type = _Pred; +}; + +template +struct __key_equal<_Hash, _Pred, typename __void_t::type> { + using type = typename _Hash::transparent_key_equal; +}; + template struct __hash_value_type; Index: include/unordered_map =================================================================== --- include/unordered_map +++ include/unordered_map @@ -28,7 +28,7 @@ typedef Key key_type; typedef T mapped_type; typedef Hash hasher; - typedef Pred key_equal; + typedef see [unord.req] key_equal; typedef Alloc allocator_type; typedef pair value_type; typedef value_type& reference; @@ -173,9 +173,14 @@ iterator find(const key_type& k); const_iterator find(const key_type& k) const; + template iterator find(const K& k); + template const_iterator find(const K& k) const; size_type count(const key_type& k) const; + template size_type count(const K& k) const; pair equal_range(const key_type& k); pair equal_range(const key_type& k) const; + template pair equal_range(const K& k); + template pair equal_range(const K& k) const; mapped_type& operator[](const key_type& k); mapped_type& operator[](key_type&& k); @@ -227,7 +232,7 @@ typedef Key key_type; typedef T mapped_type; typedef Hash hasher; - typedef Pred key_equal; + typedef see [unord.req] key_equal; typedef Alloc allocator_type; typedef pair value_type; typedef value_type& reference; @@ -355,8 +360,11 @@ iterator find(const key_type& k); const_iterator find(const key_type& k) const; size_type count(const key_type& k) const; + template size_type count(const K& k) const; pair equal_range(const key_type& k); pair equal_range(const key_type& k) const; + template pair equal_range(const K& k); + template pair equal_range(const K& k) const; size_type bucket_count() const noexcept; size_type max_bucket_count() const noexcept; @@ -417,6 +425,8 @@ #pragma GCC system_header #endif +#define __cpp_lib_generic_unordered_lookup + _LIBCPP_BEGIN_NAMESPACE_STD template ::type key_equal; typedef _Alloc allocator_type; typedef pair value_type; typedef value_type& reference; @@ -863,7 +873,6 @@ typedef __hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table; - __table __table_; typedef typename __table::_NodeTypes _NodeTypes; @@ -1273,14 +1282,29 @@ iterator find(const key_type& __k) {return __table_.find(__k);} _LIBCPP_INLINE_VISIBILITY const_iterator find(const key_type& __k) const {return __table_.find(__k);} + template _LIBCPP_INLINE_VISIBILITY + iterator find(const _Kt& __k) {return __table_.find(__k);} + template _LIBCPP_INLINE_VISIBILITY + const_iterator find(const _Kt& __k) const {return __table_.find(__k);} + _LIBCPP_INLINE_VISIBILITY size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} + template _LIBCPP_INLINE_VISIBILITY + size_type count(const _Kt& __k) const {return __table_.__count_unique(__k);} + + _LIBCPP_INLINE_VISIBILITY pair equal_range(const key_type& __k) {return __table_.__equal_range_unique(__k);} _LIBCPP_INLINE_VISIBILITY pair equal_range(const key_type& __k) const {return __table_.__equal_range_unique(__k);} + template_LIBCPP_INLINE_VISIBILITY + pair equal_range(const _Kt& __k) + {return __table_.__equal_range_unique(__k);} + template_LIBCPP_INLINE_VISIBILITY + pair equal_range(const _Kt& __k) const + {return __table_.__equal_range_unique(__k);} mapped_type& operator[](const key_type& __k); #ifndef _LIBCPP_CXX03_LANG @@ -1671,7 +1695,7 @@ typedef _Key key_type; typedef _Tp mapped_type; typedef _Hash hasher; - typedef _Pred key_equal; + typedef typename __key_equal<_Hash, _Pred>::type key_equal; typedef _Alloc allocator_type; typedef pair value_type; typedef value_type& reference; @@ -1974,14 +1998,29 @@ iterator find(const key_type& __k) {return __table_.find(__k);} _LIBCPP_INLINE_VISIBILITY const_iterator find(const key_type& __k) const {return __table_.find(__k);} + template _LIBCPP_INLINE_VISIBILITY + iterator find(const _Kt& __k) {return __table_.find(__k);} + template _LIBCPP_INLINE_VISIBILITY + const_iterator find(const _Kt& __k) const {return __table_.find(__k);} + _LIBCPP_INLINE_VISIBILITY - size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} + size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} + template _LIBCPP_INLINE_VISIBILITY + size_type count(const _Kt& __k) const {return __table_.__count_unique(__k);} + + _LIBCPP_INLINE_VISIBILITY pair equal_range(const key_type& __k) - {return __table_.__equal_range_multi(__k);} + {return __table_.__equal_range_unique(__k);} _LIBCPP_INLINE_VISIBILITY pair equal_range(const key_type& __k) const - {return __table_.__equal_range_multi(__k);} + {return __table_.__equal_range_unique(__k);} + template_LIBCPP_INLINE_VISIBILITY + pair equal_range(const _Kt& __k) + {return __table_.__equal_range_unique(__k);} + template_LIBCPP_INLINE_VISIBILITY + pair equal_range(const _Kt& __k) const + {return __table_.__equal_range_unique(__k);} _LIBCPP_INLINE_VISIBILITY size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} Index: include/unordered_set =================================================================== --- include/unordered_set +++ include/unordered_set @@ -28,7 +28,7 @@ typedef Value key_type; typedef key_type value_type; typedef Hash hasher; - typedef Pred key_equal; + typedef see [unord.req] key_equal; typedef Alloc allocator_type; typedef value_type& reference; typedef const value_type& const_reference; @@ -145,9 +145,14 @@ iterator find(const key_type& k); const_iterator find(const key_type& k) const; + template iterator find(const K& k); + template const_iterator find(const K& k) const; size_type count(const key_type& k) const; + template size_type count(const K& k) const; pair equal_range(const key_type& k); pair equal_range(const key_type& k) const; + template pair equal_range(const K& k); + template pair equal_range(const K& k) const; size_type bucket_count() const noexcept; size_type max_bucket_count() const noexcept; @@ -193,7 +198,7 @@ typedef Value key_type; typedef key_type value_type; typedef Hash hasher; - typedef Pred key_equal; + typedef see [unord.req] key_equal; typedef Alloc allocator_type; typedef value_type& reference; typedef const value_type& const_reference; @@ -309,9 +314,14 @@ iterator find(const key_type& k); const_iterator find(const key_type& k) const; + template iterator find(const K& k); + template const_iterator find(const K& k) const; size_type count(const key_type& k) const; + template size_type count(const K& k) const; pair equal_range(const key_type& k); pair equal_range(const key_type& k) const; + template pair equal_range(const K& k); + template pair equal_range(const K& k) const; size_type bucket_count() const noexcept; size_type max_bucket_count() const noexcept; @@ -370,6 +380,8 @@ #pragma GCC system_header #endif +#define __cpp_lib_generic_unordered_lookup + _LIBCPP_BEGIN_NAMESPACE_STD template @@ -384,7 +396,7 @@ typedef _Value key_type; typedef key_type value_type; typedef _Hash hasher; - typedef _Pred key_equal; + typedef typename __key_equal<_Hash, _Pred>::type key_equal; typedef _Alloc allocator_type; typedef value_type& reference; typedef const value_type& const_reference; @@ -672,14 +684,29 @@ iterator find(const key_type& __k) {return __table_.find(__k);} _LIBCPP_INLINE_VISIBILITY const_iterator find(const key_type& __k) const {return __table_.find(__k);} + template _LIBCPP_INLINE_VISIBILITY + iterator find(const _Kt& __k) {return __table_.find(__k);} + template _LIBCPP_INLINE_VISIBILITY + const_iterator find(const _Kt& __k) const {return __table_.find(__k);} + _LIBCPP_INLINE_VISIBILITY size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} + template _LIBCPP_INLINE_VISIBILITY + size_type count(const _Kt& __k) const {return __table_.__count_unique(__k);} + + _LIBCPP_INLINE_VISIBILITY pair equal_range(const key_type& __k) {return __table_.__equal_range_unique(__k);} _LIBCPP_INLINE_VISIBILITY pair equal_range(const key_type& __k) const {return __table_.__equal_range_unique(__k);} + template_LIBCPP_INLINE_VISIBILITY + pair equal_range(const _Kt& __k) + {return __table_.__equal_range_unique(__k);} + template_LIBCPP_INLINE_VISIBILITY + pair equal_range(const _Kt& __k) const + {return __table_.__equal_range_unique(__k);} _LIBCPP_INLINE_VISIBILITY size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} @@ -984,7 +1011,7 @@ typedef _Value key_type; typedef key_type value_type; typedef _Hash hasher; - typedef _Pred key_equal; + typedef typename __key_equal<_Hash, _Pred>::type key_equal; typedef _Alloc allocator_type; typedef value_type& reference; typedef const value_type& const_reference; @@ -1240,14 +1267,29 @@ iterator find(const key_type& __k) {return __table_.find(__k);} _LIBCPP_INLINE_VISIBILITY const_iterator find(const key_type& __k) const {return __table_.find(__k);} + template _LIBCPP_INLINE_VISIBILITY + iterator find(const _Kt& __k) {return __table_.find(__k);} + template _LIBCPP_INLINE_VISIBILITY + const_iterator find(const _Kt& __k) const {return __table_.find(__k);} + _LIBCPP_INLINE_VISIBILITY - size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} + size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} + template _LIBCPP_INLINE_VISIBILITY + size_type count(const _Kt& __k) const {return __table_.__count_unique(__k);} + + _LIBCPP_INLINE_VISIBILITY pair equal_range(const key_type& __k) - {return __table_.__equal_range_multi(__k);} + {return __table_.__equal_range_unique(__k);} _LIBCPP_INLINE_VISIBILITY pair equal_range(const key_type& __k) const - {return __table_.__equal_range_multi(__k);} + {return __table_.__equal_range_unique(__k);} + template_LIBCPP_INLINE_VISIBILITY + pair equal_range(const _Kt& __k) + {return __table_.__equal_range_unique(__k);} + template_LIBCPP_INLINE_VISIBILITY + pair equal_range(const _Kt& __k) const + {return __table_.__equal_range_unique(__k);} _LIBCPP_INLINE_VISIBILITY size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} Index: test/std/containers/hetro_lookups.pass.cpp =================================================================== --- /dev/null +++ test/std/containers/hetro_lookups.pass.cpp @@ -0,0 +1,57 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include +#include +#include +#include +#include "test_macros.h" + +// +// + +using namespace std; + +struct custom_hash +{ + using transparent_key_equal = equal_to; + size_t operator()(int i) const { return (double)i; } +}; + +template +void test_container_lookups(U... args) +{ + T u; + P pairs[] = {args...}; + + for (auto& x: pairs) u.insert(x); + + assert(u.find(1.0) != u.end()); + assert(u.count(2.0) != 0); + + auto range = u.equal_range(2.0); + assert(range.first != range.second); +} + +int main () +{ + test_container_lookups, pair>(make_pair(0, -0), + make_pair(1, -1), + make_pair(2, -2), + make_pair(2, -3)); + test_container_lookups, pair>(make_pair(0, -0), + make_pair(1, -1), + make_pair(2, -2), + make_pair(2, -3)); + test_container_lookups, int>( + 0, 1, 2, 2); + test_container_lookups, int>( + 0, 1, 2, 2); + + return 0; +} \ No newline at end of file Index: test/std/containers/key_equal.fail.cpp =================================================================== --- /dev/null +++ test/std/containers/key_equal.fail.cpp @@ -0,0 +1,36 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include +#include +#include +#include "test_macros.h" + +// +// + +using namespace std; + +struct custom_hash +{ + using transparent_key_equal = equal_to; +}; + + +int main () +{ + // expected-error {{type 'const custom_hash' does not provide a call operator}} + // expected-error {{static_assert failed due to requirement '__check_hash_requirements::value' "the specified hash does not meet the Hash requirements"}} + unordered_map u = { + {0, -0}, + {1, -1}, + {2, -2} + }; + + return 0; +} \ No newline at end of file Index: test/std/containers/key_equal.pass.cpp =================================================================== --- /dev/null +++ test/std/containers/key_equal.pass.cpp @@ -0,0 +1,41 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include +#include +#include +#include +#include "test_macros.h" + +// +// + +using namespace std; + +struct custom_hash +{ + using transparent_key_equal = equal_to; + size_t operator()(int i) const { return i; } +}; + +template +void test_key_equal() +{ + ASSERT_SAME_TYPE(typename T::key_equal, custom_hash::transparent_key_equal); + ASSERT_SAME_TYPE(typename U::key_equal, equal_to); +} + +int main () +{ + test_key_equal, unordered_map>(); + test_key_equal, unordered_multimap>(); + test_key_equal, unordered_set>(); + test_key_equal, unordered_multiset>(); + + return 0; +} \ No newline at end of file