From patchwork Tue Oct 1 03:43:57 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Palka X-Patchwork-Id: 1991306 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=MoBmJqwS; 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 4XHkNF1j7Hz1xtg for ; Tue, 1 Oct 2024 13:44:59 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id BB9EF3861003 for ; Tue, 1 Oct 2024 03:44:56 +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 2B2173858C41 for ; Tue, 1 Oct 2024 03:44:09 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 2B2173858C41 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 2B2173858C41 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=1727754254; cv=none; b=qke7E+BYqB8kv7GLt5TwMDD1JsjpoCivW3yN2j3VUfZDf7zztaUJrl5IeU2q78iN6P+FyQztnSr+ZhRQrLV7RD16AEteqSWSyzWucB446WF0hSxPx6Y2jMGzLX37Z6etafjfEWy3FHc4J+8QfjC++DJgB31afo8CuWF2G2BbI0M= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1727754254; c=relaxed/simple; bh=jF+CNvWdRjNJSpbyz5B+c3b8V8h6M1pKnyeUh+ogcAk=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=VKkr0Gg3zdtLpCb4Cweiyqo4YWVeT3V4scSMx6JkYVs86YJ6jdWX+MCZWLLb1twc/0d9/aI2o3lvjkm1fM4PtOMaIrR/XDtIVRGbeBH3BRXOIXjWyFxj8CC4Q6RcgmPItJly350eUWLoNXuqhDxTXgOhp1tAjUeKF85Rd0KfeLQ= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1727754248; 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; bh=sI1jNvplcKQ6LEFsT7D88uHzGU3JeTr2Xg55WzINUck=; b=MoBmJqwSXzHsx0F6Fo9RMM8Q76TKq3xHChIJpKkUMKLVUItEkaYazsaEqJpS6Jt+FISpTq 1k/6DhCFUlfTD0oIgFpjDBjjm4+B8AXKKlwgAkn/g8oKsouitxwj4B70l1sXVq/JYXC3zi JlmNB//aCUT8EjhzNiphvb3wwoWOOVw= Received: from mail-qv1-f72.google.com (mail-qv1-f72.google.com [209.85.219.72]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-315-_T_XOm-fMQiPRw5rHM4NfQ-1; Mon, 30 Sep 2024 23:44:06 -0400 X-MC-Unique: _T_XOm-fMQiPRw5rHM4NfQ-1 Received: by mail-qv1-f72.google.com with SMTP id 6a1803df08f44-6cb2dc0c233so12258066d6.0 for ; Mon, 30 Sep 2024 20:44:06 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1727754245; x=1728359045; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=sI1jNvplcKQ6LEFsT7D88uHzGU3JeTr2Xg55WzINUck=; b=HvpsLZ4jH8aj9PCtAvOCUtaKulGeU8AL2hsntsi9v8C5MNGZcQoYimT98vBL1RaPBL +tmVF/cQKNrqaH8LxlI2bsyA9F5W8EFnX9imgxw0Pz+4Vza8mY4nrL0CAW8i0jVSaBnm pkb1IZygboEqNABBI6/qV6V45ELqxHwCniSOJzxkzd3aJK+cE0p6RbEM09KTHL9OmQJd fXZi/A2w5NEXSTjt6v8MbW64RKjWL9fCAZE9oW5C8ssWWMd5yoXvE+yWHykanN4l14jp emUKy+KaCpZqFaooso5cWVGVAWN3PS56kmB0NvH/cyCy/P6zmvFwwiVgALYtZdRYIw74 FVJQ== X-Gm-Message-State: AOJu0YxRw6G68vJUMKz9c1JUEsw3h1OkQaxxLPL1gmfwsDZNVQdvGL/h 35n9LGLdw1XlOQvueYymnoIxUX2Rket/+rD79wvMiDu3pVLTr2rJevjptZCXUrzbalY9rCh9UhR vzmRf5qxJx2nf8HCJ6YqLM814ltwV2Uf9G9+eZaONdjxQhuL1P/FXir02nnccVo2jR8uT+o7dXR rM2jRbTxxeG7eeBMqIfrtAUKrf5xPcbgxw2oFV X-Received: by 2002:a05:6214:1d25:b0:6c3:589b:7ab4 with SMTP id 6a1803df08f44-6cb4bd9fa99mr75125676d6.5.1727754244295; Mon, 30 Sep 2024 20:44:04 -0700 (PDT) X-Google-Smtp-Source: AGHT+IH0fEbMTBWdUvQfTc+irkscm9jpC6Af+lBL4iNoZP9mf5vFn9rQjMtnCaarjU8TepziIMh5Jg== X-Received: by 2002:a05:6214:1d25:b0:6c3:589b:7ab4 with SMTP id 6a1803df08f44-6cb4bd9fa99mr75125316d6.5.1727754242855; Mon, 30 Sep 2024 20:44:02 -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.43.59 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 30 Sep 2024 20:44:01 -0700 (PDT) From: Patrick Palka To: gcc-patches@gcc.gnu.org Cc: libstdc++@gcc.gnu.org, Patrick Palka Subject: [PATCH 1/2] libstdc++: Implement C++23 (P0429R9) Date: Mon, 30 Sep 2024 23:43:57 -0400 Message-ID: <20241001034358.1375479-1-ppalka@redhat.com> X-Mailer: git-send-email 2.47.0.rc0 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=unavailable 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_map and std::flat_multimap from P0429R9. The implementation is shared as much as possible between the two adaptors via a common base class that's parameterized according to key uniqueness. The main known issues are: * the range insert() overload exceeds its complexity requirements since an idiomatic efficient implementation needs a non-buggy ranges::inplace_merge * exception safety is likely incomplete/buggy * unimplemented from_range_t constructors and insert_range function * the main workhorse function _M_try_emplace is probably buggy buggy wrt its handling of the hint parameter and could be simplified * more extensive testcases are a WIP The iterator type is encoded as a {pointer, index} pair instead of an {iterator, iterator} pair. I'm not sure which encoding is preferable? It seems the latter would allow for better debuggability when the underlying iterators are debug iterators. libstdc++-v3/ChangeLog: * include/Makefile.am: Add new header. * include/Makefile.in: Regenerate. * include/bits/stl_function.h (__transparent_comparator): Define. * include/bits/utility.h (sorted_unique_t): Define for C++23. (sorted_unique): Likewise. (sorted_equivalent_t): Likewise. (sorted_equivalent): Likewise. * include/bits/version.def (flat_map): Define. * include/bits/version.h: Regenerate. * include/std/flat_map: New file. * testsuite/23_containers/flat_map/1.cc: New test. * testsuite/23_containers/flat_multimap/1.cc: New test. --- libstdc++-v3/include/Makefile.am | 1 + libstdc++-v3/include/Makefile.in | 1 + libstdc++-v3/include/bits/stl_function.h | 6 + libstdc++-v3/include/bits/utility.h | 8 + libstdc++-v3/include/bits/version.def | 8 + libstdc++-v3/include/bits/version.h | 10 + libstdc++-v3/include/std/flat_map | 1477 +++++++++++++++++ .../testsuite/23_containers/flat_map/1.cc | 90 + .../23_containers/flat_multimap/1.cc | 77 + 9 files changed, 1678 insertions(+) create mode 100644 libstdc++-v3/include/std/flat_map create mode 100644 libstdc++-v3/testsuite/23_containers/flat_map/1.cc create mode 100644 libstdc++-v3/testsuite/23_containers/flat_multimap/1.cc diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am index 422a0f4bd0a..632bbafa63e 100644 --- a/libstdc++-v3/include/Makefile.am +++ b/libstdc++-v3/include/Makefile.am @@ -70,6 +70,7 @@ std_headers = \ ${std_srcdir}/deque \ ${std_srcdir}/execution \ ${std_srcdir}/filesystem \ + ${std_srcdir}/flat_map \ ${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 9fd4ab4848c..1ac963c4415 100644 --- a/libstdc++-v3/include/Makefile.in +++ b/libstdc++-v3/include/Makefile.in @@ -426,6 +426,7 @@ std_freestanding = \ @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/deque \ @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/execution \ @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/filesystem \ +@GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/flat_map \ @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/stl_function.h b/libstdc++-v3/include/bits/stl_function.h index c9123ccecae..c579ba9f47b 100644 --- a/libstdc++-v3/include/bits/stl_function.h +++ b/libstdc++-v3/include/bits/stl_function.h @@ -1426,6 +1426,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template using __has_is_transparent_t = typename __has_is_transparent<_Func, _SfinaeType>::type; + +#if __cpp_concepts + template + concept __transparent_comparator + = requires { typename _Func::is_transparent; }; +#endif #endif _GLIBCXX_END_NAMESPACE_VERSION diff --git a/libstdc++-v3/include/bits/utility.h b/libstdc++-v3/include/bits/utility.h index 4a6c16dc2e0..9e10ce2cb1c 100644 --- a/libstdc++-v3/include/bits/utility.h +++ b/libstdc++-v3/include/bits/utility.h @@ -308,6 +308,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION */ _GLIBCXX17_INLINE constexpr _Swallow_assign ignore{}; +#if __glibcxx_flat_map || __glibcxx_flat_set // >= C++23 + struct sorted_unique_t { explicit sorted_unique_t() = default; }; + inline constexpr sorted_unique_t sorted_unique{}; + + struct sorted_equivalent_t { explicit sorted_equivalent_t() = default; }; + inline constexpr sorted_equivalent_t sorted_equivalent{}; +#endif + _GLIBCXX_END_NAMESPACE_VERSION } // namespace diff --git a/libstdc++-v3/include/bits/version.def b/libstdc++-v3/include/bits/version.def index f2e28175b08..631eca7beac 100644 --- a/libstdc++-v3/include/bits/version.def +++ b/libstdc++-v3/include/bits/version.def @@ -1658,6 +1658,14 @@ ftms = { }; }; +ftms = { + name = flat_map; + 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 dcd93fd432d..1f3040fcbde 100644 --- a/libstdc++-v3/include/bits/version.h +++ b/libstdc++-v3/include/bits/version.h @@ -1830,6 +1830,16 @@ #endif /* !defined(__cpp_lib_adaptor_iterator_pair_constructor) && defined(__glibcxx_want_adaptor_iterator_pair_constructor) */ #undef __glibcxx_want_adaptor_iterator_pair_constructor +#if !defined(__cpp_lib_flat_map) +# if (__cplusplus >= 202100L) +# define __glibcxx_flat_map 202207L +# if defined(__glibcxx_want_all) || defined(__glibcxx_want_flat_map) +# define __cpp_lib_flat_map 202207L +# endif +# endif +#endif /* !defined(__cpp_lib_flat_map) && defined(__glibcxx_want_flat_map) */ +#undef __glibcxx_want_flat_map + #if !defined(__cpp_lib_formatters) # if (__cplusplus >= 202100L) && _GLIBCXX_HOSTED # define __glibcxx_formatters 202302L diff --git a/libstdc++-v3/include/std/flat_map b/libstdc++-v3/include/std/flat_map new file mode 100644 index 00000000000..83bb9c19d84 --- /dev/null +++ b/libstdc++-v3/include/std/flat_map @@ -0,0 +1,1477 @@ +// -*- 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_map + * This is a Standard C++ Library header. + */ + +#ifndef _GLIBCXX_FLAT_MAP +#define _GLIBCXX_FLAT_MAP 1 + +#ifdef _GLIBCXX_SYSHDR +#pragma GCC system_header +#endif + +#define __glibcxx_want_flat_map +#include + +#ifdef __cpp_lib_flat_map // >= 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_map; + + template + class flat_multimap; + + template + class _Flat_map_impl + { + static_assert(is_same_v<_Key, typename _KeyContainer::value_type>); + static_assert(is_same_v<_Tp, typename _MappedContainer::value_type>); + + static_assert(is_nothrow_swappable_v<_KeyContainer>); + static_assert(is_nothrow_swappable_v<_MappedContainer>); + + using _Derived = __conditional_t<_Multi, + flat_multimap<_Key, _Tp, _Compare, + _KeyContainer, _MappedContainer>, + flat_map<_Key, _Tp, _Compare, + _KeyContainer, _MappedContainer>>; + using __sorted_t = __conditional_t<_Multi, sorted_equivalent_t, sorted_unique_t>; + + public: + template struct _Iterator; + + using key_type = _Key; + using mapped_type = _Tp; + using value_type = pair; + using key_compare = _Compare; + using reference = pair; + using const_reference = pair; + using size_type = size_t; + using difference_type = ptrdiff_t; + using iterator = _Iterator; + using const_iterator = _Iterator; + using reverse_iterator = std::reverse_iterator; + using const_reverse_iterator = std::reverse_iterator; + using key_container_type = _KeyContainer; + using mapped_container_type = _MappedContainer; + + private: + using __emplace_result_t = __conditional_t<_Multi, iterator, pair>; + + public: + class value_compare + { + [[no_unique_address]] key_compare _M_comp; + value_compare(key_compare __c) : _M_comp(__c) { } + + public: + bool + operator()(const_reference __x, const_reference __y) const + { return _M_comp(__x.first, __y.first); } + + friend _Flat_map_impl; + }; + + struct containers + { + key_container_type keys; + mapped_container_type values; + }; + + // constructors + _Flat_map_impl() : _Flat_map_impl(key_compare()) { } + + explicit + _Flat_map_impl(const key_compare& __comp) + : _M_cont(), _M_comp(__comp) + { } + + _Flat_map_impl(key_container_type __key_cont, + mapped_container_type __mapped_cont, + const key_compare& __comp = key_compare()) + : _M_cont(std::move(__key_cont), std::move(__mapped_cont)), _M_comp(__comp) + { + __glibcxx_assert(_M_cont.keys.size() == _M_cont.values.size()); + _M_sort_uniq(); + } + + _Flat_map_impl(__sorted_t, + key_container_type __key_cont, + mapped_container_type __mapped_cont, + const key_compare& __comp = key_compare()) + : _M_cont(std::move(__key_cont), std::move(__mapped_cont)), _M_comp(__comp) + { __glibcxx_assert(_M_cont.keys.size() == _M_cont.values.size()); } + + template> + _Flat_map_impl(_InputIterator __first, _InputIterator __last, + const key_compare& __comp = key_compare()) + : _M_cont(), _M_comp(__comp) + { insert(__first, __last); } + + template> + _Flat_map_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_map_impl(initializer_list __il, + const key_compare& __comp = key_compare()) + : _Flat_map_impl(__il.begin(), __il.end(), __comp) + { } + + _Flat_map_impl(__sorted_t __s, + initializer_list __il, + const key_compare& __comp = key_compare()) + : _Flat_map_impl(__s, __il.begin(), __il.end(), __comp) + { } + + // constructors with allocators + + template + explicit + _Flat_map_impl(const _Alloc& __a) + : _Flat_map_impl(key_compare(), __a) + { } + + template + _Flat_map_impl(const key_compare& __comp, const _Alloc& __a) + : _M_cont(std::make_obj_using_allocator(__a), + std::make_obj_using_allocator(__a)), + _M_comp(__comp) + { } + + template + _Flat_map_impl(const key_container_type& __key_cont, + const mapped_container_type& __mapped_cont, + const _Alloc& __a) + : _Flat_map_impl(__key_cont, __mapped_cont, key_compare(), __a) + { } + + template + _Flat_map_impl(const key_container_type& __key_cont, + const mapped_container_type& __mapped_cont, + const key_compare& __comp, + const _Alloc& __a) + : _M_cont(std::make_obj_using_allocator(__a, __key_cont), + std::make_obj_using_allocator(__a, __mapped_cont)), + _M_comp(__comp) + { + __glibcxx_assert(_M_cont.keys.size() == _M_cont.values.size()); + _M_sort_uniq(); + } + + template + _Flat_map_impl(__sorted_t __s, + const key_container_type& __key_cont, + const mapped_container_type& __mapped_cont, + const _Alloc& __a) + : _Flat_map_impl(__s, __key_cont, __mapped_cont, key_compare(), __a) + { } + + template + _Flat_map_impl(__sorted_t __s, + const key_container_type& __key_cont, + const mapped_container_type& __mapped_cont, + const key_compare& __comp, + const _Alloc& __a) + : _M_comp(__comp), + _M_cont(std::make_obj_using_allocator(__a, __key_cont), + std::make_obj_using_allocator(__a, __mapped_cont)) + { __glibcxx_assert(_M_cont.keys.size() == _M_cont.values.size()); } + + template + _Flat_map_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_map_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_map_impl(_InputIterator __first, _InputIterator __last, + const _Alloc& __a) + : _Flat_map_impl(std::move(__first), std::move(__last), key_compare(), __a) + { } + + template> + _Flat_map_impl(_InputIterator __first, _InputIterator __last, + const key_compare& __comp, + const _Alloc& __a) + : _Flat_map_impl(__comp, __a) + { insert(__first, __last); } + + template> + _Flat_map_impl(__sorted_t __s, + _InputIterator __first, _InputIterator __last, + const _Alloc& __a) + : _Flat_map_impl(__s, std::move(__first), std::move(__last), key_compare(), __a) + { } + + template> + _Flat_map_impl(__sorted_t __s, + _InputIterator __first, _InputIterator __last, + const key_compare& __comp, + const _Alloc& __a) + : _Flat_map_impl(__comp, __a) + { insert(__s, __first, __last); } + + // TODO: Implement allocator-aware from_range_t constructors. + + template + _Flat_map_impl(initializer_list __il, + const _Alloc& __a) + : _Flat_map_impl(__il, key_compare(), __a) + { } + + template + _Flat_map_impl(initializer_list __il, + const key_compare& __comp, + const _Alloc& __a) + : _Flat_map_impl(__il.begin(), __il.end(), __comp, __a) + { } + + template + _Flat_map_impl(__sorted_t __s, + initializer_list __il, + const _Alloc& __a) + : _Flat_map_impl(__s, __il.begin(), __il.end(), key_compare(), __a) + { } + + template + _Flat_map_impl(__sorted_t __s, + initializer_list __il, + const key_compare& __comp, + const _Alloc& __a) + : _Flat_map_impl(__s, __il.begin(), __il.end(), __comp, __a) + { } + + _Derived& + operator=(initializer_list __il) + { + clear(); + insert(__il); + return static_cast<_Derived&>(*this); + } + + // iterators + iterator + begin() noexcept + { return {this, _M_cont.keys.cbegin()}; } + + const_iterator + begin() const noexcept + { return {this, _M_cont.keys.cbegin()}; } + + iterator + end() noexcept + { return {this, _M_cont.keys.cend()}; } + + const_iterator + end() const noexcept + { return {this, _M_cont.keys.cend()}; } + + reverse_iterator + rbegin() noexcept + { return reverse_iterator(end()); } + + const_reverse_iterator + rbegin() const noexcept + { return const_reverse_iterator(end()); } + + reverse_iterator + rend() noexcept + { return reverse_iterator(begin()); } + + const_reverse_iterator + rend() const noexcept + { return const_reverse_iterator(begin()); } + + const_iterator + cbegin() const noexcept + { return {this, _M_cont.keys.cbegin()}; } + + const_iterator + cend() const noexcept + { return {this, _M_cont.keys.cend()}; } + + const_reverse_iterator + crbegin() const noexcept + { return const_reverse_iterator(cend()); } + + const_reverse_iterator + crend() const noexcept + { return const_reverse_iterator(cbegin()); } + + // capacity + [[nodiscard]] bool + empty() const noexcept + { return _M_cont.keys.empty(); } + + size_type + size() const noexcept + { return _M_cont.keys.size(); } + + size_type + max_size() const noexcept + { return std::min(keys().max_size(), values().max_size()); } + + // element access + // operator[] and at defined directly in class flat_map only. + + // modifiers + template + pair + _M_try_emplace(optional __hint, _Key2&& __k, _Args&&... __args) + { + // TODO: Simplify and audit the hint handling. + typename key_container_type::iterator __key_it; + int __r = -1, __s = -1; + if (__hint.has_value() + && (__hint == cbegin() + || (__r = !_M_comp(__k, (*__hint)[-1].first))) // k >= hint[-1] + && (__hint == cend() + || (__s = !_M_comp((*__hint)[0].first, __k)))) // k <= hint[0] + { + __key_it = _M_cont.keys.begin() + __hint->_M_index; + if constexpr (!_Multi) + if (__r == 1 && !_M_comp(__key_it[-1], __k)) // k == hint[-1] + return {iterator{this, __key_it - 1}, false}; + } + else + { + auto __first = _M_cont.keys.begin(); + auto __last = _M_cont.keys.end(); + if (__r == 1) // k >= hint[-1] + __first += __hint->_M_index; + else if (__r == 0) // k < __hint[-1] + __last = __first + __hint->_M_index; + if constexpr (_Multi) + { + if (__s == 0) // hint[0] < k + // Insert before the leftmost equivalent key. + __key_it = ranges::lower_bound(__first, __last, __k, _M_comp); + else + // Insert after the rightmost equivalent key. + __key_it = ranges::upper_bound(std::make_reverse_iterator(__last), + std::make_reverse_iterator(__first), + __k, std::not_fn(_M_comp)).base(); + } + else + __key_it = ranges::lower_bound(__first, __last, __k, _M_comp); + } + + if constexpr (!_Multi) + if (__key_it != _M_cont.keys.end() && !_M_comp(__k, __key_it[0])) + return {iterator{this, __key_it}, false}; + + __key_it = _M_cont.keys.insert(__key_it, std::move(__k)); + __try + { + auto __value_it = _M_cont.values.begin() + (__key_it - _M_cont.keys.begin()); + _M_cont.values.emplace(__value_it, std::forward<_Args>(__args)...); + } + __catch(...) + { + _M_cont.keys.erase(__key_it); + __throw_exception_again; + } + return {iterator{this, __key_it}, true}; + } + + template + requires is_constructible_v + __emplace_result_t + emplace(_Args&&... __args) + { + value_type __p(std::forward<_Args>(__args)...); + auto __r = _M_try_emplace(nullopt, std::move(__p.first), std::move(__p.second)); + if constexpr (_Multi) + return __r.first; + else + return __r; + } + + template + iterator + emplace_hint(const_iterator __position, _Args&&... __args) + { + value_type __p(std::forward<_Args>(__args)...); + return _M_try_emplace(__position, std::move(__p.first), std::move(__p.second)).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) + { + // FIXME: This implementation fails its complexity requirements. + // We can't idiomatically implement an efficient version (as in the + // disabled code) until ranges::inplace_merge is fixed to dispatch + // on iterator concept instead of iterator category. +#if 0 + auto __n = size(); + for (; __first != __last; ++__first) + { + value_type __value = *__first; + _M_cont.keys.emplace_back(std::move(__value.first)); + _M_cont.values.emplace_back(std::move(__value.second)); + } + auto __zv = views::zip(_M_cont.keys, _M_cont.values); + ranges::sort(__zv.begin() + __n, __zv.end(), value_comp()); + ranges::inplace_merge(__zv.begin(), __zv.begin() + __n, __zv.end(), value_comp()); + if constexpr (!_Multi) + _M_unique(); +#else + for (; __first != __last; ++__first) + { + value_type __value = *__first; + _M_cont.keys.emplace_back(std::move(__value.first)); + _M_cont.values.emplace_back(std::move(__value.second)); + } + _M_sort_uniq(); +#endif + } + + template> + void + insert(__sorted_t, _InputIterator __first, _InputIterator __last) + { + // FIXME: This implementation fails its complexity requirements; see above. + insert(std::move(__first), std::move(__last)); + } + + // 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()); } + + containers + extract() && + { + struct _Guard + { + _Guard(_Flat_map_impl* __m) : _M_m(__m) { } + + ~_Guard() { _M_m->clear(); } + + _Flat_map_impl* _M_m; + } __clear_guard = {this}; + return {std::move(_M_cont.keys), std::move(_M_cont.values)}; + } + + void + replace(key_container_type&& __key_cont, mapped_container_type&& __mapped_cont) + { + __glibcxx_assert(__key_cont.size() == __mapped_cont.size()); + __try + { + _M_cont.keys = std::move(__key_cont); + _M_cont.values = std::move(__mapped_cont); + } + __catch(...) + { + clear(); + __throw_exception_again; + } + } + + // try_emplace defined directly in class flat_map only. + // insert_or_assign defined directly in class flat_map only. + + iterator + erase(iterator __position) + { return erase(static_cast(__position)); } + + iterator + erase(const_iterator __position) + { + auto __idx = __position._M_index; + auto __it = _M_cont.keys.erase(_M_cont.keys.begin() + __idx); + _M_cont.values.erase(_M_cont.values.begin() + __idx); + return iterator{this, __it}; + } + + 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) + { + auto __it = _M_cont.keys.erase(_M_cont.keys.begin() + __first._M_index, + _M_cont.keys.begin() + __last._M_index); + _M_cont.values.erase(_M_cont.values.begin() + __first._M_index, + _M_cont.values.begin() + __last._M_index); + return iterator{this, __it}; + } + + 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.keys.clear(); + _M_cont.values.clear(); + } + + // observers + key_compare + key_comp() const + { return _M_comp; } + + value_compare + value_comp() const + { return value_compare(key_comp()); } + + const key_container_type& + keys() const noexcept + { return _M_cont.keys; } + + const mapped_container_type& + values() const noexcept + { return _M_cont.values; } + + // 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->first)) + 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->first)) + 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) + { + auto __it = std::lower_bound(_M_cont.keys.begin(), _M_cont.keys.end(), + __x, _M_comp); + return {this, __it}; + } + + template + requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> + const_iterator + lower_bound(const _Key2& __x) const + { + auto __it = std::lower_bound(_M_cont.keys.begin(), _M_cont.keys.end(), + __x, _M_comp); + return {this, __it}; + } + + 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) + { + auto __it = std::upper_bound(_M_cont.keys.begin(), _M_cont.keys.end(), + __x, _M_comp); + return {this, __it}; + } + + template + requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> + const_iterator + upper_bound(const _Key2& __x) const + { + auto __it = std::upper_bound(_M_cont.keys.begin(), _M_cont.keys.end(), + __x, _M_comp); + return {this, __it}; + } + + 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) + { + auto [__first, __last] = ranges::equal_range(_M_cont.keys, __x, _M_comp); + return {{this, __first}, {this, __last}}; + } + + template + requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> + pair + equal_range(const _Key2& __x) const + { + auto [__first, __last] = ranges::equal_range(_M_cont.keys, __x, _M_comp); + return {{this, __first}, {this, __last}}; + } + + friend bool + operator==(const _Derived& __x, const _Derived& __y) + { + return ranges::equal(__x._M_cont.keys, __y._M_cont.keys) + && ranges::equal(__x._M_cont.values, __y._M_cont.values); + } + + 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) + { + __try + { + auto __zv = views::zip(__c._M_cont.keys, __c._M_cont.values); + auto __sr = ranges::remove_if(__zv, __pred); + auto __erased = __sr.size(); + __c.erase(__c.end() - __erased, __c.end()); + return __erased; + } + __catch(...) + { + __c.clear(); + __throw_exception_again; + } + } + + private: + containers _M_cont; + [[no_unique_address]] _Compare _M_comp; + + void + _M_sort_uniq() + { + auto __zv = views::zip(_M_cont.keys, _M_cont.values); + ranges::sort(__zv, value_comp()); + if constexpr (!_Multi) + _M_unique(); + } + + void + _M_unique() requires (!_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.first, __y.first) && !_M_comp(__y.first, __x.first); } + + [[no_unique_address]] key_compare _M_comp; + }; + + auto __zv = views::zip(_M_cont.keys, _M_cont.values); + auto __it = ranges::unique(__zv, __key_equiv(_M_comp)).begin(); + auto __n = __it - __zv.begin(); + _M_cont.keys.erase(_M_cont.keys.begin() + __n, _M_cont.keys.end()); + _M_cont.values.erase(_M_cont.values.begin() + __n, _M_cont.values.end()); + } + }; + + template + template + class _Flat_map_impl<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer, _Multi>::_Iterator + { + using __size_type = typename _Flat_map_impl::size_type; + + public: + using iterator_category = input_iterator_tag; + using iterator_concept = random_access_iterator_tag; + using value_type = pair; + using reference = pair&>; + using difference_type = ptrdiff_t; + + _Iterator() = default; + _Iterator(const _Iterator&) = default; + _Iterator& operator=(const _Iterator&) = default; + + // Allow conversion from iterator to const_iterator + _Iterator(const _Iterator& __it) requires _Const + : _M_cont(__it._M_cont), _M_index(__it._M_index) + { } + + reference + operator*() const noexcept + { return {_M_cont->keys[_M_index], _M_cont->values[_M_index]}; } + + struct pointer + { + reference __p; + + const reference* + operator->() const noexcept + { return std::__addressof(__p); } + }; + + pointer + operator->() const + { return pointer{operator*()}; } + + reference + operator[](difference_type __n) const noexcept + { return *(*this + __n); } + + _Iterator& + operator++() noexcept + { + ++_M_index; + return *this; + } + + _Iterator& + operator--() noexcept + { + --_M_index; + return *this; + } + + _Iterator + operator++(int) noexcept + { + auto __tmp = *this; + ++*this; + return __tmp; + } + + _Iterator + operator--(int) noexcept + { + auto __tmp = *this; + --*this; + return __tmp; + } + + _Iterator& + operator+=(difference_type __n) noexcept + { + _M_index += __n; + return *this; + } + + _Iterator& + operator-=(difference_type __n) noexcept + { + _M_index -= __n; + return *this; + } + + private: + friend _Flat_map_impl; + friend _Iterator; + + _Iterator(_Flat_map_impl* __fm, typename key_container_type::const_iterator __it) + requires (!_Const) + : _M_cont(std::__addressof(__fm->_M_cont)), _M_index(__it - __fm->keys().cbegin()) + { } + + _Iterator(const _Flat_map_impl* __fm, typename key_container_type::const_iterator __it) + requires _Const + : _M_cont(std::__addressof(__fm->_M_cont)), _M_index(__it - __fm->keys().cbegin()) + { } + + friend _Iterator + operator+(_Iterator __it, difference_type __n) noexcept + { + __it += __n; + return __it; + } + + friend _Iterator + operator+(difference_type __n, _Iterator __it) noexcept + { + __it += __n; + return __it; + } + + friend _Iterator + operator-(_Iterator __it, difference_type __n) noexcept + { + __it -= __n; + return __it; + } + + friend difference_type + operator-(const _Iterator& __x, const _Iterator& __y) noexcept + { + __glibcxx_assert(__x._M_cont == __y._M_cont); + return __x._M_index - __y._M_index; + } + + friend bool + operator==(const _Iterator& __x, const _Iterator& __y) noexcept + { + __glibcxx_assert(__x._M_cont == __y._M_cont); + __glibcxx_assert((__x._M_index == size_t(-1)) == (__y._M_index == size_t(-1))); + return __x._M_index == __y._M_index; + } + + friend strong_ordering + operator<=>(const _Iterator& __x, const _Iterator& __y) + { + __glibcxx_assert(__x._M_cont == __y._M_cont); + __glibcxx_assert((__x._M_index == size_t(-1)) == (__y._M_index == size_t(-1))); + return __x._M_index <=> __y._M_index; + } + + ranges::__maybe_const_t<_Const, containers>* _M_cont = nullptr; + __size_type _M_index = -1; + }; + + /* Class template flat_map - container adaptor + * + * @ingroup + */ + template, + typename _KeyContainer = vector<_Key>, + typename _MappedContainer = vector<_Tp>> + class flat_map + : private _Flat_map_impl<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer, false> + { + using _Impl = _Flat_map_impl<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer, false>; + friend _Impl; + + public: + // types + using typename _Impl::key_type; + using typename _Impl::mapped_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::key_container_type; + using typename _Impl::mapped_container_type; + using typename _Impl::value_compare; + using typename _Impl::containers; + + // 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; + + // element access + mapped_type& + operator[](const key_type& __x) + { return operator[](__x); } + + mapped_type& + operator[](key_type&& __x) + { return operator[](std::move(__x)); } + + template + requires same_as, _Key> || __transparent_comparator<_Compare> + mapped_type& + operator[](_Key2&& __x) + { return try_emplace(std::forward<_Key2>(__x)).first->second; } + + mapped_type& + at(const key_type& __x) + { return at(__x); } + + const mapped_type& + at(const key_type& __x) const + { return at(__x); } + + template + requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> + mapped_type& + at(const _Key2& __x) + { + auto __it = this->find(__x); + if (__it == this->end()) + __throw_out_of_range("flat_map::at"); + return __it->second; + } + + template + requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> + const mapped_type& + at(const _Key2& __x) const + { + auto __it = this->find(__x); + if (__it == this->end()) + __throw_out_of_range("flat_map::at"); + return __it->second; + } + + // 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; + + template + requires is_constructible_v + pair + try_emplace(const key_type& __k, _Args&&... __args) + { return _Impl::_M_try_emplace(nullopt, __k, std::forward<_Args>(__args)...); } + + template + requires is_constructible_v + pair + try_emplace(key_type&& __k, _Args&&... __args) + { + return _Impl::_M_try_emplace(nullopt, std::move(__k), + std::forward<_Args>(__args)...); + } + + template + requires __transparent_comparator<_Compare> + && is_constructible_v + && is_constructible_v + && (!is_convertible_v<_Key2&&, const_iterator>) + && (!is_convertible_v<_Key2&&, iterator>) + pair + try_emplace(_Key2&& __k, _Args&&... __args) + { + return _Impl::_M_try_emplace(nullopt, std::forward<_Key2>(__k), + std::forward<_Args>(__args)...); + } + + template + requires is_constructible_v + iterator + try_emplace(const_iterator __hint, const key_type& __k, _Args&&... __args) + { return _Impl::_M_try_emplace(__hint, __k, std::forward<_Args>(__args)...).first; } + + template + requires is_constructible_v + iterator + try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args) + { + return _Impl::_M_try_emplace(__hint, std::move(__k), + std::forward<_Args>(__args)...).first; + } + + template + requires __transparent_comparator<_Compare> + && is_constructible_v + && is_constructible_v + iterator + try_emplace(const_iterator __hint, _Key2&& __k, _Args&&... __args) + { + return _Impl::_M_try_emplace(__hint, std::forward<_Key2>(__k), + std::forward<_Args>(__args)...).first; + } + + template + requires is_assignable_v + && is_constructible_v + pair + insert_or_assign(const key_type& __k, _Mapped&& __obj) + { return insert_or_assign(__k, std::forward<_Mapped>(__obj)); } + + template + requires is_assignable_v + && is_constructible_v + pair + insert_or_assign(key_type&& __k, _Mapped&& __obj) + { + return insert_or_assign(std::move(__k), + std::forward<_Mapped>(__obj)); + } + + template + requires (same_as, _Key> || __transparent_comparator<_Compare>) + && is_constructible_v + && is_assignable_v + && is_constructible_v + pair + insert_or_assign(_Key2&& __k, _Mapped&& __obj) + { + auto __r = _Impl::_M_try_emplace(nullopt, std::forward<_Key2>(__k), + std::forward<_Mapped>(__obj)); + if (!__r.second) + __r.first->second = std::forward<_Mapped>(__obj); + return __r; + } + + template + requires is_assignable_v + && is_constructible_v + iterator + insert_or_assign(const_iterator __hint, const key_type& __k, _Mapped&& __obj) + { + return insert_or_assign(__hint, __k, + std::forward<_Mapped>(__obj)); + } + + template + requires is_assignable_v + && is_constructible_v + iterator + insert_or_assign(const_iterator __hint, key_type&& __k, _Mapped&& __obj) + { + return insert_or_assign(__hint, std::move(__k), + std::forward<_Mapped>(__obj)); + } + + template + requires (same_as, _Key> || __transparent_comparator<_Compare>) + && is_constructible_v + && is_assignable_v + && is_constructible_v + iterator + insert_or_assign(const_iterator __hint, _Key2&& __k, _Mapped&& __obj) + { + auto __r = _Impl::_M_try_emplace(__hint, std::forward<_Key2>(__k), + std::forward<_Mapped>(__obj)); + if (!__r.second) + __r.first->second = std::forward<_Mapped>(__obj); + return __r.first; + } + + // observers + using _Impl::key_comp; + using _Impl::value_comp; + using _Impl::keys; + using _Impl::values; + + // 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_map(_KeyContainer, _MappedContainer, _Compare = _Compare()) + -> flat_map; + + template> + flat_map(_KeyContainer, _MappedContainer, _Alloc) + -> flat_map, _KeyContainer, _MappedContainer>; + + template, + typename = _RequireAllocator<_Alloc>> + flat_map(_KeyContainer, _MappedContainer, _Compare, _Alloc) + -> flat_map; + + template, + typename = _RequireNotAllocator<_Compare>> + flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Compare = _Compare()) + -> flat_map; + + template> + flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Alloc) + -> flat_map, _KeyContainer, _MappedContainer>; + + template, + typename = _RequireAllocator<_Alloc>> + flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Compare, _Alloc) + -> flat_map; + + template>, + typename = _RequireInputIter<_InputIterator>, + typename = _RequireNotAllocator<_Compare>> + flat_map(_InputIterator, _InputIterator, _Compare = _Compare()) + -> flat_map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>; + + template>, + typename = _RequireInputIter<_InputIterator>, + typename = _RequireNotAllocator<_Compare>> + flat_map(sorted_unique_t, _InputIterator, _InputIterator, _Compare = _Compare()) + -> flat_map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>; + + // TODO: Implement from_range_t deduction guides. + + template, + typename = _RequireNotAllocator<_Compare>> + flat_map(initializer_list>, _Compare = _Compare()) + -> flat_map<_Key, _Tp, _Compare>; + + template, + typename = _RequireNotAllocator<_Compare>> + flat_map(sorted_unique_t, initializer_list>, _Compare = _Compare()) + -> flat_map<_Key, _Tp, _Compare>; + + template + struct uses_allocator, _Alloc> + : bool_constant + && uses_allocator_v<_MappedContainer, _Alloc>> + { }; + + /* Class template flat_multimap - container adaptor + * + * @ingroup + */ + template, + typename _KeyContainer = vector<_Key>, + typename _MappedContainer = vector<_Tp>> + class flat_multimap + : private _Flat_map_impl<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer, true> + { + using _Impl = _Flat_map_impl<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer, true>; + friend _Impl; + + public: + // types + using typename _Impl::key_type; + using typename _Impl::mapped_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::key_container_type; + using typename _Impl::mapped_container_type; + using typename _Impl::value_compare; + using typename _Impl::containers; + + // 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; + using _Impl::keys; + using _Impl::values; + + // 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_multimap(_KeyContainer, _MappedContainer, _Compare = _Compare()) + -> flat_multimap; + + template> + flat_multimap(_KeyContainer, _MappedContainer, _Alloc) + -> flat_multimap, _KeyContainer, _MappedContainer>; + + template, + typename = _RequireAllocator<_Alloc>> + flat_multimap(_KeyContainer, _MappedContainer, _Compare, _Alloc) + -> flat_multimap; + + template, + typename = _RequireNotAllocator<_Compare>> + flat_multimap(sorted_equivalent_t, _KeyContainer, _MappedContainer, _Compare = _Compare()) + -> flat_multimap; + + template> + flat_multimap(sorted_equivalent_t, _KeyContainer, _MappedContainer, _Alloc) + -> flat_multimap, _KeyContainer, _MappedContainer>; + + template, + typename = _RequireAllocator<_Alloc>> + flat_multimap(sorted_equivalent_t, _KeyContainer, _MappedContainer, _Compare, _Alloc) + -> flat_multimap; + + template>, + typename = _RequireInputIter<_InputIterator>, + typename = _RequireNotAllocator<_Compare>> + flat_multimap(_InputIterator, _InputIterator, _Compare = _Compare()) + -> flat_multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>; + + template>, + typename = _RequireInputIter<_InputIterator>, + typename = _RequireNotAllocator<_Compare>> + flat_multimap(sorted_equivalent_t, _InputIterator, _InputIterator, _Compare = _Compare()) + -> flat_multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>; + + // TODO: Implement from_range_t deduction guides. + + template, + typename = _RequireNotAllocator<_Compare>> + flat_multimap(initializer_list>, _Compare = _Compare()) + -> flat_multimap<_Key, _Tp, _Compare>; + + template, + typename = _RequireNotAllocator<_Compare>> + flat_multimap(sorted_equivalent_t, initializer_list>, _Compare = _Compare()) + -> flat_multimap<_Key, _Tp, _Compare>; + + template + struct uses_allocator, + _Alloc> + : bool_constant + && uses_allocator_v<_MappedContainer, _Alloc>> + { }; + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace std +#endif // __cpp_lib_flat_map +#endif // _GLIBCXX_FLAT_MAP diff --git a/libstdc++-v3/testsuite/23_containers/flat_map/1.cc b/libstdc++-v3/testsuite/23_containers/flat_map/1.cc new file mode 100644 index 00000000000..e56ac5394f3 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/flat_map/1.cc @@ -0,0 +1,90 @@ +// { dg-do run { target c++23 } } + +#include +#include +#include + +template class Sequence> +void +test01() +{ + std::flat_map, Sequence, Sequence> m; + static_assert( std::ranges::random_access_range ); + + m.insert({1,-1}); + m.insert({2,-2}); + m.insert({3,-3}); + m.insert({1,-4}); + m.insert({2,-5}); + m.insert({3,-6}); + m.insert({0, 0}); + VERIFY( m.size() == 4 ); + VERIFY( std::ranges::equal(m.keys(), (int[]){0, 1, 2, 3}) ); + VERIFY( std::ranges::equal(m.values(), (int[]){0, -1, -2, -3}) ); + + for (int i = 0; i < 4; i++) + { + m.clear(); + m.insert(m.end(), {0, 0}); + m.insert(m.end(), {1,-1}); + m.insert(m.end(), {2,-2}); + m.insert(m.end(), {3,-3}); + m.insert(m.begin() + i, {1,-4}); + m.insert(m.begin() + i, {2,-5}); + m.insert(m.begin() + i, {3,-6}); + m.insert(m.begin() + i, {0,-7}); + VERIFY( std::ranges::equal(m.keys(), (int[]){0, 1, 2, 3}) ); + VERIFY( std::ranges::equal(m.values(), (int[]){0, -1, -2, -3}) ); + } + + m.clear(); + m = {{10,0},{10,1}}; + VERIFY( m.size() == 1 ); + m.insert({{11,2},{12,3},{11,4}}); + VERIFY( m.size() == 3 ); + VERIFY( m[10] == 0 ); + VERIFY( m[11] == 2 ); + VERIFY( m[12] == 3 ); + m[20] = 42; + VERIFY( m[20] == 42 ); + VERIFY( m.end()[-1] == std::pair(20,42) ); +} + +void +test02() +{ + std::flat_map> m; + static_assert( std::ranges::random_access_range ); + + auto r = m.insert({1,-1}); + VERIFY( r.first->first == 1 && r.first->second == -1 && r.second ); + r = m.insert({2,-2}); + VERIFY( r.first->first == 2 && r.first->second == -2 && r.second ); + r = m.insert({3,-3}); + VERIFY( r.first->first == 3 && r.first->second == -3 && r.second ); + r = m.insert({1,-4}); + VERIFY( r.first->first == 1 && r.first->second == -1 && !r.second ); + r = m.insert({2,-5}); + VERIFY( r.first->first == 2 && r.first->second == -2 && !r.second ); + r = m.insert({3,-6}); + VERIFY( r.first->first == 3 && r.first->second == -3 && !r.second ); + r = m.insert_or_assign(0, 0); + VERIFY( r.first->first == 0 && r.first->second == 0 && r.second ); + r = m.insert_or_assign(0, 1); + VERIFY( r.first->first == 0 && r.first->second == 1 && !r.second ); + VERIFY( *m.insert_or_assign(m.end(), 0, 2) == std::pair(0, 2) ); + VERIFY( m.size() == 4 ); + VERIFY( std::ranges::equal(m.keys(), (int[]){3, 2, 1, 0}) ); + VERIFY( std::ranges::equal(m.values(), (int[]){-3, -2, -1, 2}) ); + + VERIFY( m.contains(3) && !m.contains(7) ); + VERIFY( m.count(3) == 1 ); +} + +int +main() +{ + test01(); + test01(); + test02(); +} diff --git a/libstdc++-v3/testsuite/23_containers/flat_multimap/1.cc b/libstdc++-v3/testsuite/23_containers/flat_multimap/1.cc new file mode 100644 index 00000000000..3a245b94ebe --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/flat_multimap/1.cc @@ -0,0 +1,77 @@ +// { dg-do run { target c++23 } } + +#include +#include +#include + +template class Sequence> +void +test01() +{ + std::flat_multimap, Sequence, Sequence> m; + static_assert( std::ranges::random_access_range ); + + m.insert({1,-1}); + m.insert({2,-2}); + m.insert({3,-3}); + m.insert({1,-4}); + m.insert({2,-5}); + m.insert({3,-6}); + m.insert({0, 0}); + VERIFY( m.size() == 7 ); + VERIFY( std::ranges::equal(m.keys(), (int[]){0, 1, 1, 2, 2, 3, 3}) ); + VERIFY( std::ranges::equal(m.values(), (int[]){0, -1, -4, -2, -5, -3, -6}) ); + + m.clear(); + m.insert(m.begin(), {0, 0}); + m.insert(m.begin(), {1,-1}); + m.insert(m.begin(), {2,-2}); + m.insert(m.begin(), {3,-3}); + m.insert(m.begin(), {1,-4}); + m.insert(m.begin(), {2,-5}); + m.insert(m.begin(), {3,-6}); + m.insert(m.begin(), {0,-7}); + VERIFY( std::ranges::equal(m.keys(), (int[]){0, 0, 1, 1, 2, 2, 3, 3}) ); + VERIFY( std::ranges::equal(m.values(), (int[]){-7, 0, -4, -1, -5, -2, -6, -3}) ); + + m.clear(); + m = {{10,0},{10,1}}; + VERIFY( m.size() == 2 ); + m.insert({{11,2},{12,3},{11,4}}); + VERIFY( m.size() == 5 ); + VERIFY( m.end()[-1] == std::pair(12,3) ); +} + +void +test02() +{ + std::flat_multimap> m; + static_assert( std::ranges::random_access_range ); + + auto r = m.insert({1,-1}); + VERIFY( r->first == 1 && r->second == -1 ); + r = m.insert({2,-2}); + VERIFY( r->first == 2 && r->second == -2 ); + r = m.insert({3,-3}); + VERIFY( r->first == 3 && r->second == -3 ); + r = m.insert({1,-4}); + VERIFY( r->first == 1 && r->second == -4 ); + r = m.insert({2,-5}); + VERIFY( r->first == 2 && r->second == -5 ); + r = m.insert({3,-6}); + VERIFY( r->first == 3 && r->second == -6 ); + VERIFY( m.size() == 6 ); + VERIFY( std::ranges::equal(m.keys(), (int[]){3, 3, 2, 2, 1, 1}) ); + VERIFY( std::ranges::equal(m.values(), (int[]){-3, -6, -2, -5, -1, -4}) ); + + VERIFY( m.contains(3) && !m.contains(7) ); + VERIFY( m.count(3) == 2 ); +} + +int +main() +{ + test01(); + test01(); + test02(); +}