From patchwork Mon Jan 19 17:16:08 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Wakely X-Patchwork-Id: 430617 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 28229140213 for ; Tue, 20 Jan 2015 04:16:33 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; q=dns; s= default; b=I6PWW2Bjarl1iTqyKvB4EUXQW8nUZ3GjJUJ90sgTxf+hsTmzt+UME A7WkQ5q28un9A4igbRV6rc7Nk2Q/WPOgHunX8aIxl89MeeOxrZ26Tf7wmQKKEvDE vvTtRsf/sYqPbApilE2taj6HxEvCUzm2qrSCNX1+UD45yZsUGNA83Y= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; s= default; bh=hcMUNcPAe08A3ic77xicTEXIuGQ=; b=A9cgetZW/yJXe4OqqelW HRCBYAc67ljw+0DsXnxcWgPsSiNCCIXWVl831QL/8MpdNZM/EccC6Dn9Zlg3UkZT 0XgvjOSXScB39PSMCiYI9XW8famxQ9jLCTl6596nqf7+fpA5cDKM8MIb/I+2DkvF nNhERqzHkL8gEGZHa9TIFHM= Received: (qmail 20008 invoked by alias); 19 Jan 2015 17:16:22 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 19984 invoked by uid 89); 19 Jan 2015 17:16:19 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.0 required=5.0 tests=AWL, BAYES_00, SPF_HELO_PASS, SPF_PASS, T_RP_MATCHES_RCVD autolearn=ham version=3.3.2 X-Spam-User: qpsmtpd, 2 recipients X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-GCM-SHA384 encrypted) ESMTPS; Mon, 19 Jan 2015 17:16:12 +0000 Received: from int-mx14.intmail.prod.int.phx2.redhat.com (int-mx14.intmail.prod.int.phx2.redhat.com [10.5.11.27]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id t0JHGAe2026951 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=FAIL); Mon, 19 Jan 2015 12:16:11 -0500 Received: from localhost (ovpn-116-18.ams2.redhat.com [10.36.116.18]) by int-mx14.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id t0JHG8lW014132; Mon, 19 Jan 2015 12:16:09 -0500 Date: Mon, 19 Jan 2015 17:16:08 +0000 From: Jonathan Wakely To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: [patch] [C++14] Implement N3657: heterogeneous lookup in associative containers. Message-ID: <20150119171608.GM3360@redhat.com> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.23 (2014-03-12) This is the last missing piece of the C++14 library, as proposed in http://www.open-std.org/JTC1/sc22/wg21/docs/papers/2013/n3657.htm Tested x86_64-linux, *not* committed. commit 99d7d1ebce9f290220966e138ef9b9e741878917 Author: Jonathan Wakely Date: Mon Jan 19 17:05:34 2015 +0000 Implement N3657: heterogeneous lookup in associative containers. * include/bits/stl_map.h (map::find<>, map::count<>, map::lower_bound<>, map::upper_bound<>, map::equal_range<>): New member function templates to perform heterogeneous lookup. * include/bits/stl_multimap.h (multimap::find<>, multimap::count<>, multimap::lower_bound<>, multimap::upper_bound<>, multimap::equal_range<>): Likewise. * include/bits/stl_multiset.h (multiset::find<>, multiset::count<>, multiset::lower_bound<>, multiset::upper_bound<>, multiset::equal_range<>): Likewise. * include/bits/stl_set.h (set::find<>, set::count<>, set::lower_bound<>, set::upper_bound<>, set::equal_range<>): Likewise. * include/bits/stl_tree.h (_Rb_tree::_S_lower_bound_tr, _Rb_tree::_S_upper_bound_tr, _Rb_tree::_M_find_tr, _Rb_tree::_M_count_tr, _Rb_tree::_M_lower_bound_tr, _Rb_tree::_M_upper_bound_tr, _Rb_tree::_M_equal_range_tr): Likewise. * testsuite/23_containers/map/operations/2.cc: New. * testsuite/23_containers/multimap/operations/2.cc: New. * testsuite/23_containers/multiset/operations/2.cc: New. * testsuite/23_containers/set/operations/2.cc: New. diff --git a/libstdc++-v3/include/bits/stl_map.h b/libstdc++-v3/include/bits/stl_map.h index 3bac4e0..df18973 100644 --- a/libstdc++-v3/include/bits/stl_map.h +++ b/libstdc++-v3/include/bits/stl_map.h @@ -824,6 +824,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return value_compare(_M_t.key_comp()); } // [23.3.1.3] map operations + + //@{ /** * @brief Tries to locate an element in a %map. * @param __x Key of (key, value) %pair to be located. @@ -835,10 +837,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * pointing to the sought after %pair. If unsuccessful it returns the * past-the-end ( @c end() ) iterator. */ + iterator find(const key_type& __x) { return _M_t.find(__x); } +#if __cplusplus > 201103L + template + auto + find(const _Kt& __x) -> decltype(_M_t._M_find_tr(__x)) + { return _M_t._M_find_tr(__x); } +#endif + //@} + + //@{ /** * @brief Tries to locate an element in a %map. * @param __x Key of (key, value) %pair to be located. @@ -850,10 +862,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * iterator pointing to the sought after %pair. If unsuccessful it * returns the past-the-end ( @c end() ) iterator. */ + const_iterator find(const key_type& __x) const { return _M_t.find(__x); } +#if __cplusplus > 201103L + template + auto + find(const _Kt& __x) const -> decltype(_M_t._M_find_tr(__x)) + { return _M_t._M_find_tr(__x); } +#endif + //@} + + //@{ /** * @brief Finds the number of elements with given key. * @param __x Key of (key, value) pairs to be located. @@ -866,6 +888,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER count(const key_type& __x) const { return _M_t.find(__x) == _M_t.end() ? 0 : 1; } +#if __cplusplus > 201103L + template + auto + count(const _Kt& __x) const -> decltype(_M_t._M_count_tr(__x)) + { return _M_t._M_find_tr(__x) == _M_t.end() ? 0 : 1; } +#endif + //@} + + //@{ /** * @brief Finds the beginning of a subsequence matching given key. * @param __x Key of (key, value) pair to be located. @@ -881,6 +912,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER lower_bound(const key_type& __x) { return _M_t.lower_bound(__x); } +#if __cplusplus > 201103L + template + auto + lower_bound(const _Kt& __x) + -> decltype(_M_t._M_lower_bound_tr(__x)) + { return _M_t._M_lower_bound_tr(__x); } +#endif + //@} + + //@{ /** * @brief Finds the beginning of a subsequence matching given key. * @param __x Key of (key, value) pair to be located. @@ -896,6 +937,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER lower_bound(const key_type& __x) const { return _M_t.lower_bound(__x); } +#if __cplusplus > 201103L + template + auto + lower_bound(const _Kt& __x) const + -> decltype(_M_t._M_lower_bound_tr(__x)) + { return _M_t._M_lower_bound_tr(__x); } +#endif + //@} + + //@{ /** * @brief Finds the end of a subsequence matching given key. * @param __x Key of (key, value) pair to be located. @@ -906,6 +957,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER upper_bound(const key_type& __x) { return _M_t.upper_bound(__x); } +#if __cplusplus > 201103L + template + auto + upper_bound(const _Kt& __x) + -> decltype(_M_t._M_upper_bound_tr(__x)) + { return _M_t._M_upper_bound_tr(__x); } +#endif + //@} + + //@{ /** * @brief Finds the end of a subsequence matching given key. * @param __x Key of (key, value) pair to be located. @@ -916,6 +977,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER upper_bound(const key_type& __x) const { return _M_t.upper_bound(__x); } +#if __cplusplus > 201103L + template + auto + upper_bound(const _Kt& __x) const + -> decltype(_M_t._M_upper_bound_tr(__x)) + { return _M_t._M_upper_bound_tr(__x); } +#endif + //@} + + //@{ /** * @brief Finds a subsequence matching given key. * @param __x Key of (key, value) pairs to be located. @@ -935,6 +1006,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER equal_range(const key_type& __x) { return _M_t.equal_range(__x); } +#if __cplusplus > 201103L + template + auto + equal_range(const _Kt& __x) + -> decltype(_M_t._M_equal_range_tr(__x)) + { return _M_t._M_equal_range_tr(__x); } +#endif + //@} + + //@{ /** * @brief Finds a subsequence matching given key. * @param __x Key of (key, value) pairs to be located. @@ -954,6 +1035,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER equal_range(const key_type& __x) const { return _M_t.equal_range(__x); } +#if __cplusplus > 201103L + template + auto + equal_range(const _Kt& __x) const + -> decltype(_M_t._M_equal_range_tr(__x)) + { return _M_t._M_equal_range_tr(__x); } +#endif + //@} + template friend bool operator==(const map<_K1, _T1, _C1, _A1>&, diff --git a/libstdc++-v3/include/bits/stl_multimap.h b/libstdc++-v3/include/bits/stl_multimap.h index 5a81f8f..f3d21ab 100644 --- a/libstdc++-v3/include/bits/stl_multimap.h +++ b/libstdc++-v3/include/bits/stl_multimap.h @@ -734,6 +734,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return value_compare(_M_t.key_comp()); } // multimap operations + + //@{ /** * @brief Tries to locate an element in a %multimap. * @param __x Key of (key, value) pair to be located. @@ -749,6 +751,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER find(const key_type& __x) { return _M_t.find(__x); } +#if __cplusplus > 201103L + template + auto + find(const _Kt& __x) -> decltype(_M_t._M_find_tr(__x)) + { return _M_t._M_find_tr(__x); } +#endif + //@} + + //@{ /** * @brief Tries to locate an element in a %multimap. * @param __x Key of (key, value) pair to be located. @@ -764,6 +775,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER find(const key_type& __x) const { return _M_t.find(__x); } +#if __cplusplus > 201103L + template + auto + find(const _Kt& __x) const -> decltype(_M_t._M_find_tr(__x)) + { return _M_t._M_find_tr(__x); } +#endif + //@} + + //@{ /** * @brief Finds the number of elements with given key. * @param __x Key of (key, value) pairs to be located. @@ -773,6 +793,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER count(const key_type& __x) const { return _M_t.count(__x); } +#if __cplusplus > 201103L + template + auto + count(const _Kt& __x) const -> decltype(_M_t._M_count_tr(__x)) + { return _M_t._M_count_tr(__x); } +#endif + //@} + + //@{ /** * @brief Finds the beginning of a subsequence matching given key. * @param __x Key of (key, value) pair to be located. @@ -788,6 +817,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER lower_bound(const key_type& __x) { return _M_t.lower_bound(__x); } +#if __cplusplus > 201103L + template + auto + lower_bound(const _Kt& __x) + -> decltype(_M_t._M_lower_bound_tr(__x)) + { return _M_t._M_lower_bound_tr(__x); } +#endif + //@} + + //@{ /** * @brief Finds the beginning of a subsequence matching given key. * @param __x Key of (key, value) pair to be located. @@ -803,6 +842,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER lower_bound(const key_type& __x) const { return _M_t.lower_bound(__x); } +#if __cplusplus > 201103L + template + auto + lower_bound(const _Kt& __x) const + -> decltype(_M_t._M_lower_bound_tr(__x)) + { return _M_t._M_lower_bound_tr(__x); } +#endif + //@} + + //@{ /** * @brief Finds the end of a subsequence matching given key. * @param __x Key of (key, value) pair to be located. @@ -813,6 +862,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER upper_bound(const key_type& __x) { return _M_t.upper_bound(__x); } +#if __cplusplus > 201103L + template + auto + upper_bound(const _Kt& __x) + -> decltype(_M_t._M_upper_bound_tr(__x)) + { return _M_t._M_upper_bound_tr(__x); } +#endif + //@} + + //@{ /** * @brief Finds the end of a subsequence matching given key. * @param __x Key of (key, value) pair to be located. @@ -823,6 +882,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER upper_bound(const key_type& __x) const { return _M_t.upper_bound(__x); } +#if __cplusplus > 201103L + template + auto + upper_bound(const _Kt& __x) const + -> decltype(_M_t._M_upper_bound_tr(__x)) + { return _M_t._M_upper_bound_tr(__x); } +#endif + //@} + + //@{ /** * @brief Finds a subsequence matching given key. * @param __x Key of (key, value) pairs to be located. @@ -840,6 +909,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER equal_range(const key_type& __x) { return _M_t.equal_range(__x); } +#if __cplusplus > 201103L + template + auto + equal_range(const _Kt& __x) + -> decltype(_M_t._M_equal_range_tr(__x)) + { return _M_t._M_equal_range_tr(__x); } +#endif + //@} + + //@{ /** * @brief Finds a subsequence matching given key. * @param __x Key of (key, value) pairs to be located. @@ -857,6 +936,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER equal_range(const key_type& __x) const { return _M_t.equal_range(__x); } +#if __cplusplus > 201103L + template + auto + equal_range(const _Kt& __x) const + -> decltype(_M_t._M_equal_range_tr(__x)) + { return _M_t._M_equal_range_tr(__x); } +#endif + //@} + template friend bool operator==(const multimap<_K1, _T1, _C1, _A1>&, diff --git a/libstdc++-v3/include/bits/stl_multiset.h b/libstdc++-v3/include/bits/stl_multiset.h index be04221..7e92836 100644 --- a/libstdc++-v3/include/bits/stl_multiset.h +++ b/libstdc++-v3/include/bits/stl_multiset.h @@ -636,6 +636,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER // multiset operations: + //@{ /** * @brief Finds the number of elements with given key. * @param __x Key of elements to be located. @@ -645,6 +646,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER count(const key_type& __x) const { return _M_t.count(__x); } +#if __cplusplus > 201103L + template + auto + count(const _Kt& __x) const -> decltype(_M_t._M_count_tr(__x)) + { return _M_t._M_count_tr(__x); } +#endif + //@} + // _GLIBCXX_RESOLVE_LIB_DEFECTS // 214. set::find() missing const overload //@{ @@ -666,6 +675,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER const_iterator find(const key_type& __x) const { return _M_t.find(__x); } + +#if __cplusplus > 201103L + template + auto + find(const _Kt& __x) -> decltype(_M_t._M_find_tr(__x)) + { return _M_t._M_find_tr(__x); } + + template + auto + find(const _Kt& __x) const -> decltype(_M_t._M_find_tr(__x)) + { return _M_t._M_find_tr(__x); } +#endif //@} //@{ @@ -687,6 +708,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER const_iterator lower_bound(const key_type& __x) const { return _M_t.lower_bound(__x); } + +#if __cplusplus > 201103L + template + auto + lower_bound(const _Kt& __x) + -> decltype(_M_t._M_lower_bound_tr(__x)) + { return _M_t._M_lower_bound_tr(__x); } + + template + auto + lower_bound(const _Kt& __x) const + -> decltype(_M_t._M_lower_bound_tr(__x)) + { return _M_t._M_lower_bound_tr(__x); } +#endif //@} //@{ @@ -703,6 +738,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER const_iterator upper_bound(const key_type& __x) const { return _M_t.upper_bound(__x); } + +#if __cplusplus > 201103L + template + auto + upper_bound(const _Kt& __x) + -> decltype(_M_t._M_upper_bound_tr(__x)) + { return _M_t._M_upper_bound_tr(__x); } + + template + auto + upper_bound(const _Kt& __x) const + -> decltype(_M_t._M_upper_bound_tr(__x)) + { return _M_t._M_upper_bound_tr(__x); } +#endif //@} //@{ @@ -728,6 +777,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER std::pair equal_range(const key_type& __x) const { return _M_t.equal_range(__x); } + +#if __cplusplus > 201103L + template + auto + equal_range(const _Kt& __x) + -> decltype(_M_t._M_equal_range_tr(__x)) + { return _M_t._M_equal_range_tr(__x); } + + template + auto + equal_range(const _Kt& __x) const + -> decltype(_M_t._M_equal_range_tr(__x)) + { return _M_t._M_equal_range_tr(__x); } +#endif //@} template diff --git a/libstdc++-v3/include/bits/stl_set.h b/libstdc++-v3/include/bits/stl_set.h index 3944bcd..5189234 100644 --- a/libstdc++-v3/include/bits/stl_set.h +++ b/libstdc++-v3/include/bits/stl_set.h @@ -651,6 +651,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER // set operations: + //@{ /** * @brief Finds the number of elements. * @param __x Element to located. @@ -663,6 +664,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER count(const key_type& __x) const { return _M_t.find(__x) == _M_t.end() ? 0 : 1; } +#if __cplusplus > 201103L + template + auto + count(const _Kt& __x) const + -> decltype(_M_t._M_count_tr(__x)) + { return _M_t._M_find_tr(__x) == _M_t.end() ? 0 : 1; } +#endif + //@} + // _GLIBCXX_RESOLVE_LIB_DEFECTS // 214. set::find() missing const overload //@{ @@ -684,6 +694,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER const_iterator find(const key_type& __x) const { return _M_t.find(__x); } + +#if __cplusplus > 201103L + template + auto + find(const _Kt& __x) -> decltype(_M_t._M_find_tr(__x)) + { return _M_t._M_find_tr(__x); } + + template + auto + find(const _Kt& __x) const -> decltype(_M_t._M_find_tr(__x)) + { return _M_t._M_find_tr(__x); } +#endif //@} //@{ @@ -705,6 +727,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER const_iterator lower_bound(const key_type& __x) const { return _M_t.lower_bound(__x); } + +#if __cplusplus > 201103L + template + auto + lower_bound(const _Kt& __x) + -> decltype(_M_t._M_lower_bound_tr(__x)) + { return _M_t._M_lower_bound_tr(__x); } + + template + auto + lower_bound(const _Kt& __x) const + -> decltype(_M_t._M_lower_bound_tr(__x)) + { return _M_t._M_lower_bound_tr(__x); } +#endif //@} //@{ @@ -721,6 +757,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER const_iterator upper_bound(const key_type& __x) const { return _M_t.upper_bound(__x); } + +#if __cplusplus > 201103L + template + auto + upper_bound(const _Kt& __x) + -> decltype(_M_t._M_upper_bound_tr(__x)) + { return _M_t._M_upper_bound_tr(__x); } + + template + auto + upper_bound(const _Kt& __x) const + -> decltype(_M_t._M_upper_bound_tr(__x)) + { return _M_t._M_upper_bound_tr(__x); } +#endif //@} //@{ @@ -746,6 +796,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER std::pair equal_range(const key_type& __x) const { return _M_t.equal_range(__x); } + +#if __cplusplus > 201103L + template + auto + equal_range(const _Kt& __x) + -> decltype(_M_t._M_equal_range_tr(__x)) + { return _M_t._M_equal_range_tr(__x); } + + template + auto + equal_range(const _Kt& __x) const + -> decltype(_M_t._M_equal_range_tr(__x)) + { return _M_t._M_equal_range_tr(__x); } +#endif //@} template diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h index e78b2db..5ca8e28 100644 --- a/libstdc++-v3/include/bits/stl_tree.h +++ b/libstdc++-v3/include/bits/stl_tree.h @@ -1118,6 +1118,137 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION pair equal_range(const key_type& __k) const; +#if __cplusplus > 201103L + template> + struct __is_transparent { }; + + template + struct + __is_transparent<_Cmp, _Kt, __void_t> + { typedef void type; }; + + static auto _S_iter(_Link_type __x) { return iterator(__x); } + + static auto _S_iter(_Const_Link_type __x) { return const_iterator(__x); } + + template + static auto + _S_lower_bound_tr(_Cmp& __cmp, _Link __x, _Link __y, const _Kt& __k) + { + while (__x != 0) + if (!__cmp(_S_key(__x), __k)) + __y = __x, __x = _S_left(__x); + else + __x = _S_right(__x); + return _S_iter(__y); + } + + template + static auto + _S_upper_bound_tr(_Cmp& __cmp, _Link __x, _Link __y, const _Kt& __k) + { + while (__x != 0) + if (__cmp(__k, _S_key(__x))) + __y = __x, __x = _S_left(__x); + else + __x = _S_right(__x); + return _S_iter(__y); + } + + template::type> + iterator + _M_find_tr(const _Kt& __k) + { + auto& __cmp = _M_impl._M_key_compare; + auto __j = _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k); + return (__j == end() || __cmp(__k, _S_key(__j._M_node))) + ? end() : __j; + } + + template::type> + const_iterator + _M_find_tr(const _Kt& __k) const + { + auto& __cmp = _M_impl._M_key_compare; + auto __j = _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k); + return (__j == end() || __cmp(__k, _S_key(__j._M_node))) + ? end() : __j; + } + + template::type> + size_type + _M_count_tr(const _Kt& __k) const + { + auto __p = _M_equal_range_tr(__k); + return std::distance(__p.first, __p.second); + } + + template::type> + iterator + _M_lower_bound_tr(const _Kt& __k) + { + auto& __cmp = _M_impl._M_key_compare; + return _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k); + } + + template::type> + const_iterator + _M_lower_bound_tr(const _Kt& __k) const + { + auto& __cmp = _M_impl._M_key_compare; + return _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k); + } + + template::type> + iterator + _M_upper_bound_tr(const _Kt& __k) + { + auto& __cmp = _M_impl._M_key_compare; + return _S_upper_bound_tr(__cmp, _M_begin(), _M_end(), __k); + } + + template::type> + const_iterator + _M_upper_bound_tr(const _Kt& __k) const + { + auto& __cmp = _M_impl._M_key_compare; + return _S_upper_bound_tr(__cmp, _M_begin(), _M_end(), __k); + } + + template::type> + pair + _M_equal_range_tr(const _Kt& __k) + { + auto __low = _M_lower_bound_tr(__k); + auto __high = __low; + auto& __cmp = _M_impl._M_key_compare; + while (__high != end() && !__cmp(__k, _S_key(__high._M_node))) + ++__high; + return { __low, __high }; + } + + template::type> + pair + _M_equal_range_tr(const _Kt& __k) const + { + auto __low = _M_lower_bound_tr(__k); + auto __high = __low; + auto& __cmp = _M_impl._M_key_compare; + while (__high != end() && !__cmp(__k, _S_key(__high._M_node))) + ++__high; + return { __low, __high }; + } +#endif + // Debugging. bool __rb_verify() const; diff --git a/libstdc++-v3/testsuite/23_containers/map/operations/2.cc b/libstdc++-v3/testsuite/23_containers/map/operations/2.cc new file mode 100644 index 0000000..6cc277a --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/map/operations/2.cc @@ -0,0 +1,140 @@ +// Copyright (C) 2015 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-options "-std=gnu++14" } + +#include +#include + +struct Cmp +{ + 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 Cmp::count = 0; + +using test_type = std::map; + +test_type x{ { 1, '2' }, { 3, '4' } }; +const test_type& cx = x; + +void +test01() +{ + Cmp::count = 0; + + 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( Cmp::count == 0); +} + +void +test02() +{ + Cmp::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( Cmp::count == 0); +} + +void +test03() +{ + Cmp::count = 0; + + auto it = x.lower_bound(1L); + VERIFY( it != x.end() && it->second == '2' ); + it = x.lower_bound(2L); + VERIFY( it != x.end() && it->second == '4' ); + + auto cit = cx.lower_bound(1L); + VERIFY( cit != cx.end() && cit->second == '2' ); + cit = cx.lower_bound(2L); + VERIFY( cit != cx.end() && cit->second == '4' ); + + VERIFY( Cmp::count == 0); +} + +void +test04() +{ + Cmp::count = 0; + + auto it = x.upper_bound(1L); + VERIFY( it != x.end() && it->second == '4' ); + it = x.upper_bound(3L); + VERIFY( it == x.end() ); + + auto cit = cx.upper_bound(1L); + VERIFY( cit != cx.end() && cit->second == '4' ); + cit = cx.upper_bound(3L); + VERIFY( cit == cx.end() ); + + VERIFY( Cmp::count == 0); +} + +void +test05() +{ + Cmp::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( Cmp::count == 0); +} + + +int +main() +{ + test01(); + test02(); + test03(); + test04(); + test05(); +} diff --git a/libstdc++-v3/testsuite/23_containers/multimap/operations/2.cc b/libstdc++-v3/testsuite/23_containers/multimap/operations/2.cc new file mode 100644 index 0000000..67c3bfd --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/multimap/operations/2.cc @@ -0,0 +1,141 @@ +// Copyright (C) 2015 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-options "-std=gnu++14" } + +#include +#include + +struct Cmp +{ + 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 Cmp::count = 0; + +using test_type = std::multimap; + +test_type x{ { 1, '2' }, { 3, '4' }, { 3, '5' } }; +const test_type& cx = x; + +void +test01() +{ + Cmp::count = 0; + + 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( Cmp::count == 0); +} + +void +test02() +{ + Cmp::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( Cmp::count == 0); +} + +void +test03() +{ + Cmp::count = 0; + + auto it = x.lower_bound(1L); + VERIFY( it != x.end() && it->second == '2' ); + it = x.lower_bound(2L); + VERIFY( it != x.end() && it->second == '4' ); + + auto cit = cx.lower_bound(1L); + VERIFY( cit != cx.end() && cit->second == '2' ); + cit = cx.lower_bound(2L); + VERIFY( cit != cx.end() && cit->second == '4' ); + + VERIFY( Cmp::count == 0); +} + +void +test04() +{ + Cmp::count = 0; + + auto it = x.upper_bound(1L); + VERIFY( it != x.end() && it->second == '4' ); + it = x.upper_bound(3L); + VERIFY( it == x.end() ); + + auto cit = cx.upper_bound(1L); + VERIFY( cit != cx.end() && cit->second == '4' ); + cit = cx.upper_bound(3L); + VERIFY( cit == cx.end() ); + + VERIFY( Cmp::count == 0); +} + +void +test05() +{ + Cmp::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 == '4' ); + VERIFY( std::distance(cit.first, cit.second) == 2 ); + cit = cx.equal_range(2L); + VERIFY( cit.first == cit.second && cit.first != cx.end() ); + + VERIFY( Cmp::count == 0); +} + + +int +main() +{ + test01(); + test02(); + test03(); + test04(); + test05(); +} diff --git a/libstdc++-v3/testsuite/23_containers/multiset/operations/2.cc b/libstdc++-v3/testsuite/23_containers/multiset/operations/2.cc new file mode 100644 index 0000000..ff2748f --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/multiset/operations/2.cc @@ -0,0 +1,141 @@ +// Copyright (C) 2015 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-options "-std=gnu++14" } + +#include +#include + +struct Cmp +{ + 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 Cmp::count = 0; + +using test_type = std::multiset; + +test_type x{ 1, 3, 3, 5 }; +const test_type& cx = x; + +void +test01() +{ + Cmp::count = 0; + + 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( Cmp::count == 0); +} + +void +test02() +{ + Cmp::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( Cmp::count == 0); +} + +void +test03() +{ + Cmp::count = 0; + + auto it = x.lower_bound(1L); + VERIFY( it != x.end() && *it == 1 ); + it = x.lower_bound(2L); + VERIFY( it != x.end() && *it == 3 ); + + auto cit = cx.lower_bound(1L); + VERIFY( cit != cx.end() && *cit == 1 ); + cit = cx.lower_bound(2L); + VERIFY( cit != cx.end() && *cit == 3 ); + + VERIFY( Cmp::count == 0); +} + +void +test04() +{ + Cmp::count = 0; + + auto it = x.upper_bound(1L); + VERIFY( it != x.end() && *it == 3 ); + it = x.upper_bound(5L); + VERIFY( it == x.end() ); + + auto cit = cx.upper_bound(1L); + VERIFY( cit != cx.end() && *cit == 3 ); + cit = cx.upper_bound(5L); + VERIFY( cit == cx.end() ); + + VERIFY( Cmp::count == 0); +} + +void +test05() +{ + Cmp::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( Cmp::count == 0); +} + + +int +main() +{ + test01(); + test02(); + test03(); + test04(); + test05(); +} diff --git a/libstdc++-v3/testsuite/23_containers/set/operations/2.cc b/libstdc++-v3/testsuite/23_containers/set/operations/2.cc new file mode 100644 index 0000000..752bc7d --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/set/operations/2.cc @@ -0,0 +1,140 @@ +// Copyright (C) 2015 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-options "-std=gnu++14" } + +#include +#include + +struct Cmp +{ + 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 Cmp::count = 0; + +using test_type = std::set; + +test_type x{ 1, 3, 5 }; +const test_type& cx = x; + +void +test01() +{ + Cmp::count = 0; + + 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( Cmp::count == 0); +} + +void +test02() +{ + Cmp::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( Cmp::count == 0); +} + +void +test03() +{ + Cmp::count = 0; + + auto it = x.lower_bound(1L); + VERIFY( it != x.end() && *it == 1 ); + it = x.lower_bound(2L); + VERIFY( it != x.end() && *it == 3 ); + + auto cit = cx.lower_bound(1L); + VERIFY( cit != cx.end() && *cit == 1 ); + cit = cx.lower_bound(2L); + VERIFY( cit != cx.end() && *cit == 3 ); + + VERIFY( Cmp::count == 0); +} + +void +test04() +{ + Cmp::count = 0; + + auto it = x.upper_bound(1L); + VERIFY( it != x.end() && *it == 3 ); + it = x.upper_bound(5L); + VERIFY( it == x.end() ); + + auto cit = cx.upper_bound(1L); + VERIFY( cit != cx.end() && *cit == 3 ); + cit = cx.upper_bound(5L); + VERIFY( cit == cx.end() ); + + VERIFY( Cmp::count == 0); +} + +void +test05() +{ + Cmp::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( Cmp::count == 0); +} + + +int +main() +{ + test01(); + test02(); + test03(); + test04(); + test05(); +}