From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-40133.protonmail.ch (mail-40133.protonmail.ch [185.70.40.133]) by sourceware.org (Postfix) with ESMTPS id C6A7E3858425 for ; Mon, 11 Mar 2024 23:36:10 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org C6A7E3858425 Authentication-Results: sourceware.org; dmarc=pass (p=quarantine dis=none) header.from=protonmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=protonmail.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org C6A7E3858425 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=185.70.40.133 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1710200172; cv=none; b=K8FvrRpxUSxlFL0VmuIUlodD1gNoyGLBL0Br4ZMNbjacGMhIPrygw7yZIG1Mnvoh967dLBWXhYgMoHIwJYk+DdmuMFLXmP6AQtPYsYGZqnZhVDlxfRgZA20/Pg+L7SusV6EhEO7upX5Rm3GrEk9jmSvvdWgmcai3vcFpAVct9ls= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1710200172; c=relaxed/simple; bh=OpO9yrUiYTdoNKQLAfD1yehwmHUCkY2yifEAt2R7Xkg=; h=DKIM-Signature:Date:To:From:Subject:Message-ID:MIME-Version; b=KnQYrTgWnCtYUvKHePfmcbU8caSsWarhZIp/HIRtr64WsQzGJ6OvdSyTfYmEe3Hvtl9OYjQ3EggWw2A1yM6uGvUpETRB0Sa5X4i91J3Wgqerf4k08Jryz+p8CfgJPSE29J+Ib15+qvjXwJ4BbFNiVVR+pQ9NGPkICSHfTF5bPBk= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com; s=protonmail3; t=1710200169; x=1710459369; bh=stVefCrzd9Wqy0qFvwznskQaMaumRfhIROJhiXxuK+E=; h=Date:To:From:Subject:Message-ID:Feedback-ID:From:To:Cc:Date: Subject:Reply-To:Feedback-ID:Message-ID:BIMI-Selector; b=uFxnYGf6yZgb/qE5RNUPEXldHr2vfZywC2CzpW2zis7Fny1h2rHcKtxaxJuRTpcgm Y2uMbEMQVz4ZtmdFDO++kXEVtAbme6h/ZU3c+rMl+paKaWC8T1faP7/w8Z7cOJUPOW kDx4tiQ+TjL5Z145a7pIMIvfkp5gYjhQ+wCzsivPMfTCcDzBdwyXUrtslG8Hh66AS6 S8rXL451d8W7qqbqrfs0BU6zQgjy8LyeFmQ10ZhIAc64Ph5U+VF/Ht5RbmtSyZwE1j GD+XEP7VqGomZ5IMMLDxM2bS8THv6+2Uph1e5qRYim6kVfS41r176MWrMP+KAKYOgF csud47cIt03tQ== Date: Mon, 11 Mar 2024 23:35:50 +0000 To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org From: =?utf-8?Q?Barnab=C3=A1s_P=C5=91cze?= Subject: [PATCH v1] libstdc++: Optimize removal from unique assoc containers [PR112934] Message-ID: <20240311233548.3705328-1-pobrn@protonmail.com> Feedback-ID: 20568564:user:proton MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-10.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,GIT_PATCH_0,RCVD_IN_MSPIKE_H4,RCVD_IN_MSPIKE_WL,SPF_HELO_PASS,SPF_PASS,TXREP,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: Previously, calling erase(key) on both std::map and std::set would execute that same code that std::multi{map,set} would. However, doing that is unnecessary because std::{map,set} guarantee that all elements are unique. It is reasonable to expect that erase(key) is equivalent or better than: auto it =3D m.find(key); if (it !=3D m.end()) m.erase(it); However, this was not the case. Fix that by adding a new function _Rb_tree<>::_M_erase_unique() that is essentially equivalent to the above snippet, and use this from both std::map and std::set. libstdc++-v3/ChangeLog: =09PR libstdc++/112934 =09* include/bits/stl_tree.h (_Rb_tree<>::_M_erase_unique): Add. =09* include/bits/stl_map.h (map<>::erase): Use _M_erase_unique. =09* include/bits/stl_set.h (set<>::erase): Likewise. --- libstdc++-v3/include/bits/stl_map.h | 2 +- libstdc++-v3/include/bits/stl_set.h | 2 +- libstdc++-v3/include/bits/stl_tree.h | 17 +++++++++++++++++ 3 files changed, 19 insertions(+), 2 deletions(-) diff --git a/libstdc++-v3/include/bits/stl_map.h b/libstdc++-v3/include/bit= s/stl_map.h index ad58a631af5..229643b77fd 100644 --- a/libstdc++-v3/include/bits/stl_map.h +++ b/libstdc++-v3/include/bits/stl_map.h @@ -1115,7 +1115,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER */ size_type erase(const key_type& __x) - { return _M_t.erase(__x); } + { return _M_t._M_erase_unique(__x); } =20 #if __cplusplus >=3D 201103L // _GLIBCXX_RESOLVE_LIB_DEFECTS diff --git a/libstdc++-v3/include/bits/stl_set.h b/libstdc++-v3/include/bit= s/stl_set.h index c0eb4dbf65f..51a1717ec62 100644 --- a/libstdc++-v3/include/bits/stl_set.h +++ b/libstdc++-v3/include/bits/stl_set.h @@ -684,7 +684,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER */ size_type erase(const key_type& __x) - { return _M_t.erase(__x); } + { return _M_t._M_erase_unique(__x); } =20 #if __cplusplus >=3D 201103L // _GLIBCXX_RESOLVE_LIB_DEFECTS diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bi= ts/stl_tree.h index 6f470f04f6a..9e80d449c7e 100644 --- a/libstdc++-v3/include/bits/stl_tree.h +++ b/libstdc++-v3/include/bits/stl_tree.h @@ -1225,6 +1225,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION size_type erase(const key_type& __x); =20 + size_type + _M_erase_unique(const key_type& __x); + #if __cplusplus >=3D 201103L // _GLIBCXX_RESOLVE_LIB_DEFECTS // DR 130. Associative erase should return an iterator. @@ -2518,6 +2521,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return __old_size - size(); } =20 + template + typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_typ= e + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + _M_erase_unique(const _Key& __x) + { + iterator __it =3D find(__x); + if (__it =3D=3D end()) +=09return 0; + + _M_erase_aux(__it); + return 1; + } + template typename _Rb_tree<_Key, _Val, _KeyOfValue, --=20 2.44.0