From patchwork Tue Dec 1 07:19:18 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Fran=C3=A7ois_Dumont?= X-Patchwork-Id: 1408633 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=pass (p=none dis=none) header.from=gcc.gnu.org Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=BeudejwL; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4ClYPy5TzSz9sRK for ; Tue, 1 Dec 2020 18:19:31 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 113CC393D004; Tue, 1 Dec 2020 07:19:28 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 113CC393D004 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1606807168; bh=Ktliai8eVlBvpwYXiIC8fOlpgLxTdjTjSOjN6+FEoVo=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=BeudejwLy4Lpy/wjU2vskIlxQQNvrTEADN3mbxS6FBBA45goKhqBnxfdq1zpDzljn Lkz6spysaUB0d1fniHef54xq+Y7/DCLuppJqX/VVDL5VLM9YkChZ8JmNe29EPOvQlU lQa+jU2knPe3IFxCj5LD+U47EzJbfdBbaiACqkEE= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-wm1-x336.google.com (mail-wm1-x336.google.com [IPv6:2a00:1450:4864:20::336]) by sourceware.org (Postfix) with ESMTPS id 088BE3854810; Tue, 1 Dec 2020 07:19:22 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 088BE3854810 Received: by mail-wm1-x336.google.com with SMTP id g185so2763519wmf.3; Mon, 30 Nov 2020 23:19:21 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:to:from:subject:message-id:date:user-agent :mime-version:content-language; bh=Ktliai8eVlBvpwYXiIC8fOlpgLxTdjTjSOjN6+FEoVo=; b=sPuV9Mww/fpaCwQE0PVddSkkyH91td7twcgBo/lsgQklZLIfwqt2K1LZdNjg1S5f2m v/gGZoT+It0eOsMIcSftEv+YN9VplHp/gfNXNVV0CbeO5ou/2SWGRZ692Ycr64OlNnq5 32YNy3I6TT2dCAHoc8aKPBzazysHsrRnZtLvot7+oHdm+trY2Z58ybRJC1DhI/ZJ0sDN BELoX2HkUTwxmUfJw8KIJdWyomCxkpx6jVfTTVpcl64I69+yn5COgCs6dgZcwm+mnlK5 5jgzQ/tVga7chbCsRSKVKy6WPWD3RWvsUkFZQF4/a3t4ySDGYiASJKWTIpIgP8CyaaxY 5E6Q== X-Gm-Message-State: AOAM532m2amDMUJm0xDPo6LSYLILuYngxeWwEXk258DKJduAcucbCIob yZ8go+HGAj0jNbM/6XErNsErnVMnAymuXw== X-Google-Smtp-Source: ABdhPJxjR2v0oC+8XFfp9/1UFawRZmwFMGttcWsot2i4RS6jsoJYlcDgX0e7hLAOJMgyvWcjasUkAw== X-Received: by 2002:a1c:2502:: with SMTP id l2mr1271121wml.40.1606807160759; Mon, 30 Nov 2020 23:19:20 -0800 (PST) Received: from ?IPv6:2a01:e0a:1dc:b1c0:5c4a:f2c8:e01c:2c3? ([2a01:e0a:1dc:b1c0:5c4a:f2c8:e01c:2c3]) by smtp.googlemail.com with ESMTPSA id e1sm1576730wra.22.2020.11.30.23.19.19 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 30 Nov 2020 23:19:19 -0800 (PST) To: "libstdc++@gcc.gnu.org" , gcc-patches Subject: [PATCH] Add unordered containers heterogeneous lookup Message-ID: <7ec87f53-858e-c4b6-8f71-f48a0bc7dc19@gmail.com> Date: Tue, 1 Dec 2020 08:19:18 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.10.0 MIME-Version: 1.0 Content-Language: fr X-Spam-Status: No, score=-10.3 required=5.0 tests=BAYES_00, BODY_8BITS, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: =?utf-8?q?Fran=C3=A7ois_Dumont_via_Gcc-patches?= From: =?utf-8?q?Fran=C3=A7ois_Dumont?= Reply-To: =?utf-8?q?Fran=C3=A7ois_Dumont?= Errors-To: gcc-patches-bounces@gcc.gnu.org Sender: "Gcc-patches" Let me know if I need to reference a specific paper or any other Standard reference here. Maybe P1690R1 I used here ? I tried to allow the same partition trick you can have on ordered containers (see Partition in tests) even if here elements are not ordered so I aren't sure there can be any usage of it.     libstdc++: Add unordered containers heterogeneous lookup     Add unordered containers heterogeneous lookup member functions find, count, contains and     equal_range in C++20. Those members are considered for overload resolution only if hash and     equal functors used to instantiate the container have a nested is_transparent type.     libstdc++-v3/ChangeLog:             * include/bits/stl_tree.h             (__has_is_transparent, __has_is_transparent_t): Move...             * include/bits/stl_function.h: ...here.             * include/bits/hashtable_policy.h (_Hash_code_base<>::_M_hash_code):             Use template key type.             (_Hashtable_base<>::_M_equals): Likewise.             * include/bits/hashtable.h (_Hashtable<>::_M_find_tr, _Hashtable<>::_M_count_tr,             _Hashtable<>::_M_equal_range_tr): New member function templates to perform             heterogeneous lookup.             (_Hashtable<>::_M_find_before_node): Use template key type.             (_Hashtable<>::_M_find_node): Likewise.             * include/bits/unordered_map.h (unordered_map::find<>, unordered_map::count<>,             unordered_map::contains<>, unordered_map::equal_range<>): New member function             templates to perform heterogeneous lookup.             (unordered_multimap::find<>, unordered_multimap::count<>,             unordered_multimap::contains<>, unordered_multimap::equal_range<>): Likewise.             * include/bits/unordered_set.h (unordered_set::find<>, unordered_set::count<>,             unordered_set::contains<>, unordered_set::equal_range<>): Likewise.             (unordered_multiset::find<>, unordered_multiset::count<>,             unordered_multiset::contains<>, unordered_multiset::equal_range<>): Likewise.             * include/debug/unordered_map             (unordered_map::find<>, unordered_map::equal_range<>): Likewise.             (unordered_multimap::find<>, unordered_multimap::equal_range<>): Likewise.             * include/debug/unordered_set             (unordered_set::find<>, unordered_set::equal_range<>): Likewise.             (unordered_multiset::find<>, unordered_multiset::equal_range<>): Likewise.             * testsuite/23_containers/unordered_map/operations/1.cc: New test.             * testsuite/23_containers/unordered_multimap/operations/1.cc: New test.             * testsuite/23_containers/unordered_multiset/operations/1.cc: New test.             * testsuite/23_containers/unordered_set/operations/1.cc: New test. Tested under Linux x86_64 normal and debug modes. François diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 6c6c5edde0b..30d4ee58100 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -724,6 +724,38 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION std::pair equal_range(const key_type& __k) const; +#if __cplusplus > 201702L + template, + typename = __has_is_transparent_t<_Equal, _Kt>> + iterator + _M_find_tr(const _Kt& __k); + + template, + typename = __has_is_transparent_t<_Equal, _Kt>> + const_iterator + _M_find_tr(const _Kt& __k) const; + + template, + typename = __has_is_transparent_t<_Equal, _Kt>> + size_type + _M_count_tr(const _Kt& __k) const; + + template, + typename = __has_is_transparent_t<_Equal, _Kt>> + pair + _M_equal_range_tr(const _Kt& __k); + + template, + typename = __has_is_transparent_t<_Equal, _Kt>> + pair + _M_equal_range_tr(const _Kt& __k) const; +#endif + private: // Bucket index computation helpers. size_type @@ -736,12 +768,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Find and insert helper functions and types // Find the node before the one matching the criteria. + template __node_base_ptr - _M_find_before_node(size_type, const key_type&, __hash_code) const; + _M_find_before_node(size_type, const _Kt&, __hash_code) const; + template __node_ptr - _M_find_node(size_type __bkt, const key_type& __key, - __hash_code __c) const + _M_find_node(size_type __bkt, const _Kt& __key, __hash_code __c) const { __node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c); if (__before_n) @@ -1532,6 +1565,40 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return const_iterator(_M_find_node(__bkt, __k, __code)); } +#if __cplusplus > 201703L + template + template + auto + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_find_tr(const _Kt& __k) + -> iterator + { + __hash_code __code = this->_M_hash_code(__k); + std::size_t __bkt = _M_bucket_index(__code); + return iterator(_M_find_node(__bkt, __k, __code)); + } + + template + template + auto + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_find_tr(const _Kt& __k) const + -> const_iterator + { + __hash_code __code = this->_M_hash_code(__k); + std::size_t __bkt = _M_bucket_index(__code); + return const_iterator(_M_find_node(__bkt, __k, __code)); + } +#endif + template 201703L + template + template + auto + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_count_tr(const _Kt& __k) const + -> size_type + { + __hash_code __code = this->_M_hash_code(__k); + std::size_t __bkt = _M_bucket_index(__code); + auto __n = _M_find_node(__bkt, __k, __code); + if (!__n) + return 0; + + // All equivalent values are next to each other, if we find a + // non-equivalent value after an equivalent one it means that we won't + // find any new equivalent value. + iterator __it(__n); + size_type __result = 1; + for (++__it; __it._M_cur && this->_M_equals(__k, __code, *__it._M_cur); + ++__it) + ++__result; + + return __result; + } +#endif + template 201703L + template + template + auto + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_equal_range_tr(const _Kt& __k) + -> pair + { + __hash_code __code = this->_M_hash_code(__k); + std::size_t __bkt = _M_bucket_index(__code); + auto __n = _M_find_node(__bkt, __k, __code); + iterator __ite(__n); + if (!__n) + return { __ite, __ite }; + + // All equivalent values are next to each other, if we find a + // non-equivalent value after an equivalent one it means that we won't + // find any new equivalent value. + auto __beg = __ite++; + while (__ite._M_cur && this->_M_equals(__k, __code, *__ite._M_cur)) + ++__ite; + + return { __beg, __ite }; + } + + template + template + auto + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_equal_range_tr(const _Kt& __k) const + -> pair + { + __hash_code __code = this->_M_hash_code(__k); + std::size_t __bkt = _M_bucket_index(__code); + auto __n = _M_find_node(__bkt, __k, __code); + const_iterator __ite(__n); + if (!__n) + return { __ite, __ite }; + + // All equivalent values are next to each other, if we find a + // non-equivalent value after an equivalent one it means that we won't + // find any new equivalent value. + auto __beg = __ite++; + while (__ite._M_cur && this->_M_equals(__k, __code, *__ite._M_cur)) + ++__ite; + + return { __beg, __ite }; + } +#endif + // Find the node before the one whose key compares equal to k in the bucket // bkt. Return nullptr if no node is found. template + template auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_find_before_node(size_type __bkt, const key_type& __k, + _M_find_before_node(size_type __bkt, const _Kt& __k, __hash_code __code) const -> __node_base_ptr { diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index 28372979c87..340aaede50c 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -1211,10 +1211,11 @@ namespace __detail _Hash_code_base() = default; _Hash_code_base(const _Hash& __hash) : __ebo_hash(__hash) { } + template __hash_code - _M_hash_code(const _Key& __k) const + _M_hash_code(const _Kt& __k) const { - static_assert(__is_invocable{}, + static_assert(__is_invocable{}, "hash function must be invocable with an argument of key type"); return _M_hash()(__k); } @@ -1597,11 +1598,14 @@ namespace __detail : __hash_code_base(__hash), _EqualEBO(__eq) { } + template bool - _M_equals(const _Key& __k, __hash_code __c, - const _Hash_node_value<_Value, __hash_cached::value>& __n) const + _M_equals(const _Kt& __k, __hash_code __c, + const _Hash_node_value<_Value, + __hash_cached::value>& __n) const { - static_assert(__is_invocable{}, + static_assert( + __is_invocable{}, "key equality predicate must be invocable with two arguments of " "key type"); return _S_equals(__c, __n) && _M_eq()(__k, _ExtractKey{}(__n._M_v())); diff --git a/libstdc++-v3/include/bits/stl_function.h b/libstdc++-v3/include/bits/stl_function.h index 77f8ccb051a..37dab358558 100644 --- a/libstdc++-v3/include/bits/stl_function.h +++ b/libstdc++-v3/include/bits/stl_function.h @@ -1385,6 +1385,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION /** @} */ +#if __cplusplus >= 201402L + template> + struct __has_is_transparent + { }; + + template + struct __has_is_transparent<_Func, _SfinaeType, + __void_t> + { typedef void type; }; + + template + using __has_is_transparent_t + = typename __has_is_transparent<_Func, _SfinaeType>::type; +#endif + _GLIBCXX_END_NAMESPACE_VERSION } // namespace diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h index a51d6da4ae8..3f854ace63b 100644 --- a/libstdc++-v3/include/bits/stl_tree.h +++ b/libstdc++-v3/include/bits/stl_tree.h @@ -415,21 +415,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z, _Rb_tree_node_base& __header) throw (); -#if __cplusplus >= 201402L - template> - struct __has_is_transparent - { }; - - template - struct __has_is_transparent<_Cmp, _SfinaeType, - __void_t> - { typedef void type; }; - - template - using __has_is_transparent_t - = typename __has_is_transparent<_Cmp, _SfinaeType>::type; -#endif - #if __cplusplus > 201402L template struct _Rb_tree_merge_helper { }; diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h index 1aaa1a1a6ee..1a7bee28857 100644 --- a/libstdc++-v3/include/bits/unordered_map.h +++ b/libstdc++-v3/include/bits/unordered_map.h @@ -868,11 +868,26 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER find(const key_type& __x) { return _M_h.find(__x); } +#if __cplusplus > 201703L + template + auto + find(const _Kt& __x) -> decltype(_M_h._M_find_tr(__x)) + { return _M_h._M_find_tr(__x); } +#endif + const_iterator find(const key_type& __x) const { return _M_h.find(__x); } + +#if __cplusplus > 201703L + template + auto + find(const _Kt& __x) const -> decltype(_M_h._M_find_tr(__x)) + { return _M_h._M_find_tr(__x); } +#endif //@} + //@{ /** * @brief Finds the number of elements. * @param __x Key to count. @@ -887,6 +902,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return _M_h.count(__x); } #if __cplusplus > 201703L + template + auto + count(const _Kt& __x) const -> decltype(_M_h._M_count_tr(__x)) + { return _M_h._M_count_tr(__x); } +#endif + //@} + +#if __cplusplus > 201703L + //@{ /** * @brief Finds whether an element with the given key exists. * @param __x Key of elements to be located. @@ -895,6 +919,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER bool contains(const key_type& __x) const { return _M_h.find(__x) != _M_h.end(); } + + template + auto + contains(const _Kt& __x) const + -> decltype(_M_h._M_find_tr(__x), void(), true) + { return _M_h._M_find_tr(__x) != _M_h.end(); } + //@} #endif //@{ @@ -910,9 +941,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER equal_range(const key_type& __x) { return _M_h.equal_range(__x); } +#if __cplusplus > 201703L + template + auto + equal_range(const _Kt& __x) + -> decltype(_M_h._M_equal_range_tr(__x)) + { return _M_h._M_equal_range_tr(__x); } +#endif + std::pair equal_range(const key_type& __x) const { return _M_h.equal_range(__x); } + +#if __cplusplus > 201703L + template + auto + equal_range(const _Kt& __x) const + -> decltype(_M_h._M_equal_range_tr(__x)) + { return _M_h._M_equal_range_tr(__x); } +#endif //@} //@{ @@ -1764,11 +1811,26 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER find(const key_type& __x) { return _M_h.find(__x); } +#if __cplusplus > 201703L + template + auto + find(const _Kt& __x) -> decltype(_M_h._M_find_tr(__x)) + { return _M_h._M_find_tr(__x); } +#endif + const_iterator find(const key_type& __x) const { return _M_h.find(__x); } + +#if __cplusplus > 201703L + template + auto + find(const _Kt& __x) const -> decltype(_M_h._M_find_tr(__x)) + { return _M_h._M_find_tr(__x); } +#endif //@} + //@{ /** * @brief Finds the number of elements. * @param __x Key to count. @@ -1779,6 +1841,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return _M_h.count(__x); } #if __cplusplus > 201703L + template + auto + count(const _Kt& __x) const -> decltype(_M_h._M_count_tr(__x)) + { return _M_h._M_count_tr(__x); } +#endif + //@} + +#if __cplusplus > 201703L + //@{ /** * @brief Finds whether an element with the given key exists. * @param __x Key of elements to be located. @@ -1787,6 +1858,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER bool contains(const key_type& __x) const { return _M_h.find(__x) != _M_h.end(); } + + template + auto + contains(const _Kt& __x) const + -> decltype(_M_h._M_find_tr(__x), void(), true) + { return _M_h._M_find_tr(__x) != _M_h.end(); } + //@} #endif //@{ @@ -1800,9 +1878,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER equal_range(const key_type& __x) { return _M_h.equal_range(__x); } +#if __cplusplus > 201703L + template + auto + equal_range(const _Kt& __x) + -> decltype(_M_h._M_equal_range_tr(__x)) + { return _M_h._M_equal_range_tr(__x); } +#endif + std::pair equal_range(const key_type& __x) const { return _M_h.equal_range(__x); } + +#if __cplusplus > 201703L + template + auto + equal_range(const _Kt& __x) const + -> decltype(_M_h._M_equal_range_tr(__x)) + { return _M_h._M_equal_range_tr(__x); } +#endif //@} // bucket interface. diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h index 6cbfcb1f0b6..f5391e1bdf2 100644 --- a/libstdc++-v3/include/bits/unordered_set.h +++ b/libstdc++-v3/include/bits/unordered_set.h @@ -650,11 +650,28 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER find(const key_type& __x) { return _M_h.find(__x); } +#if __cplusplus > 201703L + template + auto + find(const _Kt& __k) + -> decltype(_M_h._M_find_tr(__k)) + { return _M_h._M_find_tr(__k); } +#endif + const_iterator find(const key_type& __x) const { return _M_h.find(__x); } + +#if __cplusplus > 201703L + template + auto + find(const _Kt& __k) const + -> decltype(_M_h._M_find_tr(__k)) + { return _M_h._M_find_tr(__k); } +#endif //@} + //@{ /** * @brief Finds the number of elements. * @param __x Element to located. @@ -669,6 +686,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return _M_h.count(__x); } #if __cplusplus > 201703L + template + auto + count(const _Kt& __k) const + -> decltype(_M_h._M_count_tr(__k)) + { return _M_h._M_count_tr(__k); } +#endif + //@} + +#if __cplusplus > 201703L + //@{ /** * @brief Finds whether an element with the given key exists. * @param __x Key of elements to be located. @@ -677,6 +704,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER bool contains(const key_type& __x) const { return _M_h.find(__x) != _M_h.end(); } + + template + auto + contains(const _Kt& __k) const + -> decltype(_M_h._M_find_tr(__k), void(), true) + { return _M_h._M_find_tr(__k) != _M_h.end(); } + //@} #endif //@{ @@ -692,9 +726,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER equal_range(const key_type& __x) { return _M_h.equal_range(__x); } +#if __cplusplus > 201703L + template + auto + equal_range(const _Kt& __k) + -> decltype(_M_h._M_equal_range_tr(__k)) + { return _M_h._M_equal_range_tr(__k); } +#endif + std::pair equal_range(const key_type& __x) const { return _M_h.equal_range(__x); } + +#if __cplusplus > 201703L + template + auto + equal_range(const _Kt& __k) const + -> decltype(_M_h._M_equal_range_tr(__k)) + { return _M_h._M_equal_range_tr(__k); } +#endif //@} // bucket interface. @@ -1450,11 +1500,28 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER find(const key_type& __x) { return _M_h.find(__x); } +#if __cplusplus > 201703L + template + auto + find(const _Kt& __x) + -> decltype(_M_h._M_find_tr(__x)) + { return _M_h._M_find_tr(__x); } +#endif + const_iterator find(const key_type& __x) const { return _M_h.find(__x); } + +#if __cplusplus > 201703L + template + auto + find(const _Kt& __x) const + -> decltype(_M_h._M_find_tr(__x)) + { return _M_h._M_find_tr(__x); } +#endif //@} + //@{ /** * @brief Finds the number of elements. * @param __x Element to located. @@ -1465,6 +1532,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return _M_h.count(__x); } #if __cplusplus > 201703L + template + auto + count(const _Kt& __x) const -> decltype(_M_h._M_count_tr(__x)) + { return _M_h._M_count_tr(__x); } +#endif + //@} + +#if __cplusplus > 201703L + //@{ /** * @brief Finds whether an element with the given key exists. * @param __x Key of elements to be located. @@ -1473,6 +1549,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER bool contains(const key_type& __x) const { return _M_h.find(__x) != _M_h.end(); } + + template + auto + contains(const _Kt& __x) const + -> decltype(_M_h._M_find_tr(__x), void(), true) + { return _M_h._M_find_tr(__x) != _M_h.end(); } + //@} #endif //@{ @@ -1486,9 +1569,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER equal_range(const key_type& __x) { return _M_h.equal_range(__x); } +#if __cplusplus > 201703L + template + auto + equal_range(const _Kt& __x) + -> decltype(_M_h._M_equal_range_tr(__x)) + { return _M_h._M_equal_range_tr(__x); } +#endif + std::pair equal_range(const key_type& __x) const { return _M_h.equal_range(__x); } + +#if __cplusplus > 201703L + template + auto + equal_range(const _Kt& __x) const + -> decltype(_M_h._M_equal_range_tr(__x)) + { return _M_h._M_equal_range_tr(__x); } +#endif //@} // bucket interface. diff --git a/libstdc++-v3/include/debug/unordered_map b/libstdc++-v3/include/debug/unordered_map index bae179b58ac..a9f7452f841 100644 --- a/libstdc++-v3/include/debug/unordered_map +++ b/libstdc++-v3/include/debug/unordered_map @@ -545,10 +545,28 @@ namespace __debug find(const key_type& __key) { return { _Base::find(__key), this }; } +#if __cplusplus > 201703L + template, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + iterator + find(const _Kt& __k) + { return { _Base::find(__k), this }; } +#endif + const_iterator find(const key_type& __key) const { return { _Base::find(__key), this }; } +#if __cplusplus > 201703L + template, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + const_iterator + find(const _Kt& __k) const + { return { _Base::find(__k), this }; } +#endif + std::pair equal_range(const key_type& __key) { @@ -556,6 +574,18 @@ namespace __debug return { { __res.first, this }, { __res.second, this } }; } +#if __cplusplus > 201703L + template, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair + equal_range(const _Kt& __k) + { + auto __res = _Base::equal_range(__k); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + std::pair equal_range(const key_type& __key) const { @@ -563,6 +593,18 @@ namespace __debug return { { __res.first, this }, { __res.second, this } }; } +#if __cplusplus > 201703L + template, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair + equal_range(const _Kt& __k) const + { + auto __res = _Base::equal_range(__k); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + size_type erase(const key_type& __key) { @@ -1157,10 +1199,28 @@ namespace __debug find(const key_type& __key) { return { _Base::find(__key), this }; } +#if __cplusplus > 201703L + template, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + iterator + find(const _Kt& __k) + { return { _Base::find(__k), this }; } +#endif + const_iterator find(const key_type& __key) const { return { _Base::find(__key), this }; } +#if __cplusplus > 201703L + template, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + const_iterator + find(const _Kt& __k) const + { return { _Base::find(__k), this }; } +#endif + std::pair equal_range(const key_type& __key) { @@ -1168,6 +1228,18 @@ namespace __debug return { { __res.first, this }, { __res.second, this } }; } +#if __cplusplus > 201703L + template, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair + equal_range(const _Kt& __k) + { + auto __res = _Base::equal_range(__k); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + std::pair equal_range(const key_type& __key) const { @@ -1175,6 +1247,18 @@ namespace __debug return { { __res.first, this }, { __res.second, this } }; } +#if __cplusplus > 201703L + template, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair + equal_range(const _Kt& __k) const + { + auto __res = _Base::equal_range(__k); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + size_type erase(const key_type& __key) { diff --git a/libstdc++-v3/include/debug/unordered_set b/libstdc++-v3/include/debug/unordered_set index 97e6a74ebb4..6b7cb8b5108 100644 --- a/libstdc++-v3/include/debug/unordered_set +++ b/libstdc++-v3/include/debug/unordered_set @@ -430,10 +430,28 @@ namespace __debug find(const key_type& __key) { return { _Base::find(__key), this }; } +#if __cplusplus > 201703L + template, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + iterator + find(const _Kt& __k) + { return { _Base::find(__k), this }; } +#endif + const_iterator find(const key_type& __key) const { return { _Base::find(__key), this }; } +#if __cplusplus > 201703L + template, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + const_iterator + find(const _Kt& __k) const + { return { _Base::find(__k), this }; } +#endif + std::pair equal_range(const key_type& __key) { @@ -441,6 +459,18 @@ namespace __debug return { { __res.first, this }, { __res.second, this } }; } +#if __cplusplus > 201703L + template, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair + equal_range(const _Kt& __k) + { + auto __res = _Base::equal_range(__k); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + std::pair equal_range(const key_type& __key) const { @@ -448,6 +478,18 @@ namespace __debug return { { __res.first, this }, { __res.second, this } }; } +#if __cplusplus > 201703L + template, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair + equal_range(const _Kt& __k) const + { + auto __res = _Base::equal_range(__k); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + size_type erase(const key_type& __key) { @@ -1002,10 +1044,28 @@ namespace __debug find(const key_type& __key) { return { _Base::find(__key), this }; } +#if __cplusplus > 201703L + template, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + iterator + find(const _Kt& __k) + { return { _Base::find(__k), this }; } +#endif + const_iterator find(const key_type& __key) const { return { _Base::find(__key), this }; } +#if __cplusplus > 201703L + template, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + const_iterator + find(const _Kt& __k) const + { return { _Base::find(__k), this }; } +#endif + std::pair equal_range(const key_type& __key) { @@ -1013,6 +1073,18 @@ namespace __debug return { { __res.first, this }, { __res.second, this } }; } +#if __cplusplus > 201703L + template, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair + equal_range(const _Kt& __k) + { + auto __res = _Base::equal_range(__k); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + std::pair equal_range(const key_type& __key) const { @@ -1020,6 +1092,18 @@ namespace __debug return { { __res.first, this }, { __res.second, this } }; } +#if __cplusplus > 201703L + template, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair + equal_range(const _Kt& __k) const + { + auto __res = _Base::equal_range(__k); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + size_type erase(const key_type& __key) { diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/operations/1.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/operations/1.cc new file mode 100644 index 00000000000..df9dcd62478 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/operations/1.cc @@ -0,0 +1,168 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-do run { target c++20 } } + +#include +#include + +struct Equal +{ + typedef void is_transparent; + + bool operator()(int i, long l) const { return i == l; } + bool operator()(long l, int i) const { return l == i; } + bool operator()(int i, int j) const { ++count; return i == j; } + + static int count; +}; + +int Equal::count = 0; + +struct Hash +{ + typedef void is_transparent; + + std::size_t operator()(int i) const { ++count; return i; } + std::size_t operator()(long l) const { return l; } + + static int count; +}; + +int Hash::count = 0; + +using test_type = std::unordered_map; + +test_type x{ { 1, '2' }, { 3, '4' } }; +const test_type& cx = x; + +void +test01() +{ + Hash::count = 0; + Equal::count = 0; + + VERIFY( x.contains(1L) ); + + auto it = x.find(1L); + VERIFY( it != x.end() && it->second == '2' ); + it = x.find(2L); + VERIFY( it == x.end() ); + + auto cit = cx.find(3L); + VERIFY( cit != cx.end() && cit->second == '4' ); + cit = cx.find(2L); + VERIFY( cit == cx.end() ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); + + static_assert(std::is_same::value, + "find returns iterator"); + static_assert(std::is_same::value, + "const find returns const_iterator"); +} + +void +test02() +{ + Hash::count = 0; + Equal::count = 0; + + auto n = x.count(1L); + VERIFY( n == 1 ); + n = x.count(2L); + VERIFY( n == 0 ); + + auto cn = cx.count(3L); + VERIFY( cn == 1 ); + cn = cx.count(2L); + VERIFY( cn == 0 ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); +} + +void +test03() +{ + Hash::count = 0; + Equal::count = 0; + + auto it = x.equal_range(1L); + VERIFY( it.first != it.second && it.first->second == '2' ); + it = x.equal_range(2L); + VERIFY( it.first == it.second && it.first == x.end() ); + + auto cit = cx.equal_range(1L); + VERIFY( cit.first != cit.second && cit.first->second == '2' ); + cit = cx.equal_range(2L); + VERIFY( cit.first == cit.second && cit.first == cx.end() ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); + + using pair = std::pair; + static_assert(std::is_same::value, + "equal_range returns pair"); + using cpair = std::pair; + static_assert(std::is_same::value, + "const equal_range returns pair"); +} + +void +test04() +{ + struct E + { + bool operator()(int l, int r) const { return l == r; } + + struct Partition { }; + + bool operator()(int l, Partition) const { return l < 6; } + bool operator()(Partition, int r) const { return 3 < r; } + + using is_transparent = void; + }; + + struct H + { + size_t + operator()(int x) const + { return 0; } + + size_t + operator()(E::Partition) const + { return 0; } + + using is_transparent = void; + }; + + std::unordered_map m{ {1,0}, {2,0}, {3,0}, {4, 0}, {5, 0} }; + + auto n = m.count(E::Partition{}); + VERIFY( n == 2 ); +} + +int +main() +{ + test01(); + test02(); + test03(); + test04(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/operations/1.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/operations/1.cc new file mode 100644 index 00000000000..28d8233076b --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/operations/1.cc @@ -0,0 +1,135 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-do run { target c++20 } } + +#include +#include + +struct Equal +{ + typedef void is_transparent; + + bool operator()(int i, long l) const { return i == l; } + bool operator()(long l, int i) const { return l == i; } + bool operator()(int i, int j) const { ++count; return i == j; } + + static int count; +}; + +int Equal::count = 0; + +struct Hash +{ + typedef void is_transparent; + + std::size_t operator()(int i) const { ++count; return i; } + std::size_t operator()(long l) const { return l; } + + static int count; +}; + +int Hash::count = 0; + +using test_type = std::unordered_multimap; + +test_type x{ { 1, '2' }, { 3, '4' }, { 3, '5' } }; +const test_type& cx = x; + +void +test01() +{ + Hash::count = 0; + Equal::count = 0; + + VERIFY( x.contains(1L) ); + + auto it = x.find(1L); + VERIFY( it != x.end() && it->second == '2' ); + it = x.find(2L); + VERIFY( it == x.end() ); + + auto cit = cx.find(3L); + VERIFY( cit != cx.end() && cit->second == '5' ); + cit = cx.find(2L); + VERIFY( cit == cx.end() ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); + + static_assert(std::is_same::value, + "find returns iterator"); + static_assert(std::is_same::value, + "const find returns const_iterator"); +} + +void +test02() +{ + Hash::count = 0; + Equal::count = 0; + + auto n = x.count(1L); + VERIFY( n == 1 ); + n = x.count(2L); + VERIFY( n == 0 ); + + auto cn = cx.count(3L); + VERIFY( cn == 2 ); + cn = cx.count(2L); + VERIFY( cn == 0 ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); +} + +void +test03() +{ + Hash::count = 0; + Equal::count = 0; + + auto it = x.equal_range(1L); + VERIFY( it.first != it.second && it.first->second == '2' ); + it = x.equal_range(2L); + VERIFY( it.first == it.second && it.first == x.end() ); + + auto cit = cx.equal_range(3L); + VERIFY( cit.first != cit.second && cit.first->second == '5' ); + VERIFY( std::distance(cit.first, cit.second) == 2 ); + cit = cx.equal_range(2L); + VERIFY( cit.first == cit.second && cit.first == cx.end() ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); + + using pair = std::pair; + static_assert(std::is_same::value, + "equal_range returns pair"); + using cpair = std::pair; + static_assert(std::is_same::value, + "const equal_range returns pair"); +} + + +int +main() +{ + test01(); + test02(); + test03(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/operations/1.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/operations/1.cc new file mode 100644 index 00000000000..98a1c5b68de --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/operations/1.cc @@ -0,0 +1,135 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-do run { target c++20 } } + +#include +#include + +struct Equal +{ + typedef void is_transparent; + + bool operator()(int i, long l) const { return i == l; } + bool operator()(long l, int i) const { return l == i; } + bool operator()(int i, int j) const { ++count; return i == j; } + + static int count; +}; + +int Equal::count = 0; + +struct Hash +{ + typedef void is_transparent; + + std::size_t operator()(int i) const { ++count; return i; } + std::size_t operator()(long l) const { return l; } + + static int count; +}; + +int Hash::count = 0; + +using test_type = std::unordered_multiset; + +test_type x{ 1, 3, 3, 5 }; +const test_type& cx = x; + +void +test01() +{ + Hash::count = 0; + Equal::count = 0; + + VERIFY( x.contains(1L) ); + + auto it = x.find(1L); + VERIFY( it != x.end() && *it == 1 ); + it = x.find(2L); + VERIFY( it == x.end() ); + + auto cit = cx.find(3L); + VERIFY( cit != cx.end() && *cit == 3 ); + cit = cx.find(2L); + VERIFY( cit == cx.end() ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); + + static_assert(std::is_same::value, + "find returns iterator"); + static_assert(std::is_same::value, + "const find returns const_iterator"); +} + +void +test02() +{ + Hash::count = 0; + Equal::count = 0; + + auto n = x.count(1L); + VERIFY( n == 1 ); + n = x.count(2L); + VERIFY( n == 0 ); + + auto cn = cx.count(3L); + VERIFY( cn == 2 ); + cn = cx.count(2L); + VERIFY( cn == 0 ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); +} + +void +test03() +{ + Hash::count = 0; + Equal::count = 0; + + auto it = x.equal_range(1L); + VERIFY( it.first != it.second && *it.first == 1 ); + it = x.equal_range(2L); + VERIFY( it.first == it.second && it.first == x.end() ); + + auto cit = cx.equal_range(3L); + VERIFY( cit.first != cit.second && *cit.first == 3 ); + VERIFY( std::distance(cit.first, cit.second) == 2 ); + cit = cx.equal_range(2L); + VERIFY( cit.first == cit.second && cit.first == cx.end() ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); + + using pair = std::pair; + static_assert(std::is_same::value, + "equal_range returns pair"); + using cpair = std::pair; + static_assert(std::is_same::value, + "const equal_range returns pair"); +} + + +int +main() +{ + test01(); + test02(); + test03(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/operations/1.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/operations/1.cc new file mode 100644 index 00000000000..3498198ff6e --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/operations/1.cc @@ -0,0 +1,186 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-do run { target c++20 } } + +#include +#include + +struct Equal +{ + typedef void is_transparent; + + bool operator()(int i, long l) const { return i == l; } + bool operator()(long l, int i) const { return l == i; } + bool operator()(int i, int j) const { ++count; return i == j; } + + static int count; +}; + +int Equal::count = 0; + +struct Hash +{ + typedef void is_transparent; + + std::size_t operator()(int i) const { ++count; return i; } + std::size_t operator()(long l) const { return l; } + + static int count; +}; + +int Hash::count = 0; + +using test_type = std::unordered_set; + +test_type x{ 1, 3, 5 }; +const test_type& cx = x; + +void +test01() +{ + Hash::count = 0; + Equal::count = 0; + + VERIFY( x.contains(1L) ); + + auto it = x.find(1L); + VERIFY( it != x.end() && *it == 1 ); + it = x.find(2L); + VERIFY( it == x.end() ); + + auto cit = cx.find(3L); + VERIFY( cit != cx.end() && *cit == 3 ); + cit = cx.find(2L); + VERIFY( cit == cx.end() ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); + + static_assert(std::is_same::value, + "find returns iterator"); + static_assert(std::is_same::value, + "const find returns const_iterator"); +} + +void +test02() +{ + Hash::count = 0; + Equal::count = 0; + + auto n = x.count(1L); + VERIFY( n == 1 ); + n = x.count(2L); + VERIFY( n == 0 ); + + auto cn = cx.count(3L); + VERIFY( cn == 1 ); + cn = cx.count(2L); + VERIFY( cn == 0 ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); +} + +void +test03() +{ + Hash::count = 0; + Equal::count = 0; + + auto it = x.equal_range(1L); + VERIFY( it.first != it.second && *it.first == 1 ); + it = x.equal_range(2L); + VERIFY( it.first == it.second && it.first == x.end() ); + + auto cit = cx.equal_range(1L); + VERIFY( cit.first != cit.second && *cit.first == 1 ); + cit = cx.equal_range(2L); + VERIFY( cit.first == cit.second && cit.first == cx.end() ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); + + using pair = std::pair; + static_assert(std::is_same::value, + "equal_range returns pair"); + using cpair = std::pair; + static_assert(std::is_same::value, + "const equal_range returns pair"); +} + +void +test04() +{ + // https://gcc.gnu.org/ml/libstdc++/2015-01/msg00176.html + // Verify the new function template overloads do not cause problems + // when the comparison function is not transparent. + struct I + { + int i; + operator int() const { return i; } + }; + + std::unordered_set s; + I i = { }; + s.find(i); +} + +void +test05() +{ + struct E + { + bool operator()(int l, int r) const { return l == r; } + + struct Partition { }; + + bool operator()(int l, Partition) const { return l < 6; } + bool operator()(Partition, int r) const { return r > 3; } + + using is_transparent = void; + }; + + struct H + { + size_t + operator()(int x) const + { return (size_t)(x / 10); } + + size_t + operator()(E::Partition) const + { return 0; } + + using is_transparent = void; + }; + + std::unordered_set s{ 1, 2, 3, 4, 5 }; + + auto n = s.count(E::Partition{}); + VERIFY( n == 2 ); +} + +int +main() +{ + test01(); + test02(); + test03(); + test04(); + test05(); +}