From patchwork Tue Oct 1 03:43:58 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Palka X-Patchwork-Id: 1991307 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=Cg1ohzYQ; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4XHkNn24GPz1xtg for ; Tue, 1 Oct 2024 13:45:16 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id C56493858C41 for ; Tue, 1 Oct 2024 03:45:11 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTP id A635F3861029 for ; Tue, 1 Oct 2024 03:44:30 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org A635F3861029 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org A635F3861029 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=170.10.129.124 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1727754276; cv=none; b=nKHPmSCf4pDg3xKJvlXG3XMkyLvb9lzOUSsOf/9ELsK9XKCPKREZApVQG3iGlyfw+w4oU3Yl5Wqg225T2czg3J8AJ/gJP8aA/tMmoKygJl+ukf27Kvpz8GLnnCQVOFcbrESpVHFrs7F8cpjsmiJHYSQhMr0EJRTeLi4OOBGt1b8= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1727754276; c=relaxed/simple; bh=DFiGf5JN53PD82KOS6+l4ZvBd3fq+PTXejSLw6R1aIY=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=ejVP2fe9lSTrD56fBUYgRRaZS3Voory5PDFJaL6EIuEFZjQWQhmfgk0kwf0LA5+7BE9MS5YNMhKKP/65uV35dG3tPvr3HeubQEgv3xPFufD4Cb5ABbYwbj11XylrJ/VIgPYyWgZoB9hXejJkRZWV0oteRBZAme6vM/ePRPNxRDw= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1727754270; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=LLpelZaiM99OAGbVfYb45v36fB9X0yAotWKvn36SG8E=; b=Cg1ohzYQNjvPDHhr8lcSqiEmswvovjlKmjCRzau8izuSPUxqUd5sSxp2OxkrenyszQaaBM 9CWAEpZR4LZdcltLvfaFJ8uwtEiw+qAgwMbPSDVBtKj29cnNbzGd8vicFaD6pe6s7ZMSx3 2LxqBugRsLfdcqzJsWUfSCz1iG8OUlo= Received: from mail-qv1-f70.google.com (mail-qv1-f70.google.com [209.85.219.70]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-651-NCe_Wc5uMW-eors0fzpw4A-1; Mon, 30 Sep 2024 23:44:28 -0400 X-MC-Unique: NCe_Wc5uMW-eors0fzpw4A-1 Received: by mail-qv1-f70.google.com with SMTP id 6a1803df08f44-6cb2847dd35so12547956d6.3 for ; Mon, 30 Sep 2024 20:44:28 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1727754267; x=1728359067; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=LLpelZaiM99OAGbVfYb45v36fB9X0yAotWKvn36SG8E=; b=aSR1lgAR8U0lw5Y4UPseLHsGKRm/k4ZyH9iFzDb4q/iXsWKXRKoETO5qUFBa13OfZC Qee7fZKv+65TQC7Wz0caa3eAOpyEWHMnkLryrUSznM1nXu2zJ4CWTx64HrqsBqNOBwft s0rshBCg6/tkHptnVJngTA5Pwcc0OrFePgHP2QzUSZVB+kLTOqu6SK004EsuRYs/PprH zdexwmVtoYTgbStyT/Xoqd09z73HaHirvISckhJfegtowBaN7TqXI4RNAagQ9hkGY8AG BQrLlY+HTbX0SYpsSaWgSLzXXIeiNzNjbrQvOHYzXVpUfXQK1VVZafTIia/kpyG4nC5r STsw== X-Gm-Message-State: AOJu0YwRQh/SG6IlQmGBixqTt1777CDmSXUTYShdzU0wVXwKSCH8sQi4 Dvn2gMW6RDCAC2vb39N67i1sFeRjLwF7z3IhW+ZRkcHekln69S5UnLuZ8frLQ+9WGM4eFCjw5Ht QEicHj2/+RPaOYRBS4E+X6FGRC1cpSIG393BJFPkgm6aGTDO/6HArSdG3qbQeO9jHlc0Td2Bk4p VgBMtZgblSP8gpG9///Q4u/vaBA+QYf6soYQdE X-Received: by 2002:a05:6214:2b0e:b0:6c3:662f:8e09 with SMTP id 6a1803df08f44-6cb4be73fd7mr73610386d6.9.1727754266380; Mon, 30 Sep 2024 20:44:26 -0700 (PDT) X-Google-Smtp-Source: AGHT+IEd3jFRZAtoTy4KwVuykOLTLUNrA+e2O8gt9dIR6nA52ZodM/TyZ5enB/DOTwuFjcKSWh9V1Q== X-Received: by 2002:a05:6214:2b0e:b0:6c3:662f:8e09 with SMTP id 6a1803df08f44-6cb4be73fd7mr73610186d6.9.1727754265542; Mon, 30 Sep 2024 20:44:25 -0700 (PDT) Received: from localhost.localdomain (ool-18bb2a2e.dyn.optonline.net. [24.187.42.46]) by smtp.gmail.com with ESMTPSA id 6a1803df08f44-6cb3b600040sm45434396d6.13.2024.09.30.20.44.23 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 30 Sep 2024 20:44:24 -0700 (PDT) From: Patrick Palka To: gcc-patches@gcc.gnu.org Cc: libstdc++@gcc.gnu.org, Patrick Palka Subject: [PATCH 2/2] libstdc++: Implement C++23 (P1222R4) Date: Mon, 30 Sep 2024 23:43:58 -0400 Message-ID: <20241001034358.1375479-2-ppalka@redhat.com> X-Mailer: git-send-email 2.47.0.rc0 In-Reply-To: <20241001034358.1375479-1-ppalka@redhat.com> References: <20241001034358.1375479-1-ppalka@redhat.com> MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-13.5 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org This implements the C++23 container adaptors std::flat_set and std::flat_multiset from P1222R4. The implementation is essentially an simpler and pared down version of std::flat_map. The main known issues are: * exception safety is likely incomplete/buggy * unimplemented from_range_t constructors and insert_range function * the main worthouse function _M_try_emplace is probably buggy wrt its handling of the hint parameter and could be simplified * more extensive testcases are a WIP libstdc++-v3/ChangeLog: * include/Makefile.am: Add new header . * include/Makefile.in: Regenerate. * include/bits/version.def (__cpp_flat_set): Define. * include/bits/version.h: Regenerate * include/std/flat_set: New file. * testsuite/23_containers/flat_multiset/1.cc: New test. * testsuite/23_containers/flat_set/1.cc: New test. --- libstdc++-v3/include/Makefile.am | 1 + libstdc++-v3/include/Makefile.in | 1 + libstdc++-v3/include/bits/version.def | 8 + libstdc++-v3/include/bits/version.h | 10 + libstdc++-v3/include/std/flat_set | 968 ++++++++++++++++++ .../23_containers/flat_multiset/1.cc | 73 ++ .../testsuite/23_containers/flat_set/1.cc | 78 ++ 7 files changed, 1139 insertions(+) create mode 100644 libstdc++-v3/include/std/flat_set create mode 100644 libstdc++-v3/testsuite/23_containers/flat_multiset/1.cc create mode 100644 libstdc++-v3/testsuite/23_containers/flat_set/1.cc diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am index 632bbafa63e..e49cdb23c55 100644 --- a/libstdc++-v3/include/Makefile.am +++ b/libstdc++-v3/include/Makefile.am @@ -71,6 +71,7 @@ std_headers = \ ${std_srcdir}/execution \ ${std_srcdir}/filesystem \ ${std_srcdir}/flat_map \ + ${std_srcdir}/flat_set \ ${std_srcdir}/format \ ${std_srcdir}/forward_list \ ${std_srcdir}/fstream \ diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in index 1ac963c4415..8e6ee44cc0e 100644 --- a/libstdc++-v3/include/Makefile.in +++ b/libstdc++-v3/include/Makefile.in @@ -427,6 +427,7 @@ std_freestanding = \ @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/execution \ @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/filesystem \ @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/flat_map \ +@GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/flat_set \ @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/format \ @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/forward_list \ @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/fstream \ diff --git a/libstdc++-v3/include/bits/version.def b/libstdc++-v3/include/bits/version.def index 631eca7beac..827582cf2ea 100644 --- a/libstdc++-v3/include/bits/version.def +++ b/libstdc++-v3/include/bits/version.def @@ -1666,6 +1666,14 @@ ftms = { }; }; +ftms = { + name = flat_set; + values = { + v = 202207; + cxxmin = 23; + }; +}; + ftms = { name = formatters; values = { diff --git a/libstdc++-v3/include/bits/version.h b/libstdc++-v3/include/bits/version.h index 1f3040fcbde..311586461e3 100644 --- a/libstdc++-v3/include/bits/version.h +++ b/libstdc++-v3/include/bits/version.h @@ -1840,6 +1840,16 @@ #endif /* !defined(__cpp_lib_flat_map) && defined(__glibcxx_want_flat_map) */ #undef __glibcxx_want_flat_map +#if !defined(__cpp_lib_flat_set) +# if (__cplusplus >= 202100L) +# define __glibcxx_flat_set 202207L +# if defined(__glibcxx_want_all) || defined(__glibcxx_want_flat_set) +# define __cpp_lib_flat_set 202207L +# endif +# endif +#endif /* !defined(__cpp_lib_flat_set) && defined(__glibcxx_want_flat_set) */ +#undef __glibcxx_want_flat_set + #if !defined(__cpp_lib_formatters) # if (__cplusplus >= 202100L) && _GLIBCXX_HOSTED # define __glibcxx_formatters 202302L diff --git a/libstdc++-v3/include/std/flat_set b/libstdc++-v3/include/std/flat_set new file mode 100644 index 00000000000..bbb63408cc2 --- /dev/null +++ b/libstdc++-v3/include/std/flat_set @@ -0,0 +1,968 @@ +// -*- C++ -*- + +// Copyright The GNU Toolchain Authors. +// +// 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// . + +/** @file include/flat_set + * This is a Standard C++ Library header. + */ + +#ifndef _GLIBCXX_FLAT_SET +#define _GLIBCXX_FLAT_SET 1 + +#ifdef _GLIBCXX_SYSHDR +#pragma GCC system_header +#endif + +#define __glibcxx_want_flat_set +#include + +#ifdef __cpp_lib_flat_set // >= C++23 + +#include +#include + +#include +#include +#include +#include +#include +#include +#include +#include +#include // std::less +#include + +namespace std _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + template + class flat_set; + + template + class flat_multiset; + + template + class _Flat_set_impl + { + static_assert(is_same_v<_Key, typename _KeyContainer::value_type>); + static_assert(is_nothrow_swappable_v<_KeyContainer>); + + using _Derived = __conditional_t<_Multi, + flat_multiset<_Key, _Compare, _KeyContainer>, + flat_set<_Key, _Compare, _KeyContainer>>; + using __sorted_t = __conditional_t<_Multi, sorted_equivalent_t, sorted_unique_t>; + + public: + using key_type = _Key; + using value_type = _Key; + using key_compare = _Compare; + using value_compare = _Compare; + using reference = value_type&; + using const_reference = const value_type&; + using size_type = typename _KeyContainer::size_type; + using difference_type = typename _KeyContainer::difference_type; + using iterator = typename _KeyContainer::const_iterator; + using const_iterator = typename _KeyContainer::const_iterator; + using reverse_iterator = std::reverse_iterator; + using const_reverse_iterator = std::reverse_iterator; + using container_type = _KeyContainer; + + private: + using __emplace_result_t = __conditional_t<_Multi, iterator, pair>; + + public: + // constructors + _Flat_set_impl() : _Flat_set_impl(key_compare()) { } + + explicit + _Flat_set_impl(const key_compare& __comp) + : _M_cont(), _M_comp(__comp) + { } + + _Flat_set_impl(container_type __cont, const key_compare& __comp = key_compare()) + : _M_cont(std::move(__cont)), _M_comp(__comp) + { _M_sort_uniq(); } + + _Flat_set_impl(__sorted_t, + container_type __cont, const key_compare& __comp = key_compare()) + : _M_cont(std::move(__cont)), _M_comp(__comp) + { } + + template> + _Flat_set_impl(_InputIterator __first, _InputIterator __last, + const key_compare& __comp = key_compare()) + : _M_cont(), _M_comp(__comp) + { insert(__first, __last); } + + template> + _Flat_set_impl(__sorted_t __s, + _InputIterator __first, _InputIterator __last, + const key_compare& __comp = key_compare()) + : _M_cont(), _M_comp(__comp) + { insert(__s, __first, __last); } + + // TODO: Implement from_range_t constructors. + + _Flat_set_impl(initializer_list __il, + const key_compare& __comp = key_compare()) + : _Flat_set_impl(__il.begin(), __il.end(), __comp) + { } + + _Flat_set_impl(__sorted_t __s, + initializer_list __il, + const key_compare& __comp = key_compare()) + : _Flat_set_impl(__s, __il.begin(), __il.end(), __comp) + { } + + // constructors with allocators + + template + explicit + _Flat_set_impl(const _Alloc& __a) + : _Flat_set_impl(key_compare(), __a) + { } + + template + _Flat_set_impl(const key_compare& __comp, const _Alloc& __a) + : _M_cont(std::make_obj_using_allocator(__a)), + _M_comp(__comp) + { } + + template + _Flat_set_impl(const container_type& __cont, const _Alloc& __a) + : _Flat_set_impl(__cont, key_compare(), __a) + { } + + template + _Flat_set_impl(const container_type& __cont, const key_compare& __comp, + const _Alloc& __a) + : _M_cont(std::make_obj_using_allocator(__a, __cont)), + _M_comp(__comp) + { _M_sort_uniq(); } + + template + _Flat_set_impl(__sorted_t __s, const container_type& __cont, const _Alloc& __a) + : _Flat_set_impl(__s, __cont, key_compare(), __a) + { } + + template + _Flat_set_impl(__sorted_t __s, + const container_type& __cont, const key_compare& __comp, + const _Alloc& __a) + : _M_comp(__comp), + _M_cont(std::make_obj_using_allocator(__a, __cont)) + { } + + template + _Flat_set_impl(const _Derived& __x, const _Alloc& __a) + : _M_comp(__x._M_comp), + _M_cont(std::make_obj_using_allocator(__a, + __x._M_cont)) + { } + + template + _Flat_set_impl(_Derived&& __x, const _Alloc& __a) + : _M_comp(__x._M_comp), + _M_cont(std::make_obj_using_allocator(__a, std::move(__x._M_cont))) + { } + + template> + _Flat_set_impl(_InputIterator __first, _InputIterator __last, + const _Alloc& __a) + : _Flat_set_impl(std::move(__first), std::move(__last), key_compare(), __a) + { } + + template> + _Flat_set_impl(_InputIterator __first, _InputIterator __last, + const key_compare& __comp, + const _Alloc& __a) + : _Flat_set_impl(__comp, __a) + { insert(__first, __last); } + + template> + _Flat_set_impl(__sorted_t __s, + _InputIterator __first, _InputIterator __last, + const _Alloc& __a) + : _Flat_set_impl(__s, std::move(__first), std::move(__last), key_compare(), __a) + { } + + template> + _Flat_set_impl(__sorted_t __s, + _InputIterator __first, _InputIterator __last, + const key_compare& __comp, + const _Alloc& __a) + : _Flat_set_impl(__comp, __a) + { insert(__s, __first, __last); } + + // TODO: Implement allocator-aware from_range_t constructors. + + template + _Flat_set_impl(initializer_list __il, + const _Alloc& __a) + : _Flat_set_impl(__il, key_compare(), __a) + { } + + template + _Flat_set_impl(initializer_list __il, + const key_compare& __comp, + const _Alloc& __a) + : _Flat_set_impl(__il.begin(), __il.end(), __comp, __a) + { } + + template + _Flat_set_impl(__sorted_t __s, + initializer_list __il, + const _Alloc& __a) + : _Flat_set_impl(__s, __il.begin(), __il.end(), key_compare(), __a) + { } + + template + _Flat_set_impl(__sorted_t __s, + initializer_list __il, + const key_compare& __comp, + const _Alloc& __a) + : _Flat_set_impl(__s, __il.begin(), __il.end(), __comp, __a) + { } + + _Derived& + operator=(initializer_list __il) + { + clear(); + insert(__il); + return static_cast<_Derived&>(*this); + } + + // iterators + const_iterator + begin() const noexcept + { return _M_cont.begin(); } + + const_iterator + end() const noexcept + { return _M_cont.end(); } + + const_reverse_iterator + rbegin() const noexcept + { return const_reverse_iterator(end()); } + + const_reverse_iterator + rend() const noexcept + { return const_reverse_iterator(begin()); } + + const_iterator + cbegin() const noexcept + { return begin(); } + + const_iterator + cend() const noexcept + { return end(); } + + const_reverse_iterator + crbegin() const noexcept + { return rbegin(); } + + const_reverse_iterator + crend() const noexcept + { return rend(); } + + // capacity + [[nodiscard]] bool + empty() const noexcept + { return _M_cont.empty(); } + + size_type + size() const noexcept + { return _M_cont.size(); } + + size_type + max_size() const noexcept + { return _M_cont.max_size(); } + + // modifiers + template + pair + _M_try_emplace(optional __hint, _Args&&... __args) + { + // TODO: Simplify and audit the hint handling. + value_type __k(std::forward<_Args>(__args)...); + typename container_type::iterator __it; + int __r = -1, __s = -1; + if (__hint.has_value() + && (__hint == cbegin() + || (__r = !_M_comp(__k, (*__hint)[-1]))) // k >= hint[-1] + && (__hint == cend() + || (__s = !_M_comp((*__hint)[0], __k)))) // k <= hint[0] + { + __it = _M_cont.begin() + (*__hint - begin()); + if constexpr (!_Multi) + if (__r == 1 && !_M_comp(__it[-1], __k)) // k == hint[-1] + return {__it - 1, false}; + } + else + { + auto __first = _M_cont.begin(); + auto __last = _M_cont.end(); + if (__r == 1) // k >= hint[-1] + __first += *__hint - _M_cont.begin(); + else if (__r == 0) // k < __hint[-1] + __last = __first + (*__hint - _M_cont.begin()); + if constexpr (_Multi) + { + if (__s == 0) // hint[0] < k + // Insert before the leftmost equivalent key. + __it = std::lower_bound(__first, __last, __k, _M_comp); + else + // Insert after the rightmost equivalent key. + __it = std::upper_bound(std::make_reverse_iterator(__last), + std::make_reverse_iterator(__first), + __k, std::not_fn(_M_comp)).base(); + } + else + __it = std::lower_bound(__first, __last, __k, _M_comp); + } + + if constexpr (!_Multi) + if (__it != _M_cont.end() && !_M_comp(__k, __it[0])) + return {__it, false}; + + __it = _M_cont.insert(__it, std::move(__k)); + return {__it, true}; + } + + template + requires is_constructible_v + __emplace_result_t + emplace(_Args&&... __args) + { + auto __r = _M_try_emplace(nullopt, std::forward<_Args>(__args)...); + if constexpr (_Multi) + return __r.first; + else + return __r; + } + + template + iterator + emplace_hint(const_iterator __position, _Args&&... __args) + { return _M_try_emplace(__position, std::forward<_Args>(__args)...).first; } + + __emplace_result_t + insert(const value_type& __x) + { return emplace(__x); } + + __emplace_result_t + insert(value_type&& __x) + { return emplace(std::move(__x)); } + + iterator + insert(const_iterator __position, const value_type& __x) + { return emplace_hint(__position, __x); } + + iterator + insert(const_iterator __position, value_type&& __x) + { return emplace_hint(__position, std::move(__x)); } + + template + requires is_constructible_v + __emplace_result_t + insert(_Arg&& __x) + { return emplace(std::forward<_Arg>(__x)); } + + template + requires is_constructible_v + iterator + insert(const_iterator __position, _Arg&& __x) + { return emplace_hint(__position, std::forward<_Arg>(__x)); } + + template> + void + insert(_InputIterator __first, _InputIterator __last) + { + auto __it = _M_cont.insert(_M_cont.end(), __first, __last); + std::sort(__it, _M_cont.end(), _M_comp); + std::inplace_merge(_M_cont.begin(), __it, _M_cont.end(), _M_comp); + _M_unique(); + } + + template> + void + insert(__sorted_t, _InputIterator __first, _InputIterator __last) + { + auto __it = _M_cont.insert(_M_cont.end(), __first, __last); + std::inplace_merge(_M_cont.begin(), __it, _M_cont.end(), _M_comp); + _M_unique(); + } + + // TODO: Implement insert_range. + + void + insert(initializer_list __il) + { insert(__il.begin(), __il.end()); } + + void + insert(__sorted_t __s, initializer_list __il) + { insert(__s, __il.begin(), __il.end()); } + + container_type + extract() && + { + struct _Guard + { + _Guard(_Flat_set_impl* __m) : _M_m(__m) { } + + ~_Guard() { _M_m->clear(); } + + _Flat_set_impl* _M_m; + } __clear_guard = {this}; + return std::move(_M_cont); + } + + void + replace(container_type&& __cont) + { + __try + { + _M_cont = std::move(__cont); + } + __catch(...) + { + clear(); + __throw_exception_again; + } + } + + iterator + erase(const_iterator __position) + { return _M_cont.erase(__position); } + + size_type + erase(const key_type& __x) + { return erase(__x); } + + template + requires same_as, _Key> + || (__transparent_comparator<_Compare> + && !is_convertible_v<_Key2, iterator> + && !is_convertible_v<_Key2, const_iterator>) + size_type + erase(_Key2&& __x) + { + auto [__first, __last] = equal_range(std::forward<_Key2>(__x)); + auto __n = __last - __first; + erase(__first, __last); + return __n; + } + + iterator + erase(const_iterator __first, const_iterator __last) + { return _M_cont.erase(__first, __last); } + + void + swap(_Derived& __x) noexcept + { + using std::swap; + swap(_M_cont, __x._M_cont); + swap(_M_comp, __x._M_comp); + } + + void + clear() noexcept + { _M_cont.clear(); } + + // observers + key_compare + key_comp() const + { return _M_comp; } + + value_compare + value_comp() const + { return _M_comp; } + + // map operations + iterator + find(const key_type& __x) + { return find(__x); } + + const_iterator + find(const key_type& __x) const + { return find(__x); } + + template + requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> + iterator + find(const _Key2& __x) + { + auto __it = lower_bound(__x); + if (__it != end() && !_M_comp(__x, *__it)) + return __it; + else + return end(); + } + + template + requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> + const_iterator + find(const _Key2& __x) const + { + auto __it = lower_bound(__x); + if (__it != cend() && !_M_comp(__x, *__it)) + return __it; + else + return cend(); + } + + size_type + count(const key_type& __x) const + { + if constexpr (_Multi) + return count(__x); + else + return contains(__x); + } + + template + requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> + size_type + count(const _Key2& __x) const + { + auto [__first, __last] = equal_range(__x); + return __last - __first; + } + + bool + contains(const key_type& __x) const + { return contains(__x); } + + template + requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> + bool + contains(const _Key2& __x) const + { return find(__x) != cend(); } + + iterator + lower_bound(const key_type& __x) + { return lower_bound(__x); } + + const_iterator + lower_bound(const key_type& __x) const + { return lower_bound(__x); } + + template + requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> + iterator + lower_bound(const _Key2& __x) + { return std::lower_bound(begin(), end(), __x, _M_comp); } + + template + requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> + const_iterator + lower_bound(const _Key2& __x) const + { return std::lower_bound(begin(), end(), __x, _M_comp); } + + iterator + upper_bound(const key_type& __x) + { return upper_bound(__x); } + + const_iterator + upper_bound(const key_type& __x) const + { return upper_bound(__x); } + + template + requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> + iterator + upper_bound(const _Key2& __x) + { return std::upper_bound(begin(), end(), __x, _M_comp); } + + template + requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> + const_iterator + upper_bound(const _Key2& __x) const + { return std::upper_bound(begin(), end(), __x, _M_comp); } + + pair + equal_range(const key_type& __x) + { return equal_range(__x); } + + pair + equal_range(const key_type& __x) const + { return equal_range(__x); } + + template + requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> + pair + equal_range(const _Key2& __x) + { return std::equal_range(begin(), end(), __x, _M_comp); } + + template + requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> + pair + equal_range(const _Key2& __x) const + { return std::equal_range(begin(), end(), __x, _M_comp); } + + friend bool + operator==(const _Derived& __x, const _Derived& __y) + { return ranges::equal(__x, __y); } + + template + friend __detail::__synth3way_t<_Up> + operator<=>(const _Derived& __x, const _Derived& __y) + { + return std::lexicographical_compare_three_way(__x.begin(), __x.end(), + __y.begin(), __y.end(), + __detail::__synth3way); + } + + friend void + swap(_Derived& __x, _Derived& __y) noexcept + { return __x.swap(__y); } + + template + friend size_type + erase_if(_Derived& __c, _Predicate __pred) + { + auto [__first, __last] = ranges::remove_if(__c._M_cont, __pred); + auto __n = __last - __first; + __c.erase(__first, __last); + return __n; + } + + private: + container_type _M_cont; + [[no_unique_address]] _Compare _M_comp; + + void + _M_sort_uniq() + { + std::sort(_M_cont.begin(), _M_cont.end(), _M_comp); + _M_unique(); + } + + void + _M_unique() + { + if constexpr (!_Multi) + { + struct __key_equiv + { + __key_equiv(key_compare __c) : _M_comp(__c) { } + + bool + operator()(const_reference __x, const_reference __y) const + { return !_M_comp(__x, __y) && !_M_comp(__y, __x); } + + [[no_unique_address]] key_compare _M_comp; + }; + + auto [__first, __last] = ranges::unique(_M_cont, __key_equiv(_M_comp)); + _M_cont.erase(__first, __last); + } + } + }; + + /* Class template flat_set - container adaptor + * + * @ingroup + */ + template, + typename _KeyContainer = vector<_Key>> + class flat_set + : private _Flat_set_impl<_Key, _Compare, _KeyContainer, false> + { + using _Impl = _Flat_set_impl<_Key, _Compare, _KeyContainer, false>; + friend _Impl; + + public: + // types + using typename _Impl::key_type; + using typename _Impl::value_type; + using typename _Impl::key_compare; + using typename _Impl::reference; + using typename _Impl::const_reference; + using typename _Impl::size_type; + using typename _Impl::difference_type; + using typename _Impl::iterator; + using typename _Impl::const_iterator; + using typename _Impl::reverse_iterator; + using typename _Impl::const_reverse_iterator; + using typename _Impl::container_type; + using typename _Impl::value_compare; + + // constructors + using _Impl::_Impl; + + // iterators + using _Impl::begin; + using _Impl::end; + using _Impl::rbegin; + using _Impl::rend; + + using _Impl::cbegin; + using _Impl::cend; + using _Impl::crbegin; + using _Impl::crend; + + // capacity + using _Impl::empty; + using _Impl::size; + using _Impl::max_size; + + // modifiers + using _Impl::emplace; + using _Impl::emplace_hint; + using _Impl::insert; + // using _Impl::insert_range; + using _Impl::extract; + using _Impl::replace; + using _Impl::erase; + using _Impl::swap; + using _Impl::clear; + + // observers + using _Impl::key_comp; + using _Impl::value_comp; + + // map operations + using _Impl::find; + using _Impl::count; + using _Impl::contains; + using _Impl::lower_bound; + using _Impl::upper_bound; + using _Impl::equal_range; + }; + + template, + typename = _RequireNotAllocator<_Compare>> + flat_set(_KeyContainer, _Compare = _Compare()) + -> flat_set; + + template> + flat_set(_KeyContainer, _Alloc) + -> flat_set, _KeyContainer>; + + template, + typename = _RequireAllocator<_Alloc>> + flat_set(_KeyContainer, _Compare, _Alloc) + -> flat_set; + + template, + typename = _RequireNotAllocator<_Compare>> + flat_set(sorted_unique_t, _KeyContainer, _Compare = _Compare()) + -> flat_set; + + template> + flat_set(sorted_unique_t, _KeyContainer, _Alloc) + -> flat_set, _KeyContainer>; + + template, + typename = _RequireAllocator<_Alloc>> + flat_set(sorted_unique_t, _KeyContainer, _Compare, _Alloc) + -> flat_set; + + template>, + typename = _RequireInputIter<_InputIterator>, + typename = _RequireNotAllocator<_Compare>> + flat_set(_InputIterator, _InputIterator, _Compare = _Compare()) + -> flat_set<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>; + + template>, + typename = _RequireInputIter<_InputIterator>, + typename = _RequireNotAllocator<_Compare>> + flat_set(sorted_unique_t, _InputIterator, _InputIterator, _Compare = _Compare()) + -> flat_set<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>; + + // TODO: Implement from_range_t deduction guides. + + template, + typename = _RequireNotAllocator<_Compare>> + flat_set(initializer_list<_Key>, _Compare = _Compare()) + -> flat_set<_Key, _Compare>; + + template, + typename = _RequireNotAllocator<_Compare>> + flat_set(sorted_unique_t, initializer_list<_Key>, _Compare = _Compare()) + -> flat_set<_Key, _Compare>; + + template + struct uses_allocator, _Alloc> + : bool_constant> + { }; + + /* Class template flat_multiset - container adaptor + * + * @ingroup + */ + template, + typename _KeyContainer = vector<_Key>> + class flat_multiset + : private _Flat_set_impl<_Key, _Compare, _KeyContainer, true> + { + using _Impl = _Flat_set_impl<_Key, _Compare, _KeyContainer, true>; + friend _Impl; + + public: + // types + using typename _Impl::key_type; + using typename _Impl::value_type; + using typename _Impl::key_compare; + using typename _Impl::reference; + using typename _Impl::const_reference; + using typename _Impl::size_type; + using typename _Impl::difference_type; + using typename _Impl::iterator; + using typename _Impl::const_iterator; + using typename _Impl::reverse_iterator; + using typename _Impl::const_reverse_iterator; + using typename _Impl::container_type; + using typename _Impl::value_compare; + + // constructors + using _Impl::_Impl; + + // iterators + using _Impl::begin; + using _Impl::end; + using _Impl::rbegin; + using _Impl::rend; + + using _Impl::cbegin; + using _Impl::cend; + using _Impl::crbegin; + using _Impl::crend; + + // capacity + using _Impl::empty; + using _Impl::size; + using _Impl::max_size; + + // modifiers + using _Impl::emplace; + using _Impl::emplace_hint; + using _Impl::insert; + // using _Impl::insert_range; + using _Impl::extract; + using _Impl::replace; + using _Impl::erase; + using _Impl::swap; + using _Impl::clear; + + // observers + using _Impl::key_comp; + using _Impl::value_comp; + + // map operations + using _Impl::find; + using _Impl::count; + using _Impl::contains; + using _Impl::lower_bound; + using _Impl::upper_bound; + using _Impl::equal_range; + }; + + template, + typename = _RequireNotAllocator<_Compare>> + flat_multiset(_KeyContainer, _Compare = _Compare()) + -> flat_multiset; + + template> + flat_multiset(_KeyContainer, _Alloc) + -> flat_multiset, _KeyContainer>; + + template, + typename = _RequireAllocator<_Alloc>> + flat_multiset(_KeyContainer, _Compare, _Alloc) + -> flat_multiset; + + template, + typename = _RequireNotAllocator<_Compare>> + flat_multiset(sorted_equivalent_t, _KeyContainer, _Compare = _Compare()) + -> flat_multiset; + + template> + flat_multiset(sorted_equivalent_t, _KeyContainer, _Alloc) + -> flat_multiset, _KeyContainer>; + + template, + typename = _RequireAllocator<_Alloc>> + flat_multiset(sorted_equivalent_t, _KeyContainer, _Compare, _Alloc) + -> flat_multiset; + + template>, + typename = _RequireInputIter<_InputIterator>, + typename = _RequireNotAllocator<_Compare>> + flat_multiset(_InputIterator, _InputIterator, _Compare = _Compare()) + -> flat_multiset<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>; + + template>, + typename = _RequireInputIter<_InputIterator>, + typename = _RequireNotAllocator<_Compare>> + flat_multiset(sorted_equivalent_t, _InputIterator, _InputIterator, _Compare = _Compare()) + -> flat_multiset<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>; + + // TODO: Implement from_range_t deduction guides. + + template, + typename = _RequireNotAllocator<_Compare>> + flat_multiset(initializer_list<_Key>, _Compare = _Compare()) + -> flat_multiset<_Key, _Compare>; + + template, + typename = _RequireNotAllocator<_Compare>> + flat_multiset(sorted_equivalent_t, initializer_list<_Key>, _Compare = _Compare()) + -> flat_multiset<_Key, _Compare>; + + template + struct uses_allocator, _Alloc> + : bool_constant> + { }; + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace std +#endif // __cpp_lib_flat_set +#endif // _GLIBCXX_FLAT_SET diff --git a/libstdc++-v3/testsuite/23_containers/flat_multiset/1.cc b/libstdc++-v3/testsuite/23_containers/flat_multiset/1.cc new file mode 100644 index 00000000000..97368cc5609 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/flat_multiset/1.cc @@ -0,0 +1,73 @@ +// { dg-do run { target c++23 } } + +#include +#include +#include + +template class Sequence> +void +test01() +{ + std::flat_multiset, Sequence> m; + static_assert( std::ranges::random_access_range ); + + m.insert(1); + m.insert(2); + m.insert(3); + m.insert(1); + m.insert(2); + m.insert(3); + m.insert(0); + VERIFY( m.size() == 7 ); + VERIFY( std::ranges::equal(m, (int[]){0, 1, 1, 2, 2, 3, 3}) ); + + m.clear(); + m.insert(m.begin(), 0); + m.insert(m.begin(), 1); + m.insert(m.begin(), 2); + m.insert(m.begin(), 3); + m.insert(m.begin(), 1); + m.insert(m.begin(), 2); + m.insert(m.begin(), 3); + m.insert(m.begin(), 0); + VERIFY( std::ranges::equal(m, (int[]){0, 0, 1, 1, 2, 2, 3, 3}) ); + + m.clear(); + m = {10,10}; + VERIFY( m.size() == 2 ); + m.insert({11,12,11}); + VERIFY( m.size() == 5 ); +} + +void +test02() +{ + std::flat_multiset> m; + static_assert( std::ranges::random_access_range ); + + auto r = m.insert(1); + VERIFY( *r == 1 ); + r = m.insert(2); + VERIFY( *r == 2 ); + r = m.insert(3); + VERIFY( *r == 3 ); + r = m.insert(1); + VERIFY( *r == 1 ); + r = m.insert(2); + VERIFY( *r == 2 ); + r = m.insert(3); + VERIFY( *r == 3 ); + VERIFY( m.size() == 6 ); + VERIFY( std::ranges::equal(m, (int[]){3, 3, 2, 2, 1, 1}) ); + + VERIFY( m.contains(3) && !m.contains(7) ); + VERIFY( m.count(3) == 2 ); +} + +int +main() +{ + test01(); + test01(); + test02(); +} diff --git a/libstdc++-v3/testsuite/23_containers/flat_set/1.cc b/libstdc++-v3/testsuite/23_containers/flat_set/1.cc new file mode 100644 index 00000000000..dd52f5de80b --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/flat_set/1.cc @@ -0,0 +1,78 @@ +// { dg-do run { target c++23 } } + +#include +#include +#include + +template class Sequence> +void +test01() +{ + std::flat_set, Sequence> m; + static_assert( std::ranges::random_access_range ); + + m.insert(1); + m.insert(2); + m.insert(3); + m.insert(1); + m.insert(2); + m.insert(3); + m.insert(0); + VERIFY( m.size() == 4 ); + VERIFY( std::ranges::equal(m, (int[]){0, 1, 2, 3}) ); + + for (int i = 0; i < 4; i++) + { + m.clear(); + m.insert(m.end(), 0); + m.insert(m.end(), 1); + m.insert(m.end(), 2); + m.insert(m.end(), 3); + m.insert(m.begin() + i, 1); + m.insert(m.begin() + i, 2); + m.insert(m.begin() + i, 3); + m.insert(m.begin() + i, 0); + VERIFY( std::ranges::equal(m, (int[]){0, 1, 2, 3}) ); + } + + m.clear(); + m = {10,10}; + VERIFY( m.size() == 1 ); + m.insert({11, 12, 11}); + VERIFY( m.size() == 3 ); + VERIFY( m.end()[-1] == 12 ); +} + +void +test02() +{ + std::flat_set> m; + static_assert( std::ranges::random_access_range ); + + auto r = m.insert(1); + VERIFY( *r.first == 1 && r.second ); + r = m.insert(2); + VERIFY( *r.first == 2 && r.second ); + r = m.insert(3); + VERIFY( *r.first == 3 && r.second ); + r = m.insert(1); + VERIFY( *r.first == 1 && !r.second ); + r = m.insert(2); + VERIFY( *r.first == 2 && !r.second ); + r = m.insert(3); + VERIFY( *r.first == 3 && !r.second ); + m.insert(0); + VERIFY( m.size() == 4 ); + VERIFY( std::ranges::equal(m, (int[]){3, 2, 1, 0}) ); + + VERIFY( m.contains(3) && !m.contains(7) ); + VERIFY( m.count(3) == 1 ); +} + +int +main() +{ + test01(); + test01(); + test02(); +}