From patchwork Fri Jun 5 21:00:06 2015 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: 481563 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 82868140129 for ; Sat, 6 Jun 2015 07:00:37 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=M3mUppN7; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:date:from:mime-version:to:cc:subject:references :in-reply-to:content-type; q=dns; s=default; b=JHR5R6vc3MNZ14m9k xtuAMfX5srYofy2Hq68wmjWJghNs3PLPHS5YzZyrefOMjPt1jTBMVp+3auawzPqF TTsrRYFY+w6ktyVxk1yccFGd+X0+lAtN5t/gkLNUHfIhuu19L2ljbzPI6hlxpT0e 1sypRdZ6gEsjueZ03ET/ot7sbQ= 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 :message-id:date:from:mime-version:to:cc:subject:references :in-reply-to:content-type; s=default; bh=CJB6rTI9zzsrcxNEuK4TwW1 Q6xA=; b=M3mUppN7rlCvclrU0HaCkpynoi/eTSWpZztFYZWEEiZEAAwoTYDdd5h ev6JaKH4lXRO6CfOUt8/26wbdMNqHLd44dHiPKJ60JU3cIrMlwYg44E9CFePgUaX WFVVb5N7YwFNK5nzYUrdTb4tks7ot/0ez0MOnQZzOsF/T5maXN84= Received: (qmail 51620 invoked by alias); 5 Jun 2015 21:00:16 -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 51599 invoked by uid 89); 5 Jun 2015 21:00:15 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=0.7 required=5.0 tests=AWL, BAYES_99, BAYES_999, FREEMAIL_FROM, KAM_ASCII_DIVIDERS, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=no version=3.3.2 X-Spam-User: qpsmtpd, 2 recipients X-HELO: mail-wi0-f170.google.com Received: from mail-wi0-f170.google.com (HELO mail-wi0-f170.google.com) (209.85.212.170) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Fri, 05 Jun 2015 21:00:11 +0000 Received: by wiga1 with SMTP id a1so32538684wig.0; Fri, 05 Jun 2015 14:00:08 -0700 (PDT) X-Received: by 10.194.203.138 with SMTP id kq10mr911095wjc.124.1433538008434; Fri, 05 Jun 2015 14:00:08 -0700 (PDT) Received: from [192.168.0.22] (arf62-1-82-237-250-248.fbx.proxad.net. [82.237.250.248]) by mx.google.com with ESMTPSA id n1sm4922133wix.0.2015.06.05.14.00.06 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 05 Jun 2015 14:00:07 -0700 (PDT) Message-ID: <55720DD6.9020002@gmail.com> Date: Fri, 05 Jun 2015 23:00:06 +0200 From: =?windows-1252?Q?Fran=E7ois_Dumont?= User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.7.0 MIME-Version: 1.0 To: Jonathan Wakely CC: "libstdc++@gcc.gnu.org" , gcc-patches Subject: Re: Add tree heterogeneous lookup in alternative modes References: <556F5C07.2060102@gmail.com> <20150604124131.GF12728@redhat.com> In-Reply-To: <20150604124131.GF12728@redhat.com> On 04/06/2015 14:41, Jonathan Wakely wrote: > On 03/06/15 21:56 +0200, François Dumont wrote: >> Hi >> >> Here is a patch to add heterogeneous lookup to alternative modes. > > Excellent. > >> To do so I had to expose __is_transparent as __has_is_transparent to >> avoid confilct with existing __is_transparent. > > That's a better name, thanks. > > >> Should I put it in __detail namespace ? > > Could it just be protected instead of at namespace scope? No, debug containers are inheriting from normal containers, not from _Rb_tree. > > If it can't be protected it's OK here you put it, it doesn't need to > be in __detail. > > But maybe we should rename the _Kt parameter of __hash_is_transparent > to _Unused, _Dummy or something like that. It only exists to make the > specialization dependent on a template argument of the functions that > use it. > I renamed it into _SfinaeType to make the purpose of this type clearer. > >> * include/bits/stl_tree.h (_Rb_tree<>::__is_transparent<>): Move to >> outer scope and rename in ... > > "rename to ..." not "rename into..." :-) > >> (std::__hash_is_transparent<>): ... this. > > In ... > >> @@ -429,12 +477,34 @@ >> std::pair >> equal_range(const key_type& __x) const >> { >> - std::pair<_Base_iterator, _Base_iterator> __res = >> + std::pair<_Base_const_iterator, _Base_const_iterator> __res = >> _Base::equal_range(__x); >> return std::make_pair(const_iterator(__res.first, this), >> const_iterator(__res.second, this)); >> } > > Huh! Did calls to this function even compile before this fix? I had a closer look and yes, it was compiling because for set iterator and const_iterator are just the same: // DR 103. set::iterator is required to be modifiable, // but this allows modification of keys. typedef typename _Rep_type::const_iterator iterator; typedef typename _Rep_type::const_iterator const_iterator; However I slightly changed some tests to make sure the const version of equal_range and some others are used. If it is still fine I will commit the attached patch tomorrow. François Index: include/bits/stl_tree.h =================================================================== --- include/bits/stl_tree.h (revision 224099) +++ include/bits/stl_tree.h (working copy) @@ -341,7 +341,17 @@ _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z, _Rb_tree_node_base& __header) throw (); +#if __cplusplus > 201103L + template> + struct __has_is_transparent + { }; + template + struct __has_is_transparent<_Cmp, _SfinaeType, + __void_t> + { typedef void type; }; +#endif + template > class _Rb_tree @@ -1109,16 +1119,9 @@ 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; }; - template::type> + typename _Req = + typename __has_is_transparent<_Compare, _Kt>::type> iterator _M_find_tr(const _Kt& __k) { @@ -1127,7 +1130,8 @@ } template::type> + typename _Req = + typename __has_is_transparent<_Compare, _Kt>::type> const_iterator _M_find_tr(const _Kt& __k) const { @@ -1138,7 +1142,8 @@ } template::type> + typename _Req = + typename __has_is_transparent<_Compare, _Kt>::type> size_type _M_count_tr(const _Kt& __k) const { @@ -1147,7 +1152,8 @@ } template::type> + typename _Req = + typename __has_is_transparent<_Compare, _Kt>::type> iterator _M_lower_bound_tr(const _Kt& __k) { @@ -1156,7 +1162,8 @@ } template::type> + typename _Req = + typename __has_is_transparent<_Compare, _Kt>::type> const_iterator _M_lower_bound_tr(const _Kt& __k) const { @@ -1174,7 +1181,8 @@ } template::type> + typename _Req = + typename __has_is_transparent<_Compare, _Kt>::type> iterator _M_upper_bound_tr(const _Kt& __k) { @@ -1183,7 +1191,8 @@ } template::type> + typename _Req = + typename __has_is_transparent<_Compare, _Kt>::type> const_iterator _M_upper_bound_tr(const _Kt& __k) const { @@ -1201,7 +1210,8 @@ } template::type> + typename _Req = + typename __has_is_transparent<_Compare, _Kt>::type> pair _M_equal_range_tr(const _Kt& __k) { @@ -1211,7 +1221,8 @@ } template::type> + typename _Req = + typename __has_is_transparent<_Compare, _Kt>::type> pair _M_equal_range_tr(const _Kt& __k) const { Index: include/debug/map.h =================================================================== --- include/debug/map.h (revision 224099) +++ include/debug/map.h (working copy) @@ -412,10 +412,28 @@ find(const key_type& __x) { return iterator(_Base::find(__x), this); } +#if __cplusplus > 201103L + template::type> + iterator + find(const _Kt& __x) + { return { _Base::find(__x), this }; } +#endif + const_iterator find(const key_type& __x) const { return const_iterator(_Base::find(__x), this); } +#if __cplusplus > 201103L + template::type> + const_iterator + find(const _Kt& __x) const + { return { _Base::find(__x), this }; } +#endif + using _Base::count; iterator @@ -422,18 +440,54 @@ lower_bound(const key_type& __x) { return iterator(_Base::lower_bound(__x), this); } +#if __cplusplus > 201103L + template::type> + iterator + lower_bound(const _Kt& __x) + { return { _Base::lower_bound(__x), this }; } +#endif + const_iterator lower_bound(const key_type& __x) const { return const_iterator(_Base::lower_bound(__x), this); } +#if __cplusplus > 201103L + template::type> + const_iterator + lower_bound(const _Kt& __x) const + { return { _Base::lower_bound(__x), this }; } +#endif + iterator upper_bound(const key_type& __x) { return iterator(_Base::upper_bound(__x), this); } +#if __cplusplus > 201103L + template::type> + iterator + upper_bound(const _Kt& __x) + { return { _Base::upper_bound(__x), this }; } +#endif + const_iterator upper_bound(const key_type& __x) const { return const_iterator(_Base::upper_bound(__x), this); } +#if __cplusplus > 201103L + template::type> + const_iterator + upper_bound(const _Kt& __x) const + { return { _Base::upper_bound(__x), this }; } +#endif + std::pair equal_range(const key_type& __x) { @@ -443,6 +497,18 @@ iterator(__res.second, this)); } +#if __cplusplus > 201103L + template::type> + std::pair + equal_range(const _Kt& __x) + { + auto __res = _Base::equal_range(__x); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + std::pair equal_range(const key_type& __x) const { @@ -452,6 +518,18 @@ const_iterator(__res.second, this)); } +#if __cplusplus > 201103L + template::type> + std::pair + equal_range(const _Kt& __x) const + { + auto __res = _Base::equal_range(__x); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + _Base& _M_base() _GLIBCXX_NOEXCEPT { return *this; } Index: include/debug/multimap.h =================================================================== --- include/debug/multimap.h (revision 224099) +++ include/debug/multimap.h (working copy) @@ -393,10 +393,28 @@ find(const key_type& __x) { return iterator(_Base::find(__x), this); } +#if __cplusplus > 201103L + template::type> + iterator + find(const _Kt& __x) + { return { _Base::find(__x), this }; } +#endif + const_iterator find(const key_type& __x) const { return const_iterator(_Base::find(__x), this); } +#if __cplusplus > 201103L + template::type> + const_iterator + find(const _Kt& __x) const + { return { _Base::find(__x), this }; } +#endif + using _Base::count; iterator @@ -403,18 +421,54 @@ lower_bound(const key_type& __x) { return iterator(_Base::lower_bound(__x), this); } +#if __cplusplus > 201103L + template::type> + iterator + lower_bound(const _Kt& __x) + { return { _Base::lower_bound(__x), this }; } +#endif + const_iterator lower_bound(const key_type& __x) const { return const_iterator(_Base::lower_bound(__x), this); } +#if __cplusplus > 201103L + template::type> + const_iterator + lower_bound(const _Kt& __x) const + { return { _Base::lower_bound(__x), this }; } +#endif + iterator upper_bound(const key_type& __x) { return iterator(_Base::upper_bound(__x), this); } +#if __cplusplus > 201103L + template::type> + iterator + upper_bound(const _Kt& __x) + { return { _Base::upper_bound(__x), this }; } +#endif + const_iterator upper_bound(const key_type& __x) const { return const_iterator(_Base::upper_bound(__x), this); } +#if __cplusplus > 201103L + template::type> + const_iterator + upper_bound(const _Kt& __x) const + { return { _Base::upper_bound(__x), this }; } +#endif + std::pair equal_range(const key_type& __x) { @@ -424,6 +478,18 @@ iterator(__res.second, this)); } +#if __cplusplus > 201103L + template::type> + std::pair + equal_range(const _Kt& __x) + { + auto __res = _Base::equal_range(__x); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + std::pair equal_range(const key_type& __x) const { @@ -433,6 +499,18 @@ const_iterator(__res.second, this)); } +#if __cplusplus > 201103L + template::type> + std::pair + equal_range(const _Kt& __x) const + { + auto __res = _Base::equal_range(__x); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + _Base& _M_base() _GLIBCXX_NOEXCEPT { return *this; } Index: include/debug/multiset.h =================================================================== --- include/debug/multiset.h (revision 224099) +++ include/debug/multiset.h (working copy) @@ -386,6 +386,22 @@ find(const key_type& __x) const { return const_iterator(_Base::find(__x), this); } +#if __cplusplus > 201103L + template::type> + iterator + find(const _Kt& __x) + { return { _Base::find(__x), this }; } + + template::type> + const_iterator + find(const _Kt& __x) const + { return { _Base::find(__x), this }; } +#endif + using _Base::count; iterator @@ -398,7 +414,23 @@ lower_bound(const key_type& __x) const { return const_iterator(_Base::lower_bound(__x), this); } +#if __cplusplus > 201103L + template::type> iterator + lower_bound(const _Kt& __x) + { return { _Base::lower_bound(__x), this }; } + + template::type> + const_iterator + lower_bound(const _Kt& __x) const + { return { _Base::lower_bound(__x), this }; } +#endif + + iterator upper_bound(const key_type& __x) { return iterator(_Base::upper_bound(__x), this); } @@ -408,6 +440,22 @@ upper_bound(const key_type& __x) const { return const_iterator(_Base::upper_bound(__x), this); } +#if __cplusplus > 201103L + template::type> + iterator + upper_bound(const _Kt& __x) + { return { _Base::upper_bound(__x), this }; } + + template::type> + const_iterator + upper_bound(const _Kt& __x) const + { return { _Base::upper_bound(__x), this }; } +#endif + std::pair equal_range(const key_type& __x) { @@ -428,6 +476,28 @@ const_iterator(__res.second, this)); } +#if __cplusplus > 201103L + template::type> + std::pair + equal_range(const _Kt& __x) + { + auto __res = _Base::equal_range(__x); + return { { __res.first, this }, { __res.second, this } }; + } + + template::type> + std::pair + equal_range(const _Kt& __x) const + { + auto __res = _Base::equal_range(__x); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + _Base& _M_base() _GLIBCXX_NOEXCEPT { return *this; } Index: include/debug/set.h =================================================================== --- include/debug/set.h (revision 224099) +++ include/debug/set.h (working copy) @@ -393,6 +393,22 @@ find(const key_type& __x) const { return const_iterator(_Base::find(__x), this); } +#if __cplusplus > 201103L + template::type> + iterator + find(const _Kt& __x) + { return { _Base::find(__x), this }; } + + template::type> + const_iterator + find(const _Kt& __x) const + { return { _Base::find(__x), this }; } +#endif + using _Base::count; iterator @@ -405,7 +421,23 @@ lower_bound(const key_type& __x) const { return const_iterator(_Base::lower_bound(__x), this); } +#if __cplusplus > 201103L + template::type> iterator + lower_bound(const _Kt& __x) + { return { _Base::lower_bound(__x), this }; } + + template::type> + const_iterator + lower_bound(const _Kt& __x) const + { return { _Base::lower_bound(__x), this }; } +#endif + + iterator upper_bound(const key_type& __x) { return iterator(_Base::upper_bound(__x), this); } @@ -415,6 +447,22 @@ upper_bound(const key_type& __x) const { return const_iterator(_Base::upper_bound(__x), this); } +#if __cplusplus > 201103L + template::type> + iterator + upper_bound(const _Kt& __x) + { return { _Base::upper_bound(__x), this }; } + + template::type> + const_iterator + upper_bound(const _Kt& __x) const + { return { _Base::upper_bound(__x), this }; } +#endif + std::pair equal_range(const key_type& __x) { @@ -429,12 +477,34 @@ std::pair equal_range(const key_type& __x) const { - std::pair<_Base_iterator, _Base_iterator> __res = + std::pair<_Base_const_iterator, _Base_const_iterator> __res = _Base::equal_range(__x); return std::make_pair(const_iterator(__res.first, this), const_iterator(__res.second, this)); } +#if __cplusplus > 201103L + template::type> + std::pair + equal_range(const _Kt& __x) + { + auto __res = _Base::equal_range(__x); + return { { __res.first, this }, { __res.second, this } }; + } + + template::type> + std::pair + equal_range(const _Kt& __x) const + { + auto __res = _Base::equal_range(__x); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + _Base& _M_base() _GLIBCXX_NOEXCEPT { return *this; } Index: include/profile/map.h =================================================================== --- include/profile/map.h (revision 224099) +++ include/profile/map.h (working copy) @@ -429,6 +429,18 @@ return iterator(_Base::find(__x), this); } +#if __cplusplus > 201103L + template::type> + iterator + find(const _Kt& __x) + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + return { _Base::find(__x), this }; + } +#endif + const_iterator find(const key_type& __x) const { @@ -436,6 +448,18 @@ return const_iterator(_Base::find(__x), this); } +#if __cplusplus > 201103L + template::type> + const_iterator + find(const _Kt& __x) const + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + return { _Base::find(__x), this }; + } +#endif + size_type count(const key_type& __x) const { @@ -443,6 +467,18 @@ return _Base::count(__x); } +#if __cplusplus > 201103L + template::type> + size_type + count(const _Kt& __x) const + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + return _Base::count(__x); + } +#endif + iterator lower_bound(const key_type& __x) { @@ -451,6 +487,19 @@ return iterator(_Base::lower_bound(__x), this); } +#if __cplusplus > 201103L + template::type> + iterator + lower_bound(const _Kt& __x) + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + __profcxx_map2umap_invalidate(this->_M_map2umap_info); + return { _Base::lower_bound(__x), this }; + } +#endif + const_iterator lower_bound(const key_type& __x) const { @@ -459,6 +508,19 @@ return const_iterator(_Base::lower_bound(__x), this); } +#if __cplusplus > 201103L + template::type> + const_iterator + lower_bound(const _Kt& __x) const + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + __profcxx_map2umap_invalidate(this->_M_map2umap_info); + return { _Base::lower_bound(__x), this }; + } +#endif + iterator upper_bound(const key_type& __x) { @@ -467,6 +529,19 @@ return iterator(_Base::upper_bound(__x), this); } +#if __cplusplus > 201103L + template::type> + iterator + upper_bound(const _Kt& __x) + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + __profcxx_map2umap_invalidate(this->_M_map2umap_info); + return { _Base::upper_bound(__x), this }; + } +#endif + const_iterator upper_bound(const key_type& __x) const { @@ -475,6 +550,19 @@ return const_iterator(_Base::upper_bound(__x), this); } +#if __cplusplus > 201103L + template::type> + const_iterator + upper_bound(const _Kt& __x) const + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + __profcxx_map2umap_invalidate(this->_M_map2umap_info); + return { _Base::upper_bound(__x), this }; + } +#endif + std::pair equal_range(const key_type& __x) { @@ -485,6 +573,19 @@ iterator(__base_ret.second, this)); } +#if __cplusplus > 201103L + template::type> + std::pair + equal_range(const _Kt& __x) + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + auto __res = _Base::equal_range(__x); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + std::pair equal_range(const key_type& __x) const { @@ -495,6 +596,19 @@ const_iterator(__base_ret.second, this)); } +#if __cplusplus > 201103L + template::type> + std::pair + equal_range(const _Kt& __x) const + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + auto __res = _Base::equal_range(__x); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + _Base& _M_base() _GLIBCXX_NOEXCEPT { return *this; } Index: include/profile/multimap.h =================================================================== --- include/profile/multimap.h (revision 224099) +++ include/profile/multimap.h (working copy) @@ -388,6 +388,18 @@ return iterator(_Base::find(__x), this); } +#if __cplusplus > 201103L + template::type> + iterator + find(const _Kt& __x) + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + return { _Base::find(__x), this }; + } +#endif + const_iterator find(const key_type& __x) const { @@ -395,6 +407,18 @@ return const_iterator(_Base::find(__x), this); } +#if __cplusplus > 201103L + template::type> + const_iterator + find(const _Kt& __x) const + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + return { _Base::find(__x), this }; + } +#endif + size_type count(const key_type& __x) const { @@ -402,6 +426,18 @@ return _Base::count(__x); } +#if __cplusplus > 201103L + template::type> + size_type + count(const _Kt& __x) const + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + return _Base::count(__x); + } +#endif + iterator lower_bound(const key_type& __x) { @@ -410,6 +446,19 @@ return iterator(_Base::lower_bound(__x), this); } +#if __cplusplus > 201103L + template::type> + iterator + lower_bound(const _Kt& __x) + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + __profcxx_map2umap_invalidate(this->_M_map2umap_info); + return { _Base::lower_bound(__x), this }; + } +#endif + const_iterator lower_bound(const key_type& __x) const { @@ -418,6 +467,19 @@ return const_iterator(_Base::lower_bound(__x), this); } +#if __cplusplus > 201103L + template::type> + const_iterator + lower_bound(const _Kt& __x) const + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + __profcxx_map2umap_invalidate(this->_M_map2umap_info); + return { _Base::lower_bound(__x), this }; + } +#endif + iterator upper_bound(const key_type& __x) { @@ -426,6 +488,19 @@ return iterator(_Base::upper_bound(__x), this); } +#if __cplusplus > 201103L + template::type> + iterator + upper_bound(const _Kt& __x) + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + __profcxx_map2umap_invalidate(this->_M_map2umap_info); + return { _Base::upper_bound(__x), this }; + } +#endif + const_iterator upper_bound(const key_type& __x) const { @@ -434,6 +509,19 @@ return const_iterator(_Base::upper_bound(__x), this); } +#if __cplusplus > 201103L + template::type> + const_iterator + upper_bound(const _Kt& __x) const + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + __profcxx_map2umap_invalidate(this->_M_map2umap_info); + return { _Base::upper_bound(__x), this }; + } +#endif + std::pair equal_range(const key_type& __x) { @@ -444,6 +532,19 @@ iterator(__base_ret.second, this)); } +#if __cplusplus > 201103L + template::type> + std::pair + equal_range(const _Kt& __x) + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + auto __res = _Base::equal_range(__x); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + std::pair equal_range(const key_type& __x) const { @@ -454,6 +555,19 @@ const_iterator(__base_ret.second, this)); } +#if __cplusplus > 201103L + template::type> + std::pair + equal_range(const _Kt& __x) const + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + auto __res = _Base::equal_range(__x); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + _Base& _M_base() _GLIBCXX_NOEXCEPT { return *this; } Index: include/profile/multiset.h =================================================================== --- include/profile/multiset.h (revision 224099) +++ include/profile/multiset.h (working copy) @@ -379,6 +379,18 @@ return _Base::count(__x); } +#if __cplusplus > 201103L + template::type> + size_type + count(const _Kt& __x) const + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + return _Base::count(__x); + } +#endif + // multiset operations: iterator find(const key_type& __x) @@ -396,7 +408,29 @@ return const_iterator(_Base::find(__x), this); } +#if __cplusplus > 201103L + template::type> iterator + find(const _Kt& __x) + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + return { _Base::find(__x), this }; + } + + template::type> + const_iterator + find(const _Kt& __x) const + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + return { _Base::find(__x), this }; + } +#endif + + iterator lower_bound(const key_type& __x) { __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); @@ -413,7 +447,31 @@ return const_iterator(_Base::lower_bound(__x), this); } +#if __cplusplus > 201103L + template::type> iterator + lower_bound(const _Kt& __x) + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + __profcxx_map2umap_invalidate(this->_M_map2umap_info); + return { _Base::lower_bound(__x), this }; + } + + template::type> + const_iterator + lower_bound(const _Kt& __x) const + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + __profcxx_map2umap_invalidate(this->_M_map2umap_info); + return { _Base::lower_bound(__x), this }; + } +#endif + + iterator upper_bound(const key_type& __x) { __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); @@ -431,6 +489,30 @@ return const_iterator(_Base::upper_bound(__x), this); } +#if __cplusplus > 201103L + template::type> + iterator + upper_bound(const _Kt& __x) + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + __profcxx_map2umap_invalidate(this->_M_map2umap_info); + return { _Base::upper_bound(__x), this }; + } + + template::type> + const_iterator + upper_bound(const _Kt& __x) const + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + __profcxx_map2umap_invalidate(this->_M_map2umap_info); + return { _Base::upper_bound(__x), this }; + } +#endif + std::pair equal_range(const key_type& __x) { @@ -453,6 +535,30 @@ const_iterator(__base_ret.second, this)); } +#if __cplusplus > 201103L + template::type> + std::pair + equal_range(const _Kt& __x) + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + auto __res = _Base::equal_range(__x); + return { { __res.first, this }, { __res.second, this } }; + } + + template::type> + std::pair + equal_range(const _Kt& __x) const + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + auto __res = _Base::equal_range(__x); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + _Base& _M_base() _GLIBCXX_NOEXCEPT { return *this; } Index: include/profile/set.h =================================================================== --- include/profile/set.h (revision 224099) +++ include/profile/set.h (working copy) @@ -369,6 +369,18 @@ return _Base::count(__x); } +#if __cplusplus > 201103L + template::type> + size_type + count(const _Kt& __x) const + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + return _Base::count(__x); + } +#endif + // set operations: iterator find(const key_type& __x) @@ -384,7 +396,29 @@ return const_iterator(_Base::find(__x), this); } +#if __cplusplus > 201103L + template::type> iterator + find(const _Kt& __x) + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + return { _Base::find(__x), this }; + } + + template::type> + const_iterator + find(const _Kt& __x) const + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + return { _Base::find(__x), this }; + } +#endif + + iterator lower_bound(const key_type& __x) { __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); @@ -400,7 +434,31 @@ return const_iterator(_Base::lower_bound(__x), this); } +#if __cplusplus > 201103L + template::type> iterator + lower_bound(const _Kt& __x) + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + __profcxx_map2umap_invalidate(this->_M_map2umap_info); + return { _Base::lower_bound(__x), this }; + } + + template::type> + const_iterator + lower_bound(const _Kt& __x) const + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + __profcxx_map2umap_invalidate(this->_M_map2umap_info); + return { _Base::lower_bound(__x), this }; + } +#endif + + iterator upper_bound(const key_type& __x) { __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); @@ -416,6 +474,30 @@ return const_iterator(_Base::upper_bound(__x), this); } +#if __cplusplus > 201103L + template::type> + iterator + upper_bound(const _Kt& __x) + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + __profcxx_map2umap_invalidate(this->_M_map2umap_info); + return { _Base::upper_bound(__x), this }; + } + + template::type> + const_iterator + upper_bound(const _Kt& __x) const + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + __profcxx_map2umap_invalidate(this->_M_map2umap_info); + return { _Base::upper_bound(__x), this }; + } +#endif + std::pair equal_range(const key_type& __x) { @@ -436,6 +518,30 @@ const_iterator(__base_ret.second, this)); } +#if __cplusplus > 201103L + template::type> + std::pair + equal_range(const _Kt& __x) + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + auto __res = _Base::equal_range(__x); + return { { __res.first, this }, { __res.second, this } }; + } + + template::type> + std::pair + equal_range(const _Kt& __x) const + { + __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); + auto __res = _Base::equal_range(__x); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + _Base& _M_base() _GLIBCXX_NOEXCEPT { return *this; } Index: testsuite/23_containers/map/operations/1.cc =================================================================== --- testsuite/23_containers/map/operations/1.cc (revision 224099) +++ testsuite/23_containers/map/operations/1.cc (working copy) @@ -29,6 +29,7 @@ map m0; typedef map::iterator iterator; + typedef map::const_iterator const_iterator; typedef pair insert_return_type; pair pp0; typedef map::value_type value_type; @@ -110,13 +111,14 @@ VERIFY( pp0.first == m0.begin() ); VERIFY( pp0.second == irt0.first ); - pp0 = m0.equal_range(1); - VERIFY( m0.count(1) == 1 ); - VERIFY( *pp0.first == value_type(1, 1) ); - VERIFY( *pp0.second == value_type(2, 2) ); - VERIFY( pp0.first == irt0.first ); - VERIFY( --pp0.first == irt7.first); - VERIFY( pp0.second == irt1.first ); + const map& m1 = m0; + pair pp1 = m1.equal_range(1); + VERIFY( m1.count(1) == 1 ); + VERIFY( *pp1.first == value_type(1, 1) ); + VERIFY( *pp1.second == value_type(2, 2) ); + VERIFY( pp1.first == irt0.first ); + VERIFY( --pp1.first == irt7.first); + VERIFY( pp1.second == irt1.first ); } int Index: testsuite/23_containers/multimap/operations/1.cc =================================================================== --- testsuite/23_containers/multimap/operations/1.cc (revision 224099) +++ testsuite/23_containers/multimap/operations/1.cc (working copy) @@ -29,6 +29,7 @@ multimap mm0; typedef multimap::iterator iterator; + typedef multimap::const_iterator const_iterator; pair pp0; typedef multimap::value_type value_type; @@ -109,13 +110,14 @@ VERIFY( pp0.first == mm0.begin() ); VERIFY( pp0.second == iter0 ); - pp0 = mm0.equal_range(1); - VERIFY( mm0.count(1) == 5 ); - VERIFY( *pp0.first == value_type(1, 1) ); - VERIFY( *pp0.second == value_type(2, 2) ); - VERIFY( pp0.first == iter0 ); - VERIFY( --pp0.first == iter7 ); - VERIFY( pp0.second == iter1 ); + const multimap& mm1 = mm0; + pair pp1 = mm1.equal_range(1); + VERIFY( mm1.count(1) == 5 ); + VERIFY( *pp1.first == value_type(1, 1) ); + VERIFY( *pp1.second == value_type(2, 2) ); + VERIFY( pp1.first == iter0 ); + VERIFY( --pp1.first == iter7 ); + VERIFY( pp1.second == iter1 ); } int Index: testsuite/23_containers/multiset/operations/1.cc =================================================================== --- testsuite/23_containers/multiset/operations/1.cc (revision 224099) +++ testsuite/23_containers/multiset/operations/1.cc (working copy) @@ -29,6 +29,7 @@ multiset ms0; typedef multiset::iterator iterator; + typedef multiset::const_iterator const_iterator; pair pp0; pp0 = ms0.equal_range(1); @@ -108,13 +109,14 @@ VERIFY( pp0.first == ms0.begin() ); VERIFY( pp0.second == iter0 ); - pp0 = ms0.equal_range(1); - VERIFY( ms0.count(1) == 5 ); - VERIFY( *pp0.first == 1 ); - VERIFY( *pp0.second == 2 ); - VERIFY( pp0.first == iter0 ); - VERIFY( --pp0.first == iter7 ); - VERIFY( pp0.second == iter1 ); + const multiset& ms1 = ms0; + pair pp1 = ms1.equal_range(1); + VERIFY( ms1.count(1) == 5 ); + VERIFY( *pp1.first == 1 ); + VERIFY( *pp1.second == 2 ); + VERIFY( pp1.first == iter0 ); + VERIFY( --pp1.first == iter7 ); + VERIFY( pp1.second == iter1 ); } int Index: testsuite/23_containers/set/operations/1.cc =================================================================== --- testsuite/23_containers/set/operations/1.cc (revision 224099) +++ testsuite/23_containers/set/operations/1.cc (working copy) @@ -29,6 +29,7 @@ set s0; typedef set::iterator iterator; + typedef set::const_iterator const_iterator; typedef pair insert_return_type; pair pp0; @@ -109,13 +110,14 @@ VERIFY( pp0.first == s0.begin() ); VERIFY( pp0.second == irt0.first ); - pp0 = s0.equal_range(1); - VERIFY( s0.count(1) == 1 ); - VERIFY( *pp0.first == 1 ); - VERIFY( *pp0.second == 2 ); - VERIFY( pp0.first == irt0.first ); - VERIFY( --pp0.first == irt7.first ); - VERIFY( pp0.second == irt1.first ); + const set& s1 = s0; + pair pp1 = s1.equal_range(1); + VERIFY( s1.count(1) == 1 ); + VERIFY( *pp1.first == 1 ); + VERIFY( *pp1.second == 2 ); + VERIFY( pp1.first == irt0.first ); + VERIFY( --pp1.first == irt7.first ); + VERIFY( pp1.second == irt1.first ); } int