Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/2226155/?format=api
{ "id": 2226155, "url": "http://patchwork.ozlabs.org/api/patches/2226155/?format=api", "web_url": "http://patchwork.ozlabs.org/project/gcc/patch/bmm.hhuay3vzv6.gcc.gcc-TEST.ppalka.9.1.2@forge-stage.sourceware.org/", "project": { "id": 17, "url": "http://patchwork.ozlabs.org/api/projects/17/?format=api", "name": "GNU Compiler Collection", "link_name": "gcc", "list_id": "gcc-patches.gcc.gnu.org", "list_email": "gcc-patches@gcc.gnu.org", "web_url": null, "scm_url": null, "webscm_url": null, "list_archive_url": "", "list_archive_url_format": "", "commit_url_format": "" }, "msgid": "<bmm.hhuay3vzv6.gcc.gcc-TEST.ppalka.9.1.2@forge-stage.sourceware.org>", "list_archive_url": null, "date": "2026-04-22T10:14:43", "name": "[v1,2/3] libstdc++: Implement C++23 <flat_map> (P0429R9)", "commit_ref": null, "pull_url": null, "state": "new", "archived": false, "hash": "0e2e6c3868769106ac0f4ef32c88e7ffaa205e66", "submitter": { "id": 93215, "url": "http://patchwork.ozlabs.org/api/people/93215/?format=api", "name": "ppalka via Sourceware Forge", "email": "forge-bot+ppalka@forge-stage.sourceware.org" }, "delegate": null, "mbox": "http://patchwork.ozlabs.org/project/gcc/patch/bmm.hhuay3vzv6.gcc.gcc-TEST.ppalka.9.1.2@forge-stage.sourceware.org/mbox/", "series": [ { "id": 500959, "url": "http://patchwork.ozlabs.org/api/series/500959/?format=api", "web_url": "http://patchwork.ozlabs.org/project/gcc/list/?series=500959", "date": "2026-04-22T10:14:41", "name": "libstdc++: Implement C++23 <flat_map> and <flat_set>", "version": 1, "mbox": "http://patchwork.ozlabs.org/series/500959/mbox/" } ], "comments": "http://patchwork.ozlabs.org/api/patches/2226155/comments/", "check": "pending", "checks": "http://patchwork.ozlabs.org/api/patches/2226155/checks/", "tags": {}, "related": [], "headers": { "Return-Path": "<gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org>", "X-Original-To": [ "incoming@patchwork.ozlabs.org", "gcc-patches@gcc.gnu.org" ], "Delivered-To": [ "patchwork-incoming@legolas.ozlabs.org", "gcc-patches@gcc.gnu.org" ], "Authentication-Results": [ "legolas.ozlabs.org;\n spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org\n (client-ip=38.145.34.32; helo=vm01.sourceware.org;\n envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org;\n receiver=patchwork.ozlabs.org)", "sourceware.org; dmarc=none (p=none dis=none)\n header.from=forge-stage.sourceware.org", "sourceware.org;\n spf=pass smtp.mailfrom=forge-stage.sourceware.org", "server2.sourceware.org;\n arc=none smtp.remote-ip=38.145.34.39" ], "Received": [ "from vm01.sourceware.org (vm01.sourceware.org [38.145.34.32])\n\t(using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)\n\t key-exchange x25519 server-signature ECDSA (secp384r1) server-digest SHA384)\n\t(No client certificate requested)\n\tby legolas.ozlabs.org (Postfix) with ESMTPS id 4g0wCZ2241z1y2d\n\tfor <incoming@patchwork.ozlabs.org>; Wed, 22 Apr 2026 20:18:02 +1000 (AEST)", "from vm01.sourceware.org (localhost [127.0.0.1])\n\tby sourceware.org (Postfix) with ESMTP id 45F464BA903B\n\tfor <incoming@patchwork.ozlabs.org>; Wed, 22 Apr 2026 10:18:00 +0000 (GMT)", "from forge-stage.sourceware.org (vm08.sourceware.org [38.145.34.39])\n by sourceware.org (Postfix) with ESMTPS id 97F5A4BA902E\n for <gcc-patches@gcc.gnu.org>; Wed, 22 Apr 2026 10:15:59 +0000 (GMT)", "from forge-stage.sourceware.org (localhost [IPv6:::1])\n (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)\n key-exchange x25519 server-signature ECDSA (prime256v1) server-digest SHA256)\n (No client certificate requested)\n by forge-stage.sourceware.org (Postfix) with ESMTPS id 6C85B40555\n for <gcc-patches@gcc.gnu.org>; Wed, 22 Apr 2026 10:15:59 +0000 (UTC)" ], "DKIM-Filter": [ "OpenDKIM Filter v2.11.0 sourceware.org 45F464BA903B", "OpenDKIM Filter v2.11.0 sourceware.org 97F5A4BA902E" ], "DMARC-Filter": "OpenDMARC Filter v1.4.2 sourceware.org 97F5A4BA902E", "ARC-Filter": "OpenARC Filter v1.0.0 sourceware.org 97F5A4BA902E", "ARC-Seal": "i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1776852959; cv=none;\n b=uqcDUGcEqYhNQX9XF4wd6W1D2ECbliJydDkKCTH7w7xMpkG2fvRKYRsY8RT/OV5d8a5C8g8m1YwcDfrrd2J+U/G//Pf8YHB28WXYAZyGQ7eXLSSVqPv49EySLxdLR6ewWEXh53V5T5Hx7TIZB3qUmaoTz5i7Ph92lGq91KRJcf8=", "ARC-Message-Signature": "i=1; a=rsa-sha256; d=sourceware.org; s=key;\n t=1776852959; c=relaxed/simple;\n bh=CgPO4Zwveb9CKYP2lKDg3yismChMJExjsn4zzEP9cuk=;\n h=From:Date:Subject:To:Message-ID;\n b=QXXU1rFmeoZUOAAhZpC7RsbBay1hhhFW/DXNZtPwdtV1Yja5TyO+NjAvK8GRRnfMZv11Pg8x6P9zkl8P4uM/ooM8zpZtF3Ug5o4pHC1sOiJR569KBiwg3ARXqd2aLQKb1ThKt2sr45ICWAs95A+ZAsXrM11XMQi9iHa+GW8xAPY=", "ARC-Authentication-Results": "i=1; server2.sourceware.org", "From": "ppalka via Sourceware Forge\n <forge-bot+ppalka@forge-stage.sourceware.org>", "Date": "Wed, 22 Apr 2026 10:14:43 +0000", "Subject": "[PATCH v1 2/3] libstdc++: Implement C++23 <flat_map> (P0429R9)", "To": "gcc-patches mailing list <gcc-patches@gcc.gnu.org>", "Message-ID": "\n <bmm.hhuay3vzv6.gcc.gcc-TEST.ppalka.9.1.2@forge-stage.sourceware.org>", "X-Mailer": "batrachomyomachia", "X-Requested-Reviewer": "redi", "X-Pull-Request-Organization": "gcc", "X-Pull-Request-Repository": "gcc-TEST", "X-Pull-Request": "https://forge.sourceware.org/gcc/gcc-TEST/pulls/9", "References": "\n <bmm.hhuay3vzv6.gcc.gcc-TEST.ppalka.9.1.0@forge-stage.sourceware.org>", "In-Reply-To": "\n <bmm.hhuay3vzv6.gcc.gcc-TEST.ppalka.9.1.0@forge-stage.sourceware.org>", "X-Patch-URL": "\n https://forge.sourceware.org/gcc/gcc-TEST/commit/f067bf07a92ad0984fcb52368fc37e880e05997e", "X-BeenThere": "gcc-patches@gcc.gnu.org", "X-Mailman-Version": "2.1.30", "Precedence": "list", "List-Id": "Gcc-patches mailing list <gcc-patches.gcc.gnu.org>", "List-Unsubscribe": "<https://gcc.gnu.org/mailman/options/gcc-patches>,\n <mailto:gcc-patches-request@gcc.gnu.org?subject=unsubscribe>", "List-Archive": "<https://gcc.gnu.org/pipermail/gcc-patches/>", "List-Post": "<mailto:gcc-patches@gcc.gnu.org>", "List-Help": "<mailto:gcc-patches-request@gcc.gnu.org?subject=help>", "List-Subscribe": "<https://gcc.gnu.org/mailman/listinfo/gcc-patches>,\n <mailto:gcc-patches-request@gcc.gnu.org?subject=subscribe>", "Reply-To": "gcc-patches mailing list <gcc-patches@gcc.gnu.org>,\n ppalka@gcc.gnu.org", "Errors-To": "gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org" }, "content": "From: Patrick Palka <ppalka@redhat.com>\n\nThis implements the C++23 container adaptors std::flat_map and\nstd::flat_multimap from P0429R9. The implementation is shared\nas much as possible between the two adaptors via a common base\nclass that's parameterized according to key uniqueness.\n\nThe iterator type is encoded as a {pointer, index} pair instead of an\n{iterator, iterator} pair. I'm not sure which encoding is preferable?\nIt seems the latter would allow for better debuggability when the\nunderlying iterators are debug iterators.\n\nlibstdc++-v3/ChangeLog:\n\n\t* include/Makefile.am: Add new header <flat_map>.\n\t* include/Makefile.in: Regenerate.\n\t* include/bits/alloc_traits.h (__not_allocator_like): New concept.\n\t* include/bits/stl_function.h (__transparent_comparator): Likewise.\n\t* include/bits/stl_iterator_base_types.h (__has_input_iter_cat):\n\tLikewise.\n\t* include/bits/utility.h (sorted_unique_t): Define for C++23.\n\t(sorted_unique): Likewise.\n\t(sorted_equivalent_t): Likewise.\n\t(sorted_equivalent): Likewise.\n\t* include/bits/version.def (flat_map): Define.\n\t* include/bits/version.h: Regenerate.\n\t* include/bits/precompiled/stdc++.h: Include <flat_map>.\n\t* include/std/flat_map: New file.\n\t* src/c++23/std.cc.in: Export <flat_map>.\n\t* testsuite/23_containers/flat_map/1.cc: New test.\n\t* testsuite/23_containers/flat_multimap/1.cc: New test.\n---\n libstdc++-v3/include/Makefile.am | 1 +\n libstdc++-v3/include/Makefile.in | 1 +\n libstdc++-v3/include/bits/alloc_traits.h | 3 +\n libstdc++-v3/include/bits/stl_function.h | 6 +\n .../include/bits/stl_iterator_base_types.h | 6 +\n libstdc++-v3/include/bits/uses_allocator.h | 5 +\n libstdc++-v3/include/bits/utility.h | 8 +\n libstdc++-v3/include/bits/version.def | 8 +\n libstdc++-v3/include/bits/version.h | 10 +\n libstdc++-v3/include/precompiled/stdc++.h | 1 +\n libstdc++-v3/include/std/flat_map | 1570 +++++++++++++++++\n libstdc++-v3/src/c++23/std.cc.in | 10 +\n .../testsuite/23_containers/flat_map/1.cc | 166 ++\n .../23_containers/flat_multimap/1.cc | 141 ++\n 14 files changed, 1936 insertions(+)\n create mode 100644 libstdc++-v3/include/std/flat_map\n create mode 100644 libstdc++-v3/testsuite/23_containers/flat_map/1.cc\n create mode 100644 libstdc++-v3/testsuite/23_containers/flat_multimap/1.cc", "diff": "diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am\nindex 6efd3cd5f1c8..b606bcd49359 100644\n--- a/libstdc++-v3/include/Makefile.am\n+++ b/libstdc++-v3/include/Makefile.am\n@@ -70,6 +70,7 @@ std_headers = \\\n \t${std_srcdir}/deque \\\n \t${std_srcdir}/execution \\\n \t${std_srcdir}/filesystem \\\n+\t${std_srcdir}/flat_map \\\n \t${std_srcdir}/format \\\n \t${std_srcdir}/forward_list \\\n \t${std_srcdir}/fstream \\\ndiff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in\nindex 3b5f93ce185d..d277f87905b9 100644\n--- a/libstdc++-v3/include/Makefile.in\n+++ b/libstdc++-v3/include/Makefile.in\n@@ -426,6 +426,7 @@ std_freestanding = \\\n @GLIBCXX_HOSTED_TRUE@\t${std_srcdir}/deque \\\n @GLIBCXX_HOSTED_TRUE@\t${std_srcdir}/execution \\\n @GLIBCXX_HOSTED_TRUE@\t${std_srcdir}/filesystem \\\n+@GLIBCXX_HOSTED_TRUE@\t${std_srcdir}/flat_map \\\n @GLIBCXX_HOSTED_TRUE@\t${std_srcdir}/format \\\n @GLIBCXX_HOSTED_TRUE@\t${std_srcdir}/forward_list \\\n @GLIBCXX_HOSTED_TRUE@\t${std_srcdir}/fstream \\\ndiff --git a/libstdc++-v3/include/bits/alloc_traits.h b/libstdc++-v3/include/bits/alloc_traits.h\nindex 76d5646afe57..5d8a952ec1bf 100644\n--- a/libstdc++-v3/include/bits/alloc_traits.h\n+++ b/libstdc++-v3/include/bits/alloc_traits.h\n@@ -957,6 +957,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n typename _Alloc::value_type;\n __a.deallocate(__a.allocate(1u), 1u);\n };\n+\n+ template<typename _Alloc>\n+ concept __not_allocator_like = !__allocator_like<_Alloc>;\n #endif\n /// @endcond\n #endif // C++11\ndiff --git a/libstdc++-v3/include/bits/stl_function.h b/libstdc++-v3/include/bits/stl_function.h\nindex 8c77471fbf54..a472c3d79f3a 100644\n--- a/libstdc++-v3/include/bits/stl_function.h\n+++ b/libstdc++-v3/include/bits/stl_function.h\n@@ -1426,6 +1426,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n template<typename _Func, typename _SfinaeType>\n using __has_is_transparent_t\n = typename __has_is_transparent<_Func, _SfinaeType>::type;\n+\n+#if __cpp_concepts\n+ template<typename _Func>\n+ concept __transparent_comparator\n+ = requires { typename _Func::is_transparent; };\n+#endif\n #endif\n \n _GLIBCXX_END_NAMESPACE_VERSION\ndiff --git a/libstdc++-v3/include/bits/stl_iterator_base_types.h b/libstdc++-v3/include/bits/stl_iterator_base_types.h\nindex 710e367c9786..a58358e1059b 100644\n--- a/libstdc++-v3/include/bits/stl_iterator_base_types.h\n+++ b/libstdc++-v3/include/bits/stl_iterator_base_types.h\n@@ -253,6 +253,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n __enable_if_t<is_convertible<__iter_category_t<_InIter>,\n \t\t\t\t input_iterator_tag>::value>;\n \n+#if __cpp_concepts\n+ template<typename _InIter>\n+ concept __has_input_iter_cat\n+ = is_convertible_v<__iter_category_t<_InIter>, input_iterator_tag>;\n+#endif\n+\n template<typename _It,\n \t typename _Cat = __iter_category_t<_It>>\n struct __is_random_access_iter\ndiff --git a/libstdc++-v3/include/bits/uses_allocator.h b/libstdc++-v3/include/bits/uses_allocator.h\nindex 2ebb75f71209..7504244d67f8 100644\n--- a/libstdc++-v3/include/bits/uses_allocator.h\n+++ b/libstdc++-v3/include/bits/uses_allocator.h\n@@ -134,6 +134,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n uses_allocator<_Tp, _Alloc>::value;\n #endif // C++17\n \n+#if __cpp_concepts\n+ template<typename _Alloc, typename... _Ts>\n+ concept __allocator_for = (uses_allocator_v<_Ts, _Alloc> && ...);\n+#endif\n+\n template<template<typename...> class _Predicate,\n \t typename _Tp, typename _Alloc, typename... _Args>\n struct __is_uses_allocator_predicate\ndiff --git a/libstdc++-v3/include/bits/utility.h b/libstdc++-v3/include/bits/utility.h\nindex 4a6c16dc2e01..9e10ce2cb1c1 100644\n--- a/libstdc++-v3/include/bits/utility.h\n+++ b/libstdc++-v3/include/bits/utility.h\n@@ -308,6 +308,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n */\n _GLIBCXX17_INLINE constexpr _Swallow_assign ignore{};\n \n+#if __glibcxx_flat_map || __glibcxx_flat_set // >= C++23\n+ struct sorted_unique_t { explicit sorted_unique_t() = default; };\n+ inline constexpr sorted_unique_t sorted_unique{};\n+\n+ struct sorted_equivalent_t { explicit sorted_equivalent_t() = default; };\n+ inline constexpr sorted_equivalent_t sorted_equivalent{};\n+#endif\n+\n _GLIBCXX_END_NAMESPACE_VERSION\n } // namespace\n \ndiff --git a/libstdc++-v3/include/bits/version.def b/libstdc++-v3/include/bits/version.def\nindex 8d4b8e9b383e..171ee2780e8d 100644\n--- a/libstdc++-v3/include/bits/version.def\n+++ b/libstdc++-v3/include/bits/version.def\n@@ -1663,6 +1663,14 @@ ftms = {\n };\n };\n \n+ftms = {\n+ name = flat_map;\n+ values = {\n+ v = 202207;\n+ cxxmin = 23;\n+ };\n+};\n+\n ftms = {\n name = formatters;\n values = {\ndiff --git a/libstdc++-v3/include/bits/version.h b/libstdc++-v3/include/bits/version.h\nindex c556aca38fa8..5e1858855eb6 100644\n--- a/libstdc++-v3/include/bits/version.h\n+++ b/libstdc++-v3/include/bits/version.h\n@@ -1835,6 +1835,16 @@\n #endif /* !defined(__cpp_lib_adaptor_iterator_pair_constructor) && defined(__glibcxx_want_adaptor_iterator_pair_constructor) */\n #undef __glibcxx_want_adaptor_iterator_pair_constructor\n \n+#if !defined(__cpp_lib_flat_map)\n+# if (__cplusplus >= 202100L)\n+# define __glibcxx_flat_map 202207L\n+# if defined(__glibcxx_want_all) || defined(__glibcxx_want_flat_map)\n+# define __cpp_lib_flat_map 202207L\n+# endif\n+# endif\n+#endif /* !defined(__cpp_lib_flat_map) && defined(__glibcxx_want_flat_map) */\n+#undef __glibcxx_want_flat_map\n+\n #if !defined(__cpp_lib_formatters)\n # if (__cplusplus >= 202100L) && _GLIBCXX_HOSTED\n # define __glibcxx_formatters 202302L\ndiff --git a/libstdc++-v3/include/precompiled/stdc++.h b/libstdc++-v3/include/precompiled/stdc++.h\nindex 15f7f3fe34a9..67ee00d073bb 100644\n--- a/libstdc++-v3/include/precompiled/stdc++.h\n+++ b/libstdc++-v3/include/precompiled/stdc++.h\n@@ -225,6 +225,7 @@\n \n #if __cplusplus > 202002L\n #include <expected>\n+#include <flat_map>\n #include <generator>\n #include <print>\n #include <spanstream>\ndiff --git a/libstdc++-v3/include/std/flat_map b/libstdc++-v3/include/std/flat_map\nnew file mode 100644\nindex 000000000000..d2ade71fa3ca\n--- /dev/null\n+++ b/libstdc++-v3/include/std/flat_map\n@@ -0,0 +1,1570 @@\n+// <flat_map> -*- C++ -*-\n+\n+// Copyright The GNU Toolchain Authors.\n+//\n+// This file is part of the GNU ISO C++ Library. This library is free\n+// software; you can redistribute it and/or modify it under the\n+// terms of the GNU General Public License as published by the\n+// Free Software Foundation; either version 3, or (at your option)\n+// any later version.\n+\n+// This library is distributed in the hope that it will be useful,\n+// but WITHOUT ANY WARRANTY; without even the implied warranty of\n+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\n+// GNU General Public License for more details.\n+\n+// Under Section 7 of GPL version 3, you are granted additional\n+// permissions described in the GCC Runtime Library Exception, version\n+// 3.1, as published by the Free Software Foundation.\n+\n+// You should have received a copy of the GNU General Public License and\n+// a copy of the GCC Runtime Library Exception along with this program;\n+// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see\n+// <http://www.gnu.org/licenses/>.\n+\n+/** @file include/flat_map\n+ * This is a Standard C++ Library header.\n+ */\n+\n+#ifndef _GLIBCXX_FLAT_MAP\n+#define _GLIBCXX_FLAT_MAP 1\n+\n+#ifdef _GLIBCXX_SYSHDR\n+#pragma GCC system_header\n+#endif\n+\n+#define __glibcxx_want_flat_map\n+#include <bits/version.h>\n+\n+#ifdef __cpp_lib_flat_map // >= C++23\n+\n+#include <compare>\n+#include <initializer_list>\n+\n+#include <exception>\n+#include <functional> // not_fn\n+#include <optional>\n+#include <ranges> // views::zip\n+#include <type_traits>\n+#include <vector>\n+#include <bits/functexcept.h>\n+#include <bits/stl_algo.h>\n+#include <bits/stl_function.h> // less\n+#include <bits/stl_pair.h>\n+#include <bits/uses_allocator_args.h> // make_obj_using_allocator\n+#include <bits/ranges_algo.h>\n+\n+namespace std _GLIBCXX_VISIBILITY(default)\n+{\n+_GLIBCXX_BEGIN_NAMESPACE_VERSION\n+\n+ template<typename _Key, typename _Tp, typename _Compare,\n+\t typename _KeyContainer, typename _MappedContainer>\n+ class flat_map;\n+\n+ template<typename _Key, typename _Tp, typename _Compare,\n+\t typename _KeyContainer, typename _MappedContainer>\n+ class flat_multimap;\n+\n+ template<typename _Key, typename _Tp, typename _Compare,\n+\t typename _KeyContainer, typename _MappedContainer, bool _Multi>\n+ class _Flat_map_impl\n+ {\n+ static_assert(is_same_v<_Key, typename _KeyContainer::value_type>);\n+ static_assert(is_same_v<_Tp, typename _MappedContainer::value_type>);\n+\n+ static_assert(is_nothrow_swappable_v<_KeyContainer>);\n+ static_assert(is_nothrow_swappable_v<_MappedContainer>);\n+\n+ using _Derived = __conditional_t<_Multi,\n+\t\t\t\t flat_multimap<_Key, _Tp, _Compare,\n+\t\t\t\t\t\t _KeyContainer, _MappedContainer>,\n+\t\t\t\t flat_map<_Key, _Tp, _Compare,\n+\t\t\t\t\t\t_KeyContainer, _MappedContainer>>;\n+ using __sorted_t = __conditional_t<_Multi, sorted_equivalent_t, sorted_unique_t>;\n+\n+ public:\n+ template<bool _Const> struct _Iterator;\n+\n+ using key_type = _Key;\n+ using mapped_type = _Tp;\n+ using value_type = pair<key_type, mapped_type>;\n+ using key_compare = _Compare;\n+ using reference = pair<const key_type&, mapped_type&>;\n+ using const_reference = pair<const key_type&, const mapped_type&>;\n+ using size_type = size_t;\n+ using difference_type = ptrdiff_t;\n+ using iterator = _Iterator<false>;\n+ using const_iterator = _Iterator<true>;\n+ using reverse_iterator = std::reverse_iterator<iterator>;\n+ using const_reverse_iterator = std::reverse_iterator<const_iterator>;\n+ using key_container_type = _KeyContainer;\n+ using mapped_container_type = _MappedContainer;\n+\n+ private:\n+ using __emplace_result_t = __conditional_t<_Multi, iterator, pair<iterator, bool>>;\n+\n+ public:\n+ class value_compare\n+ {\n+\t[[no_unique_address]] key_compare _M_comp;\n+\tvalue_compare(key_compare __c) : _M_comp(__c) { }\n+\n+ public:\n+\tbool\n+\toperator()(const_reference __x, const_reference __y) const\n+\t{ return _M_comp(__x.first, __y.first); }\n+\n+\tfriend _Flat_map_impl;\n+ };\n+\n+ struct containers\n+ {\n+\tkey_container_type keys;\n+\tmapped_container_type values;\n+ };\n+\n+ private:\n+ struct _ClearGuard\n+ {\n+\tcontainers* _M_cont;\n+\n+\t_ClearGuard(containers& __cont)\n+\t: _M_cont(std::__addressof(__cont))\n+\t{ }\n+\n+\t~_ClearGuard()\n+\t{\n+\t if (_M_cont)\n+\t {\n+\t _M_cont->keys.clear();\n+\t _M_cont->values.clear();\n+\t }\n+\t}\n+\n+\tvoid\n+\t_M_disable()\n+\t{ _M_cont = nullptr; }\n+ };\n+\n+ _ClearGuard\n+ _M_make_clear_guard()\n+ { return _ClearGuard{this->_M_cont}; }\n+\n+ public:\n+ // constructors\n+ _Flat_map_impl() : _Flat_map_impl(key_compare()) { }\n+\n+ explicit\n+ _Flat_map_impl(const key_compare& __comp)\n+ : _M_cont(), _M_comp(__comp)\n+ { }\n+\n+ _Flat_map_impl(key_container_type __key_cont,\n+\t\t mapped_container_type __mapped_cont,\n+\t\t const key_compare& __comp = key_compare())\n+ : _M_cont(std::move(__key_cont), std::move(__mapped_cont)), _M_comp(__comp)\n+ {\n+\t__glibcxx_assert(_M_cont.keys.size() == _M_cont.values.size());\n+\t_M_sort_uniq();\n+ }\n+\n+ _Flat_map_impl(__sorted_t,\n+\t\t key_container_type __key_cont,\n+\t\t mapped_container_type __mapped_cont,\n+\t\t const key_compare& __comp = key_compare())\n+ : _M_cont(std::move(__key_cont), std::move(__mapped_cont)), _M_comp(__comp)\n+ {\n+\t__glibcxx_assert(_M_cont.keys.size() == _M_cont.values.size());\n+\t_GLIBCXX_DEBUG_ASSERT(ranges::is_sorted(_M_cont.keys, _M_comp));\n+ }\n+\n+ template<__has_input_iter_cat _InputIterator>\n+\t_Flat_map_impl(_InputIterator __first, _InputIterator __last,\n+\t\t const key_compare& __comp = key_compare())\n+\t: _M_cont(), _M_comp(__comp)\n+\t{ insert(__first, __last); }\n+\n+ template<__has_input_iter_cat _InputIterator>\n+\t_Flat_map_impl(__sorted_t __s,\n+\t\t _InputIterator __first, _InputIterator __last,\n+\t\t const key_compare& __comp = key_compare())\n+\t: _M_cont(), _M_comp(__comp)\n+\t{ insert(__s, __first, __last); }\n+\n+ template<__detail::__container_compatible_range<value_type> _Rg>\n+\t_Flat_map_impl(from_range_t __fr, _Rg&& __rg)\n+\t: _Flat_map_impl(__fr, std::forward<_Rg>(__rg), key_compare())\n+\t{ }\n+\n+ template<__detail::__container_compatible_range<value_type> _Rg>\n+\t_Flat_map_impl(from_range_t __fr, _Rg&& __rg, const key_compare& __comp)\n+\t: _Flat_map_impl(__comp)\n+\t{ insert_range(std::forward<_Rg>(__rg)); }\n+\n+ _Flat_map_impl(initializer_list<value_type> __il,\n+\t\t const key_compare& __comp = key_compare())\n+ : _Flat_map_impl(__il.begin(), __il.end(), __comp)\n+ { }\n+\n+ _Flat_map_impl(__sorted_t __s,\n+\t\t initializer_list<value_type> __il,\n+\t\t const key_compare& __comp = key_compare())\n+ : _Flat_map_impl(__s, __il.begin(), __il.end(), __comp)\n+ { }\n+\n+ // constructors with allocators\n+\n+ template<__allocator_for<key_container_type, mapped_container_type> _Alloc>\n+\texplicit\n+\t_Flat_map_impl(const _Alloc& __a)\n+\t: _Flat_map_impl(key_compare(), __a)\n+\t{ }\n+\n+ template<__allocator_for<key_container_type, mapped_container_type> _Alloc>\n+\t_Flat_map_impl(const key_compare& __comp, const _Alloc& __a)\n+\t: _M_cont(std::make_obj_using_allocator<key_container_type>(__a),\n+\t\t std::make_obj_using_allocator<mapped_container_type>(__a)),\n+\t _M_comp(__comp)\n+\t{ }\n+\n+ template<__allocator_for<key_container_type, mapped_container_type> _Alloc>\n+\t_Flat_map_impl(const key_container_type& __key_cont,\n+\t\t const mapped_container_type& __mapped_cont,\n+\t\t const _Alloc& __a)\n+\t: _Flat_map_impl(__key_cont, __mapped_cont, key_compare(), __a)\n+\t{ }\n+\n+ template<__allocator_for<key_container_type, mapped_container_type> _Alloc>\n+\t_Flat_map_impl(const key_container_type& __key_cont,\n+\t\t const mapped_container_type& __mapped_cont,\n+\t\t const key_compare& __comp,\n+\t\t const _Alloc& __a)\n+\t: _M_cont(std::make_obj_using_allocator<key_container_type>(__a, __key_cont),\n+\t\t std::make_obj_using_allocator<mapped_container_type>(__a, __mapped_cont)),\n+\t _M_comp(__comp)\n+\t{\n+\t __glibcxx_assert(_M_cont.keys.size() == _M_cont.values.size());\n+\t _M_sort_uniq();\n+\t}\n+\n+ template<__allocator_for<key_container_type, mapped_container_type> _Alloc>\n+\t_Flat_map_impl(__sorted_t __s,\n+\t\t const key_container_type& __key_cont,\n+\t\t const mapped_container_type& __mapped_cont,\n+\t\t const _Alloc& __a)\n+\t: _Flat_map_impl(__s, __key_cont, __mapped_cont, key_compare(), __a)\n+\t{ }\n+\n+ template<__allocator_for<key_container_type, mapped_container_type> _Alloc>\n+\t_Flat_map_impl(__sorted_t,\n+\t\t const key_container_type& __key_cont,\n+\t\t const mapped_container_type& __mapped_cont,\n+\t\t const key_compare& __comp,\n+\t\t const _Alloc& __a)\n+\t: _M_cont(std::make_obj_using_allocator<key_container_type>(__a, __key_cont),\n+\t\t std::make_obj_using_allocator<mapped_container_type>(__a, __mapped_cont)),\n+\t _M_comp(__comp)\n+\t{\n+\t __glibcxx_assert(_M_cont.keys.size() == _M_cont.values.size());\n+\t_GLIBCXX_DEBUG_ASSERT(ranges::is_sorted(_M_cont.keys, _M_comp));\n+\t}\n+\n+ template<__allocator_for<key_container_type, mapped_container_type> _Alloc>\n+\t_Flat_map_impl(const _Derived& __x, const _Alloc& __a)\n+\t: _M_cont(std::make_obj_using_allocator<key_container_type>(__a, __x._M_cont.keys),\n+\t\t std::make_obj_using_allocator<mapped_container_type>(__a, __x._M_cont.values)),\n+\t _M_comp(__x._M_comp)\n+\t{ }\n+\n+ template<__allocator_for<key_container_type, mapped_container_type> _Alloc>\n+\t_Flat_map_impl(_Derived&& __x, const _Alloc& __a)\n+\t: _M_cont(std::make_obj_using_allocator<key_container_type>\n+\t\t (__a, std::move(__x._M_cont.keys)),\n+\t\t std::make_obj_using_allocator<mapped_container_type>\n+\t\t (__a, std::move(__x._M_cont.values))),\n+\t _M_comp(__x._M_comp)\n+\t{ }\n+\n+ template<__has_input_iter_cat _InputIterator,\n+\t __allocator_for<key_container_type, mapped_container_type> _Alloc>\n+\t_Flat_map_impl(_InputIterator __first, _InputIterator __last,\n+\t\t const _Alloc& __a)\n+\t: _Flat_map_impl(std::move(__first), std::move(__last), key_compare(), __a)\n+\t{ }\n+\n+ template<__has_input_iter_cat _InputIterator,\n+\t __allocator_for<key_container_type, mapped_container_type> _Alloc>\n+\t_Flat_map_impl(_InputIterator __first, _InputIterator __last,\n+\t\t const key_compare& __comp,\n+\t\t const _Alloc& __a)\n+\t: _Flat_map_impl(__comp, __a)\n+\t{ insert(__first, __last); }\n+\n+ template<__has_input_iter_cat _InputIterator,\n+\t __allocator_for<key_container_type, mapped_container_type> _Alloc>\n+\t_Flat_map_impl(__sorted_t __s,\n+\t\t _InputIterator __first, _InputIterator __last,\n+\t\t const _Alloc& __a)\n+\t: _Flat_map_impl(__s, std::move(__first), std::move(__last), key_compare(), __a)\n+\t{ }\n+\n+ template<__has_input_iter_cat _InputIterator,\n+\t __allocator_for<key_container_type, mapped_container_type> _Alloc>\n+\t_Flat_map_impl(__sorted_t __s,\n+\t\t _InputIterator __first, _InputIterator __last,\n+\t\t const key_compare& __comp,\n+\t\t const _Alloc& __a)\n+\t: _Flat_map_impl(__comp, __a)\n+\t{ insert(__s, __first, __last); }\n+\n+ template<__detail::__container_compatible_range<value_type> _Rg,\n+\t __allocator_for<key_container_type, mapped_container_type> _Alloc>\n+\t_Flat_map_impl(from_range_t __fr, _Rg&& __rg,\n+\t\t const _Alloc& __a)\n+\t: _Flat_map_impl(__fr, std::forward<_Rg>(__rg), key_compare(), __a)\n+\t{ }\n+\n+ template<__detail::__container_compatible_range<value_type> _Rg,\n+\t __allocator_for<key_container_type, mapped_container_type> _Alloc>\n+\t_Flat_map_impl(from_range_t, _Rg&& __rg, const key_compare& __comp,\n+\t\t const _Alloc& __a)\n+\t: _Flat_map_impl(__comp, __a)\n+\t{ insert_range(std::forward<_Rg>(__rg)); }\n+\n+ template<__allocator_for<key_container_type, mapped_container_type> _Alloc>\n+\t_Flat_map_impl(initializer_list<value_type> __il,\n+\t\t const _Alloc& __a)\n+\t: _Flat_map_impl(__il, key_compare(), __a)\n+\t{ }\n+\n+ template<__allocator_for<key_container_type, mapped_container_type> _Alloc>\n+\t_Flat_map_impl(initializer_list<value_type> __il,\n+\t\t const key_compare& __comp,\n+\t\t const _Alloc& __a)\n+\t: _Flat_map_impl(__il.begin(), __il.end(), __comp, __a)\n+\t{ }\n+\n+ template<__allocator_for<key_container_type, mapped_container_type> _Alloc>\n+\t_Flat_map_impl(__sorted_t __s,\n+\t\t initializer_list<value_type> __il,\n+\t\t const _Alloc& __a)\n+\t: _Flat_map_impl(__s, __il.begin(), __il.end(), key_compare(), __a)\n+\t{ }\n+\n+ template<__allocator_for<key_container_type, mapped_container_type> _Alloc>\n+\t_Flat_map_impl(__sorted_t __s,\n+\t\t initializer_list<value_type> __il,\n+\t\t const key_compare& __comp,\n+\t\t const _Alloc& __a)\n+\t: _Flat_map_impl(__s, __il.begin(), __il.end(), __comp, __a)\n+\t{ }\n+\n+ _Derived&\n+ operator=(initializer_list<value_type> __il)\n+ {\n+\tclear();\n+\tinsert(__il);\n+\treturn static_cast<_Derived&>(*this);\n+ }\n+\n+ // iterators\n+ iterator\n+ begin() noexcept\n+ { return {this, _M_cont.keys.cbegin()}; }\n+\n+ const_iterator\n+ begin() const noexcept\n+ { return {this, _M_cont.keys.cbegin()}; }\n+\n+ iterator\n+ end() noexcept\n+ { return {this, _M_cont.keys.cend()}; }\n+\n+ const_iterator\n+ end() const noexcept\n+ { return {this, _M_cont.keys.cend()}; }\n+\n+ reverse_iterator\n+ rbegin() noexcept\n+ { return reverse_iterator(end()); }\n+\n+ const_reverse_iterator\n+ rbegin() const noexcept\n+ { return const_reverse_iterator(end()); }\n+\n+ reverse_iterator\n+ rend() noexcept\n+ { return reverse_iterator(begin()); }\n+\n+ const_reverse_iterator\n+ rend() const noexcept\n+ { return const_reverse_iterator(begin()); }\n+\n+ const_iterator\n+ cbegin() const noexcept\n+ { return {this, _M_cont.keys.cbegin()}; }\n+\n+ const_iterator\n+ cend() const noexcept\n+ { return {this, _M_cont.keys.cend()}; }\n+\n+ const_reverse_iterator\n+ crbegin() const noexcept\n+ { return const_reverse_iterator(cend()); }\n+\n+ const_reverse_iterator\n+ crend() const noexcept\n+ { return const_reverse_iterator(cbegin()); }\n+\n+ // capacity\n+ [[nodiscard]] bool\n+ empty() const noexcept\n+ { return _M_cont.keys.empty(); }\n+\n+ size_type\n+ size() const noexcept\n+ { return _M_cont.keys.size(); }\n+\n+ size_type\n+ max_size() const noexcept\n+ { return std::min<size_type>(keys().max_size(), values().max_size()); }\n+\n+ // element access\n+ // operator[] and at defined directly in class flat_map only.\n+\n+ // modifiers\n+ template<typename _Key2, typename... _Args>\n+\tpair<iterator, bool>\n+\t_M_try_emplace(optional<const_iterator> __hint, _Key2&& __k, _Args&&... __args)\n+\t{\n+\t // TODO: Simplify and audit the hint handling.\n+\t typename key_container_type::iterator __key_it;\n+\t typename mapped_container_type::iterator __value_it;\n+\t int __r = -1, __s = -1;\n+\t if (__hint.has_value()\n+\t && (__hint == cbegin()\n+\t\t || (__r = !_M_comp(__k, (*__hint)[-1].first))) // k >= hint[-1]\n+\t && (__hint == cend()\n+\t\t || (__s = !_M_comp((*__hint)[0].first, __k)))) // k <= hint[0]\n+\t {\n+\t __key_it = _M_cont.keys.begin() + __hint->_M_index;\n+\t if constexpr (!_Multi)\n+\t\tif (__r == 1 && !_M_comp(__key_it[-1], __k)) // k == hint[-1]\n+\t\t return {iterator{this, __key_it - 1}, false};\n+\t }\n+\t else\n+\t {\n+\t auto __first = _M_cont.keys.begin();\n+\t auto __last = _M_cont.keys.end();\n+\t if (__r == 1) // k >= hint[-1]\n+\t\t__first += __hint->_M_index;\n+\t else if (__r == 0) // k < __hint[-1]\n+\t\t__last = __first + __hint->_M_index;\n+\t if constexpr (_Multi)\n+\t\t{\n+\t\t if (__s == 0) // hint[0] < k\n+\t\t // Insert before the leftmost equivalent key.\n+\t\t __key_it = std::lower_bound(__first, __last, __k, _M_comp);\n+\t\t else\n+\t\t // Insert after the rightmost equivalent key.\n+\t\t __key_it = std::upper_bound(std::make_reverse_iterator(__last),\n+\t\t\t\t\t\tstd::make_reverse_iterator(__first),\n+\t\t\t\t\t\t__k, std::not_fn(_M_comp)).base();\n+\t\t}\n+\t else\n+\t\t__key_it = std::lower_bound(__first, __last, __k, _M_comp);\n+\t }\n+\n+\t if constexpr (!_Multi)\n+\t if (__key_it != _M_cont.keys.end() && !_M_comp(__k, __key_it[0]))\n+\t return {iterator{this, __key_it}, false};\n+\n+\t auto __guard = _M_make_clear_guard();\n+\t __key_it = _M_cont.keys.insert(__key_it, std::move(__k));\n+\t __value_it = _M_cont.values.begin() + (__key_it - _M_cont.keys.begin());\n+\t _M_cont.values.emplace(__value_it, std::forward<_Args>(__args)...);\n+\t __guard._M_disable();\n+\t return {iterator{this, __key_it}, true};\n+\t}\n+\n+ template<typename... _Args>\n+\trequires is_constructible_v<value_type, _Args...>\n+\t__emplace_result_t\n+\templace(_Args&&... __args)\n+\t{\n+\t value_type __p(std::forward<_Args>(__args)...);\n+\t auto __r = _M_try_emplace(nullopt, std::move(__p.first), std::move(__p.second));\n+\t if constexpr (_Multi)\n+\t return __r.first;\n+\t else\n+\t return __r;\n+\t}\n+\n+ template<typename... _Args>\n+\titerator\n+\templace_hint(const_iterator __position, _Args&&... __args)\n+\t{\n+\t value_type __p(std::forward<_Args>(__args)...);\n+\t return _M_try_emplace(__position, std::move(__p.first), std::move(__p.second)).first;\n+\t}\n+\n+ __emplace_result_t\n+ insert(const value_type& __x)\n+ { return emplace(__x); }\n+\n+ __emplace_result_t\n+ insert(value_type&& __x)\n+ { return emplace(std::move(__x)); }\n+\n+ iterator\n+ insert(const_iterator __position, const value_type& __x)\n+ { return emplace_hint(__position, __x); }\n+\n+ iterator\n+ insert(const_iterator __position, value_type&& __x)\n+ { return emplace_hint(__position, std::move(__x)); }\n+\n+ template<typename _Arg>\n+\trequires is_constructible_v<value_type, _Arg>\n+\t__emplace_result_t\n+\tinsert(_Arg&& __x)\n+\t{ return emplace(std::forward<_Arg>(__x)); }\n+\n+ template<typename _Arg>\n+\trequires is_constructible_v<value_type, _Arg>\n+\titerator\n+\tinsert(const_iterator __position, _Arg&& __x)\n+\t{ return emplace_hint(__position, std::forward<_Arg>(__x)); }\n+\n+ template<__has_input_iter_cat _InputIterator>\n+\tvoid\n+\tinsert(_InputIterator __first, _InputIterator __last)\n+\t{\n+\t // FIXME: This implementation fails its complexity requirements.\n+\t // We can't idiomatically implement an efficient version (as in the\n+\t // disabled code) until ranges::inplace_merge is fixed to dispatch\n+\t // on iterator concept instead of iterator category.\n+#if 0\n+\t auto __guard = _M_make_clear_guard();\n+\t auto __n = size();\n+\t for (; __first != __last; ++__first)\n+\t {\n+\t value_type __value = *__first;\n+\t _M_cont.keys.emplace_back(std::move(__value.first));\n+\t _M_cont.values.emplace_back(std::move(__value.second));\n+\t }\n+\t auto __zv = views::zip(_M_cont.keys, _M_cont.values);\n+\t ranges::sort(__zv.begin() + __n, __zv.end(), value_comp());\n+\t ranges::inplace_merge(__zv.begin(), __zv.begin() + __n, __zv.end(), value_comp());\n+\t if constexpr (!_Multi)\n+\t _M_unique();\n+\t __guard._M_cont = nullptr;\n+#else\n+\t auto __guard = _M_make_clear_guard();\n+\t for (; __first != __last; ++__first)\n+\t {\n+\t value_type __value = *__first;\n+\t _M_cont.keys.emplace_back(std::move(__value.first));\n+\t _M_cont.values.emplace_back(std::move(__value.second));\n+\t }\n+\t _M_sort_uniq();\n+\t __guard._M_disable();\n+#endif\n+\t}\n+\n+ template<__has_input_iter_cat _InputIterator>\n+\tvoid\n+\tinsert(__sorted_t, _InputIterator __first, _InputIterator __last)\n+\t{\n+\t // FIXME: This implementation fails its complexity requirements; see above.\n+\t insert(std::move(__first), std::move(__last));\n+\t}\n+\n+ template<__detail::__container_compatible_range<value_type> _Rg>\n+\tvoid\n+\tinsert_range(_Rg&& __rg)\n+\t{ insert(ranges::begin(__rg), ranges::end(__rg)); }\n+\n+ void\n+ insert(initializer_list<value_type> __il)\n+ { insert(__il.begin(), __il.end()); }\n+\n+ void\n+ insert(__sorted_t __s, initializer_list<value_type> __il)\n+ { insert(__s, __il.begin(), __il.end()); }\n+\n+ containers\n+ extract() &&\n+ {\n+\tauto __guard = _M_make_clear_guard();\n+\treturn {std::move(_M_cont.keys), std::move(_M_cont.values)};\n+ }\n+\n+ void\n+ replace(key_container_type&& __key_cont, mapped_container_type&& __mapped_cont)\n+ {\n+\t__glibcxx_assert(__key_cont.size() == __mapped_cont.size());\n+\t_GLIBCXX_DEBUG_ASSERT(ranges::is_sorted(__key_cont, _M_comp));\n+\tauto __guard = _M_make_clear_guard();\n+\t_M_cont.keys = std::move(__key_cont);\n+\t_M_cont.values = std::move(__mapped_cont);\n+\t__guard._M_disable();\n+ }\n+\n+ // try_emplace defined directly in class flat_map only.\n+ // insert_or_assign defined directly in class flat_map only.\n+\n+ iterator\n+ erase(iterator __position)\n+ { return erase(static_cast<const_iterator>(__position)); }\n+\n+ iterator\n+ erase(const_iterator __position)\n+ {\n+\tauto __guard = _M_make_clear_guard();\n+\tauto __idx = __position._M_index;\n+\tauto __it = _M_cont.keys.erase(_M_cont.keys.begin() + __idx);\n+\t_M_cont.values.erase(_M_cont.values.begin() + __idx);\n+\t__guard._M_disable();\n+\treturn iterator{this, __it};\n+ }\n+\n+ size_type\n+ erase(const key_type& __x)\n+ { return erase<const key_type&>(__x); }\n+\n+ template<typename _Key2>\n+\trequires same_as<remove_cvref_t<_Key2>, _Key>\n+\t || (__transparent_comparator<_Compare>\n+\t && !is_convertible_v<_Key2, iterator>\n+\t && !is_convertible_v<_Key2, const_iterator>)\n+\tsize_type\n+\terase(_Key2&& __x)\n+\t{\n+\t auto [__first, __last] = equal_range(std::forward<_Key2>(__x));\n+\t auto __n = __last - __first;\n+\t erase(__first, __last);\n+\t return __n;\n+\t}\n+\n+ iterator\n+ erase(const_iterator __first, const_iterator __last)\n+ {\n+\tauto __guard = _M_make_clear_guard();\n+\tauto __it = _M_cont.keys.erase(_M_cont.keys.begin() + __first._M_index,\n+\t\t\t\t _M_cont.keys.begin() + __last._M_index);\n+\t_M_cont.values.erase(_M_cont.values.begin() + __first._M_index,\n+\t\t\t _M_cont.values.begin() + __last._M_index);\n+\t__guard._M_disable();\n+\treturn iterator{this, __it};\n+ }\n+\n+ void\n+ swap(_Derived& __y) noexcept\n+ {\n+\tranges::swap(_M_comp, __y._M_comp);\n+\tranges::swap(_M_cont.keys, __y._M_cont.keys);\n+\tranges::swap(_M_cont.values, __y._M_cont.values);\n+ }\n+\n+ void\n+ clear() noexcept\n+ {\n+\t_M_cont.keys.clear();\n+\t_M_cont.values.clear();\n+ }\n+\n+ // observers\n+ [[nodiscard]]\n+ key_compare\n+ key_comp() const\n+ { return _M_comp; }\n+\n+ [[nodiscard]]\n+ value_compare\n+ value_comp() const\n+ { return value_compare(_M_comp); }\n+\n+ [[nodiscard]]\n+ const key_container_type&\n+ keys() const noexcept\n+ { return _M_cont.keys; }\n+\n+ [[nodiscard]]\n+ const mapped_container_type&\n+ values() const noexcept\n+ { return _M_cont.values; }\n+\n+ // map operations\n+ [[nodiscard]]\n+ iterator\n+ find(const key_type& __x)\n+ { return find<key_type>(__x); }\n+\n+ [[nodiscard]]\n+ const_iterator\n+ find(const key_type& __x) const\n+ { return find<key_type>(__x); }\n+\n+ template<typename _Key2>\n+\trequires same_as<_Key2, _Key> || __transparent_comparator<_Compare>\n+\t[[nodiscard]]\n+\titerator\n+\tfind(const _Key2& __x)\n+\t{\n+\t auto __it = lower_bound(__x);\n+\t if (__it != end() && !_M_comp(__x, __it->first))\n+\t return __it;\n+\t else\n+\t return end();\n+\t}\n+\n+ template<typename _Key2>\n+\trequires same_as<_Key2, _Key> || __transparent_comparator<_Compare>\n+\t[[nodiscard]]\n+\tconst_iterator\n+\tfind(const _Key2& __x) const\n+\t{\n+\t auto __it = lower_bound(__x);\n+\t if (__it != cend() && !_M_comp(__x, __it->first))\n+\t return __it;\n+\t else\n+\t return cend();\n+\t}\n+\n+ [[nodiscard]]\n+ size_type\n+ count(const key_type& __x) const\n+ { return count<key_type>(__x); }\n+\n+ template<typename _Key2>\n+\trequires same_as<_Key2, _Key> || __transparent_comparator<_Compare>\n+\t[[nodiscard]]\n+\tsize_type\n+\tcount(const _Key2& __x) const\n+\t{\n+\t if constexpr (!_Multi)\n+\t return contains<_Key2>(__x);\n+\t else\n+\t {\n+\t auto [__first, __last] = equal_range(__x);\n+\t return __last - __first;\n+\t }\n+\t}\n+\n+ [[nodiscard]]\n+ bool\n+ contains(const key_type& __x) const\n+ { return contains<key_type>(__x); }\n+\n+ template<typename _Key2>\n+\trequires same_as<_Key2, _Key> || __transparent_comparator<_Compare>\n+\t[[nodiscard]]\n+\tbool\n+\tcontains(const _Key2& __x) const\n+\t{ return find(__x) != cend(); }\n+\n+ [[nodiscard]]\n+ iterator\n+ lower_bound(const key_type& __x)\n+ { return lower_bound<key_type>(__x); }\n+\n+ [[nodiscard]]\n+ const_iterator\n+ lower_bound(const key_type& __x) const\n+ { return lower_bound<key_type>(__x); }\n+\n+ template<typename _Key2>\n+\trequires same_as<_Key2, _Key> || __transparent_comparator<_Compare>\n+\t[[nodiscard]]\n+\titerator\n+\tlower_bound(const _Key2& __x)\n+\t{\n+\t auto __it = std::lower_bound(_M_cont.keys.begin(), _M_cont.keys.end(),\n+\t\t\t\t __x, _M_comp);\n+\t return {this, __it};\n+\t}\n+\n+ template<typename _Key2>\n+\trequires same_as<_Key2, _Key> || __transparent_comparator<_Compare>\n+\t[[nodiscard]]\n+\tconst_iterator\n+\tlower_bound(const _Key2& __x) const\n+\t{\n+\t auto __it = std::lower_bound(_M_cont.keys.begin(), _M_cont.keys.end(),\n+\t\t\t\t __x, _M_comp);\n+\t return {this, __it};\n+\t}\n+\n+ [[nodiscard]]\n+ iterator\n+ upper_bound(const key_type& __x)\n+ { return upper_bound<key_type>(__x); }\n+\n+ [[nodiscard]]\n+ const_iterator\n+ upper_bound(const key_type& __x) const\n+ { return upper_bound<key_type>(__x); }\n+\n+ template<typename _Key2>\n+\trequires same_as<_Key2, _Key> || __transparent_comparator<_Compare>\n+\t[[nodiscard]]\n+\titerator\n+\tupper_bound(const _Key2& __x)\n+\t{\n+\t auto __it = std::upper_bound(_M_cont.keys.begin(), _M_cont.keys.end(),\n+\t\t\t\t __x, _M_comp);\n+\t return {this, __it};\n+\t}\n+\n+ template<typename _Key2>\n+\trequires same_as<_Key2, _Key> || __transparent_comparator<_Compare>\n+\t[[nodiscard]]\n+\tconst_iterator\n+\tupper_bound(const _Key2& __x) const\n+\t{\n+\t auto __it = std::upper_bound(_M_cont.keys.begin(), _M_cont.keys.end(),\n+\t\t\t\t __x, _M_comp);\n+\t return {this, __it};\n+\t}\n+\n+ [[nodiscard]]\n+ pair<iterator, iterator>\n+ equal_range(const key_type& __x)\n+ { return equal_range<key_type>(__x); }\n+\n+ [[nodiscard]]\n+ pair<const_iterator, const_iterator>\n+ equal_range(const key_type& __x) const\n+ { return equal_range<key_type>(__x); }\n+\n+ template<typename _Key2>\n+\trequires same_as<_Key2, _Key> || __transparent_comparator<_Compare>\n+\t[[nodiscard]]\n+\tpair<iterator, iterator>\n+\tequal_range(const _Key2& __x)\n+\t{\n+\t auto [__first, __last] = std::equal_range(_M_cont.keys.begin(),\n+\t\t\t\t\t\t _M_cont.keys.end(),\n+\t\t\t\t\t\t __x, _M_comp);\n+\t return {{this, __first}, {this, __last}};\n+\t}\n+\n+ template<typename _Key2>\n+\trequires same_as<_Key2, _Key> || __transparent_comparator<_Compare>\n+\t[[nodiscard]]\n+\tpair<const_iterator, const_iterator>\n+\tequal_range(const _Key2& __x) const\n+\t{\n+\t auto [__first, __last] = std::equal_range(_M_cont.keys.begin(),\n+\t\t\t\t\t\t _M_cont.keys.end(),\n+\t\t\t\t\t\t __x, _M_comp);\n+\t return {{this, __first}, {this, __last}};\n+\t}\n+\n+ [[nodiscard]]\n+ friend bool\n+ operator==(const _Derived& __x, const _Derived& __y)\n+ { return std::equal(__x.begin(), __x.end(), __y.begin(), __y.end()); }\n+\n+ template<typename _Up = value_type>\n+\t[[nodiscard]]\n+\tfriend __detail::__synth3way_t<_Up>\n+\toperator<=>(const _Derived& __x, const _Derived& __y)\n+\t{\n+\t return std::lexicographical_compare_three_way(__x.begin(), __x.end(),\n+\t\t\t\t\t\t\t__y.begin(), __y.end(),\n+\t\t\t\t\t\t\t__detail::__synth3way);\n+\t}\n+\n+ friend void\n+ swap(_Derived& __x, _Derived& __y) noexcept\n+ { return __x.swap(__y); }\n+\n+ template<typename _Predicate>\n+\tfriend size_type\n+\terase_if(_Derived& __c, _Predicate __pred)\n+\t{\n+\t auto __guard = __like_t<_Derived&, _Flat_map_impl>(__c)._M_make_clear_guard();\n+\t auto __zv = views::zip(__c._M_cont.keys, __c._M_cont.values);\n+\t auto __sr = ranges::remove_if(__zv, __pred);\n+\t auto __erased = __sr.size();\n+\t __c.erase(__c.end() - __erased, __c.end());\n+\t __guard._M_disable();\n+\t return __erased;\n+\t}\n+\n+ private:\n+ containers _M_cont;\n+ [[no_unique_address]] _Compare _M_comp;\n+\n+ void\n+ _M_sort_uniq()\n+ {\n+\tauto __zv = views::zip(_M_cont.keys, _M_cont.values);\n+\tranges::sort(__zv, value_comp());\n+\tif constexpr (!_Multi)\n+\t _M_unique();\n+ }\n+\n+ void\n+ _M_unique() requires (!_Multi)\n+ {\n+\tstruct __key_equiv\n+\t{\n+\t __key_equiv(key_compare __c) : _M_comp(__c) { }\n+\n+\t bool\n+\t operator()(const_reference __x, const_reference __y) const\n+\t { return !_M_comp(__x.first, __y.first) && !_M_comp(__y.first, __x.first); }\n+\n+\t [[no_unique_address]] key_compare _M_comp;\n+\t};\n+\n+\tauto __zv = views::zip(_M_cont.keys, _M_cont.values);\n+\tauto __it = ranges::unique(__zv, __key_equiv(_M_comp)).begin();\n+\tauto __n = __it - __zv.begin();\n+\t_M_cont.keys.erase(_M_cont.keys.begin() + __n, _M_cont.keys.end());\n+\t_M_cont.values.erase(_M_cont.values.begin() + __n, _M_cont.values.end());\n+ }\n+ };\n+\n+ template<typename _Key, typename _Tp, typename _Compare,\n+\t typename _KeyContainer, typename _MappedContainer, bool _Multi>\n+ template<bool _Const>\n+ class _Flat_map_impl<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer, _Multi>::_Iterator\n+ {\n+ using __size_type = typename _Flat_map_impl::size_type;\n+\n+ public:\n+ using iterator_category = input_iterator_tag;\n+ using iterator_concept = random_access_iterator_tag;\n+ using value_type = pair<const key_type, mapped_type>;\n+ using reference = pair<const key_type&,\n+\t\t\t\t ranges::__maybe_const_t<_Const, mapped_type>&>;\n+ using difference_type = ptrdiff_t;\n+\n+ _Iterator() = default;\n+\n+ _Iterator(_Iterator<!_Const> __it) requires _Const\n+ : _M_cont(__it._M_cont), _M_index(__it._M_index)\n+ { }\n+\n+ reference\n+ operator*() const noexcept\n+ {\n+\t__glibcxx_assert(_M_index < _M_cont->keys.size());\n+\treturn {_M_cont->keys[_M_index], _M_cont->values[_M_index]};\n+ }\n+\n+ struct pointer\n+ {\n+\treference __p;\n+\n+\tconst reference*\n+\toperator->() const noexcept\n+\t{ return std::__addressof(__p); }\n+ };\n+\n+ pointer\n+ operator->() const\n+ { return pointer{operator*()}; }\n+\n+ reference\n+ operator[](difference_type __n) const noexcept\n+ { return *(*this + __n); }\n+\n+ _Iterator&\n+ operator++() noexcept\n+ {\n+\t++_M_index;\n+\treturn *this;\n+ }\n+\n+ _Iterator&\n+ operator--() noexcept\n+ {\n+\t--_M_index;\n+\treturn *this;\n+ }\n+\n+ _Iterator\n+ operator++(int) noexcept\n+ {\n+\tauto __tmp = *this;\n+\t++*this;\n+\treturn __tmp;\n+ }\n+\n+ _Iterator\n+ operator--(int) noexcept\n+ {\n+\tauto __tmp = *this;\n+\t--*this;\n+\treturn __tmp;\n+ }\n+\n+ _Iterator&\n+ operator+=(difference_type __n) noexcept\n+ {\n+\t_M_index += __n;\n+\treturn *this;\n+ }\n+\n+ _Iterator&\n+ operator-=(difference_type __n) noexcept\n+ {\n+\t_M_index -= __n;\n+\treturn *this;\n+ }\n+\n+ private:\n+ friend _Flat_map_impl;\n+ friend _Iterator<!_Const>;\n+\n+ _Iterator(_Flat_map_impl* __fm, typename key_container_type::const_iterator __it)\n+ requires (!_Const)\n+ : _M_cont(std::__addressof(__fm->_M_cont)), _M_index(__it - __fm->keys().cbegin())\n+ { }\n+\n+ _Iterator(const _Flat_map_impl* __fm, typename key_container_type::const_iterator __it)\n+ requires _Const\n+ : _M_cont(std::__addressof(__fm->_M_cont)), _M_index(__it - __fm->keys().cbegin())\n+ { }\n+\n+ friend _Iterator\n+ operator+(_Iterator __it, difference_type __n) noexcept\n+ {\n+\t__it += __n;\n+\treturn __it;\n+ }\n+\n+ friend _Iterator\n+ operator+(difference_type __n, _Iterator __it) noexcept\n+ {\n+\t__it += __n;\n+\treturn __it;\n+ }\n+\n+ friend _Iterator\n+ operator-(_Iterator __it, difference_type __n) noexcept\n+ {\n+\t__it -= __n;\n+\treturn __it;\n+ }\n+\n+ friend difference_type\n+ operator-(const _Iterator& __x, const _Iterator& __y) noexcept\n+ {\n+\t__glibcxx_assert(__x._M_cont == __y._M_cont);\n+\treturn __x._M_index - __y._M_index;\n+ }\n+\n+ friend bool\n+ operator==(const _Iterator& __x, const _Iterator& __y) noexcept\n+ {\n+\t__glibcxx_assert(__x._M_cont == __y._M_cont);\n+\t__glibcxx_assert((__x._M_index == size_t(-1)) == (__y._M_index == size_t(-1)));\n+\treturn __x._M_index == __y._M_index;\n+ }\n+\n+ friend strong_ordering\n+ operator<=>(const _Iterator& __x, const _Iterator& __y)\n+ {\n+\t__glibcxx_assert(__x._M_cont == __y._M_cont);\n+\t__glibcxx_assert((__x._M_index == size_t(-1)) == (__y._M_index == size_t(-1)));\n+\treturn __x._M_index <=> __y._M_index;\n+ }\n+\n+ ranges::__maybe_const_t<_Const, containers>* _M_cont = nullptr;\n+ __size_type _M_index = -1;\n+ };\n+\n+ /* Class template flat_map - container adaptor\n+ *\n+ * @ingroup\n+ */\n+ template<typename _Key, typename _Tp, typename _Compare = less<_Key>,\n+\t typename _KeyContainer = vector<_Key>,\n+\t typename _MappedContainer = vector<_Tp>>\n+ class flat_map\n+ : private _Flat_map_impl<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer, false>\n+ {\n+ using _Impl = _Flat_map_impl<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer, false>;\n+ friend _Impl;\n+\n+ public:\n+ // types\n+ using typename _Impl::key_type;\n+ using typename _Impl::mapped_type;\n+ using typename _Impl::value_type;\n+ using typename _Impl::key_compare;\n+ using typename _Impl::reference;\n+ using typename _Impl::const_reference;\n+ using typename _Impl::size_type;\n+ using typename _Impl::difference_type;\n+ using typename _Impl::iterator;\n+ using typename _Impl::const_iterator;\n+ using typename _Impl::reverse_iterator;\n+ using typename _Impl::const_reverse_iterator;\n+ using typename _Impl::key_container_type;\n+ using typename _Impl::mapped_container_type;\n+ using typename _Impl::value_compare;\n+ using typename _Impl::containers;\n+\n+ // constructors\n+ using _Impl::_Impl;\n+\n+ // iterators\n+ using _Impl::begin;\n+ using _Impl::end;\n+ using _Impl::rbegin;\n+ using _Impl::rend;\n+\n+ using _Impl::cbegin;\n+ using _Impl::cend;\n+ using _Impl::crbegin;\n+ using _Impl::crend;\n+\n+ // capacity\n+ using _Impl::empty;\n+ using _Impl::size;\n+ using _Impl::max_size;\n+\n+ // element access\n+ mapped_type&\n+ operator[](const key_type& __x)\n+ { return operator[]<const key_type>(__x); }\n+\n+ mapped_type&\n+ operator[](key_type&& __x)\n+ { return operator[]<key_type>(std::move(__x)); }\n+\n+ template<typename _Key2>\n+\trequires same_as<remove_cvref_t<_Key2>, _Key> || __transparent_comparator<_Compare>\n+\tmapped_type&\n+\toperator[](_Key2&& __x)\n+\t{ return try_emplace(std::forward<_Key2>(__x)).first->second; }\n+\n+ mapped_type&\n+ at(const key_type& __x)\n+ { return at<key_type>(__x); }\n+\n+ const mapped_type&\n+ at(const key_type& __x) const\n+ { return at<key_type>(__x); }\n+\n+ template<typename _Key2>\n+\trequires same_as<_Key2, _Key> || __transparent_comparator<_Compare>\n+\tmapped_type&\n+\tat(const _Key2& __x)\n+\t{\n+\t auto __it = this->find(__x);\n+\t if (__it == this->end())\n+\t __throw_out_of_range(\"flat_map::at\");\n+\t return __it->second;\n+\t}\n+\n+ template<typename _Key2>\n+\trequires same_as<_Key2, _Key> || __transparent_comparator<_Compare>\n+\tconst mapped_type&\n+\tat(const _Key2& __x) const\n+\t{\n+\t auto __it = this->find(__x);\n+\t if (__it == this->end())\n+\t __throw_out_of_range(\"flat_map::at\");\n+\t return __it->second;\n+\t}\n+\n+ // modifiers\n+ using _Impl::emplace;\n+ using _Impl::emplace_hint;\n+ using _Impl::insert;\n+ // using _Impl::insert_range;\n+ using _Impl::extract;\n+ using _Impl::replace;\n+ using _Impl::erase;\n+ using _Impl::swap;\n+ using _Impl::clear;\n+\n+ template<typename... _Args>\n+\trequires is_constructible_v<mapped_type, _Args...>\n+\tpair<iterator, bool>\n+\ttry_emplace(const key_type& __k, _Args&&... __args)\n+\t{ return _Impl::_M_try_emplace(nullopt, __k, std::forward<_Args>(__args)...); }\n+\n+ template<typename... _Args>\n+\trequires is_constructible_v<mapped_type, _Args...>\n+\tpair<iterator, bool>\n+\ttry_emplace(key_type&& __k, _Args&&... __args)\n+\t{\n+\t return _Impl::_M_try_emplace(nullopt, std::move(__k),\n+\t\t\t\t std::forward<_Args>(__args)...);\n+\t}\n+\n+ template<typename _Key2, typename... _Args>\n+\trequires __transparent_comparator<_Compare>\n+\t && is_constructible_v<key_type, _Key2>\n+\t && is_constructible_v<mapped_type, _Args...>\n+\t && (!is_convertible_v<_Key2&&, const_iterator>)\n+\t && (!is_convertible_v<_Key2&&, iterator>)\n+\tpair<iterator, bool>\n+\ttry_emplace(_Key2&& __k, _Args&&... __args)\n+\t{\n+\t return _Impl::_M_try_emplace(nullopt, std::forward<_Key2>(__k),\n+\t\t\t\t std::forward<_Args>(__args)...);\n+\t}\n+\n+ template<typename... _Args>\n+\trequires is_constructible_v<mapped_type, _Args...>\n+\titerator\n+\ttry_emplace(const_iterator __hint, const key_type& __k, _Args&&... __args)\n+\t{ return _Impl::_M_try_emplace(__hint, __k, std::forward<_Args>(__args)...).first; }\n+\n+ template<typename... _Args>\n+\trequires is_constructible_v<mapped_type, _Args...>\n+\titerator\n+\ttry_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)\n+\t{\n+\t return _Impl::_M_try_emplace(__hint, std::move(__k),\n+\t\t\t\t std::forward<_Args>(__args)...).first;\n+\t}\n+\n+ template<typename _Key2, typename... _Args>\n+\trequires __transparent_comparator<_Compare>\n+\t && is_constructible_v<key_type, _Key2>\n+\t && is_constructible_v<mapped_type, _Args...>\n+\titerator\n+\ttry_emplace(const_iterator __hint, _Key2&& __k, _Args&&... __args)\n+\t{\n+\t return _Impl::_M_try_emplace(__hint, std::forward<_Key2>(__k),\n+\t\t\t\t std::forward<_Args>(__args)...).first;\n+\t}\n+\n+ template<typename _Mapped>\n+\trequires is_assignable_v<mapped_type&, _Mapped>\n+\t && is_constructible_v<mapped_type, _Mapped>\n+\tpair<iterator, bool>\n+\tinsert_or_assign(const key_type& __k, _Mapped&& __obj)\n+\t{ return insert_or_assign<const key_type&, _Mapped>(__k, std::forward<_Mapped>(__obj)); }\n+\n+ template<typename _Mapped>\n+\trequires is_assignable_v<mapped_type&, _Mapped>\n+\t && is_constructible_v<mapped_type, _Mapped>\n+\tpair<iterator, bool>\n+\tinsert_or_assign(key_type&& __k, _Mapped&& __obj)\n+\t{\n+\t return insert_or_assign<key_type, _Mapped>(std::move(__k),\n+\t\t\t\t\t\t std::forward<_Mapped>(__obj));\n+\t}\n+\n+ template<typename _Key2, typename _Mapped>\n+\trequires (same_as<remove_cvref_t<_Key2>, _Key> || __transparent_comparator<_Compare>)\n+\t && is_constructible_v<key_type, _Key2>\n+\t && is_assignable_v<mapped_type&, _Mapped>\n+\t && is_constructible_v<mapped_type, _Mapped>\n+\tpair<iterator, bool>\n+\tinsert_or_assign(_Key2&& __k, _Mapped&& __obj)\n+\t{\n+\t auto __r = _Impl::_M_try_emplace(nullopt, std::forward<_Key2>(__k),\n+\t\t\t\t\t std::forward<_Mapped>(__obj));\n+\t if (!__r.second)\n+\t __r.first->second = std::forward<_Mapped>(__obj);\n+\t return __r;\n+\t}\n+\n+ template<typename _Mapped>\n+\trequires is_assignable_v<mapped_type&, _Mapped>\n+\t && is_constructible_v<mapped_type, _Mapped>\n+\titerator\n+\tinsert_or_assign(const_iterator __hint, const key_type& __k, _Mapped&& __obj)\n+\t{\n+\t return insert_or_assign<const key_type&, _Mapped>(__hint, __k,\n+\t\t\t\t\t\t\t std::forward<_Mapped>(__obj));\n+\t}\n+\n+ template<typename _Mapped>\n+\trequires is_assignable_v<mapped_type&, _Mapped>\n+\t && is_constructible_v<mapped_type, _Mapped>\n+\titerator\n+\tinsert_or_assign(const_iterator __hint, key_type&& __k, _Mapped&& __obj)\n+\t{\n+\t return insert_or_assign<key_type, _Mapped>(__hint, std::move(__k),\n+\t\t\t\t\t\t std::forward<_Mapped>(__obj));\n+\t}\n+\n+ template<typename _Key2, typename _Mapped>\n+\trequires (same_as<remove_cvref_t<_Key2>, _Key> || __transparent_comparator<_Compare>)\n+\t && is_constructible_v<key_type, _Key2>\n+\t && is_assignable_v<mapped_type&, _Mapped>\n+\t && is_constructible_v<mapped_type, _Mapped>\n+\titerator\n+\tinsert_or_assign(const_iterator __hint, _Key2&& __k, _Mapped&& __obj)\n+\t{\n+\t auto __r = _Impl::_M_try_emplace(__hint, std::forward<_Key2>(__k),\n+\t\t\t\t\t std::forward<_Mapped>(__obj));\n+\t if (!__r.second)\n+\t __r.first->second = std::forward<_Mapped>(__obj);\n+\t return __r.first;\n+\t}\n+\n+ // observers\n+ using _Impl::key_comp;\n+ using _Impl::value_comp;\n+ using _Impl::keys;\n+ using _Impl::values;\n+\n+ // map operations\n+ using _Impl::find;\n+ using _Impl::count;\n+ using _Impl::contains;\n+ using _Impl::lower_bound;\n+ using _Impl::upper_bound;\n+ using _Impl::equal_range;\n+ };\n+\n+ template<typename _KeyContainer, typename _MappedContainer,\n+\t __not_allocator_like _Compare = less<typename _KeyContainer::value_type>>\n+ flat_map(_KeyContainer, _MappedContainer, _Compare = _Compare())\n+ -> flat_map<typename _KeyContainer::value_type, typename _MappedContainer::value_type,\n+\t\t_Compare, _KeyContainer, _MappedContainer>;\n+\n+ template<typename _KeyContainer, typename _MappedContainer,\n+\t __allocator_for<_KeyContainer, _MappedContainer> _Alloc>\n+ flat_map(_KeyContainer, _MappedContainer, _Alloc)\n+ -> flat_map<typename _KeyContainer::value_type, typename _MappedContainer::value_type,\n+\t\tless<typename _KeyContainer::value_type>, _KeyContainer, _MappedContainer>;\n+\n+ template<typename _KeyContainer, typename _MappedContainer, __not_allocator_like _Compare,\n+\t __allocator_for<_KeyContainer, _MappedContainer> _Alloc>\n+ flat_map(_KeyContainer, _MappedContainer, _Compare, _Alloc)\n+ -> flat_map<typename _KeyContainer::value_type, typename _MappedContainer::value_type,\n+\t\t_Compare, _KeyContainer, _MappedContainer>;\n+\n+ template<typename _KeyContainer, typename _MappedContainer,\n+\t __not_allocator_like _Compare = less<typename _KeyContainer::value_type>>\n+ flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Compare = _Compare())\n+ -> flat_map<typename _KeyContainer::value_type, typename _MappedContainer::value_type,\n+\t\t_Compare, _KeyContainer, _MappedContainer>;\n+\n+ template<typename _KeyContainer, typename _MappedContainer,\n+\t __allocator_for<_KeyContainer, _MappedContainer> _Alloc>\n+ flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Alloc)\n+ -> flat_map<typename _KeyContainer::value_type, typename _MappedContainer::value_type,\n+\t\tless<typename _KeyContainer::value_type>, _KeyContainer, _MappedContainer>;\n+\n+ template<typename _KeyContainer, typename _MappedContainer, __not_allocator_like _Compare,\n+\t __allocator_for<_KeyContainer, _MappedContainer> _Alloc>\n+ flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Compare, _Alloc)\n+ -> flat_map<typename _KeyContainer::value_type, typename _MappedContainer::value_type,\n+\t\t_Compare, _KeyContainer, _MappedContainer>;\n+\n+ template<__has_input_iter_cat _InputIterator,\n+\t __not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>>\n+ flat_map(_InputIterator, _InputIterator, _Compare = _Compare())\n+ -> flat_map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>;\n+\n+ template<__has_input_iter_cat _InputIterator,\n+\t __not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>>\n+ flat_map(sorted_unique_t, _InputIterator, _InputIterator, _Compare = _Compare())\n+ -> flat_map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>;\n+\n+ template<ranges::input_range _Rg,\n+\t __not_allocator_like _Compare = less<__detail::__range_key_type<_Rg>>,\n+\t __allocator_like _Alloc = allocator<byte>>\n+ flat_map(from_range_t, _Rg&&, _Compare = _Compare(), _Alloc = _Alloc())\n+ -> flat_map<__detail::__range_key_type<_Rg>, __detail::__range_mapped_type<_Rg>,\n+\t\t_Compare,\n+\t\tvector<__detail::__range_key_type<_Rg>,\n+\t\t __alloc_rebind<_Alloc, __detail::__range_key_type<_Rg>>>,\n+\t\tvector<__detail::__range_mapped_type<_Rg>,\n+\t\t __alloc_rebind<_Alloc, __detail::__range_mapped_type<_Rg>>>>;\n+\n+ template<ranges::input_range _Rg, __allocator_like _Alloc>\n+ flat_map(from_range_t, _Rg&&, _Alloc)\n+ -> flat_map<__detail::__range_key_type<_Rg>, __detail::__range_mapped_type<_Rg>,\n+\t\tless<__detail::__range_key_type<_Rg>>,\n+\t\tvector<__detail::__range_key_type<_Rg>,\n+\t\t __alloc_rebind<_Alloc, __detail::__range_key_type<_Rg>>>,\n+\t\tvector<__detail::__range_mapped_type<_Rg>,\n+\t\t __alloc_rebind<_Alloc, __detail::__range_mapped_type<_Rg>>>>;\n+\n+ template<typename _Key, typename _Tp, __not_allocator_like _Compare = less<_Key>>\n+ flat_map(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare())\n+ -> flat_map<_Key, _Tp, _Compare>;\n+\n+ template<typename _Key, typename _Tp, __not_allocator_like _Compare = less<_Key>>\n+ flat_map(sorted_unique_t, initializer_list<pair<_Key, _Tp>>, _Compare = _Compare())\n+ -> flat_map<_Key, _Tp, _Compare>;\n+\n+ template<typename _Key, typename _Tp, typename _Compare,\n+\t typename _KeyContainer, typename _MappedContainer, typename _Alloc>\n+ struct uses_allocator<flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>, _Alloc>\n+ : bool_constant<uses_allocator_v<_KeyContainer, _Alloc>\n+\t\t && uses_allocator_v<_MappedContainer, _Alloc>>\n+ { };\n+\n+ /* Class template flat_multimap - container adaptor\n+ *\n+ * @ingroup\n+ */\n+ template<typename _Key, typename _Tp, typename _Compare = less<_Key>,\n+\t typename _KeyContainer = vector<_Key>,\n+\t typename _MappedContainer = vector<_Tp>>\n+ class flat_multimap\n+ : private _Flat_map_impl<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer, true>\n+ {\n+ using _Impl = _Flat_map_impl<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer, true>;\n+ friend _Impl;\n+\n+ public:\n+ // types\n+ using typename _Impl::key_type;\n+ using typename _Impl::mapped_type;\n+ using typename _Impl::value_type;\n+ using typename _Impl::key_compare;\n+ using typename _Impl::reference;\n+ using typename _Impl::const_reference;\n+ using typename _Impl::size_type;\n+ using typename _Impl::difference_type;\n+ using typename _Impl::iterator;\n+ using typename _Impl::const_iterator;\n+ using typename _Impl::reverse_iterator;\n+ using typename _Impl::const_reverse_iterator;\n+ using typename _Impl::key_container_type;\n+ using typename _Impl::mapped_container_type;\n+ using typename _Impl::value_compare;\n+ using typename _Impl::containers;\n+\n+ // constructors\n+ using _Impl::_Impl;\n+\n+ // iterators\n+ using _Impl::begin;\n+ using _Impl::end;\n+ using _Impl::rbegin;\n+ using _Impl::rend;\n+\n+ using _Impl::cbegin;\n+ using _Impl::cend;\n+ using _Impl::crbegin;\n+ using _Impl::crend;\n+\n+ // capacity\n+ using _Impl::empty;\n+ using _Impl::size;\n+ using _Impl::max_size;\n+\n+ // modifiers\n+ using _Impl::emplace;\n+ using _Impl::emplace_hint;\n+ using _Impl::insert;\n+ // using _Impl::insert_range;\n+ using _Impl::extract;\n+ using _Impl::replace;\n+ using _Impl::erase;\n+ using _Impl::swap;\n+ using _Impl::clear;\n+\n+ // observers\n+ using _Impl::key_comp;\n+ using _Impl::value_comp;\n+ using _Impl::keys;\n+ using _Impl::values;\n+\n+ // map operations\n+ using _Impl::find;\n+ using _Impl::count;\n+ using _Impl::contains;\n+ using _Impl::lower_bound;\n+ using _Impl::upper_bound;\n+ using _Impl::equal_range;\n+ };\n+\n+ template<typename _KeyContainer, typename _MappedContainer,\n+\t __not_allocator_like _Compare = less<typename _KeyContainer::value_type>>\n+ flat_multimap(_KeyContainer, _MappedContainer, _Compare = _Compare())\n+ -> flat_multimap<typename _KeyContainer::value_type, typename _MappedContainer::value_type,\n+\t\t _Compare, _KeyContainer, _MappedContainer>;\n+\n+ template<typename _KeyContainer, typename _MappedContainer,\n+\t __allocator_for<_KeyContainer, _MappedContainer> _Alloc>\n+ flat_multimap(_KeyContainer, _MappedContainer, _Alloc)\n+ -> flat_multimap<typename _KeyContainer::value_type, typename _MappedContainer::value_type,\n+\t\t less<typename _KeyContainer::value_type>, _KeyContainer, _MappedContainer>;\n+\n+ template<typename _KeyContainer, typename _MappedContainer, __not_allocator_like _Compare,\n+\t __allocator_for<_KeyContainer, _MappedContainer> _Alloc>\n+ flat_multimap(_KeyContainer, _MappedContainer, _Compare, _Alloc)\n+ -> flat_multimap<typename _KeyContainer::value_type, typename _MappedContainer::value_type,\n+\t\t _Compare, _KeyContainer, _MappedContainer>;\n+\n+ template<typename _KeyContainer, typename _MappedContainer,\n+\t __not_allocator_like _Compare = less<typename _KeyContainer::value_type>>\n+ flat_multimap(sorted_equivalent_t, _KeyContainer, _MappedContainer, _Compare = _Compare())\n+ -> flat_multimap<typename _KeyContainer::value_type, typename _MappedContainer::value_type,\n+\t\t _Compare, _KeyContainer, _MappedContainer>;\n+\n+ template<typename _KeyContainer, typename _MappedContainer,\n+\t __allocator_for<_KeyContainer, _MappedContainer> _Alloc>\n+ flat_multimap(sorted_equivalent_t, _KeyContainer, _MappedContainer, _Alloc)\n+ -> flat_multimap<typename _KeyContainer::value_type, typename _MappedContainer::value_type,\n+\t\t less<typename _KeyContainer::value_type>, _KeyContainer, _MappedContainer>;\n+\n+ template<typename _KeyContainer, typename _MappedContainer, __not_allocator_like _Compare,\n+\t __allocator_for<_KeyContainer, _MappedContainer> _Alloc>\n+ flat_multimap(sorted_equivalent_t, _KeyContainer, _MappedContainer, _Compare, _Alloc)\n+ -> flat_multimap<typename _KeyContainer::value_type, typename _MappedContainer::value_type,\n+\t\t _Compare, _KeyContainer, _MappedContainer>;\n+\n+ template<__has_input_iter_cat _InputIterator,\n+\t __not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>>\n+ flat_multimap(_InputIterator, _InputIterator, _Compare = _Compare())\n+ -> flat_multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>;\n+\n+ template<__has_input_iter_cat _InputIterator,\n+\t __not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>>\n+ flat_multimap(sorted_equivalent_t, _InputIterator, _InputIterator, _Compare = _Compare())\n+ -> flat_multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>;\n+\n+ template<ranges::input_range _Rg,\n+\t __not_allocator_like _Compare = less<__detail::__range_key_type<_Rg>>,\n+\t __allocator_like _Alloc = allocator<byte>>\n+ flat_multimap(from_range_t, _Rg&&, _Compare = _Compare(), _Alloc = _Alloc())\n+ -> flat_multimap<__detail::__range_key_type<_Rg>, __detail::__range_mapped_type<_Rg>,\n+\t\t _Compare,\n+\t\t vector<__detail::__range_key_type<_Rg>,\n+\t\t\t __alloc_rebind<_Alloc, __detail::__range_key_type<_Rg>>>,\n+\t\t vector<__detail::__range_mapped_type<_Rg>,\n+\t\t\t __alloc_rebind<_Alloc, __detail::__range_mapped_type<_Rg>>>>;\n+\n+ template<ranges::input_range _Rg, __allocator_like _Alloc>\n+ flat_multimap(from_range_t, _Rg&&, _Alloc)\n+ -> flat_multimap<__detail::__range_key_type<_Rg>, __detail::__range_mapped_type<_Rg>,\n+\t\t less<__detail::__range_key_type<_Rg>>,\n+\t\t vector<__detail::__range_key_type<_Rg>,\n+\t\t\t __alloc_rebind<_Alloc, __detail::__range_key_type<_Rg>>>,\n+\t\t vector<__detail::__range_mapped_type<_Rg>,\n+\t\t\t __alloc_rebind<_Alloc, __detail::__range_mapped_type<_Rg>>>>;\n+\n+ template<typename _Key, typename _Tp, __not_allocator_like _Compare = less<_Key>>\n+ flat_multimap(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare())\n+ -> flat_multimap<_Key, _Tp, _Compare>;\n+\n+ template<typename _Key, typename _Tp, __not_allocator_like _Compare = less<_Key>>\n+ flat_multimap(sorted_equivalent_t, initializer_list<pair<_Key, _Tp>>, _Compare = _Compare())\n+ -> flat_multimap<_Key, _Tp, _Compare>;\n+\n+ template<typename _Key, typename _Tp, typename _Compare,\n+\t typename _KeyContainer, typename _MappedContainer, typename _Alloc>\n+ struct uses_allocator<flat_multimap<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>,\n+\t\t\t _Alloc>\n+ : bool_constant<uses_allocator_v<_KeyContainer, _Alloc>\n+\t\t && uses_allocator_v<_MappedContainer, _Alloc>>\n+ { };\n+\n+_GLIBCXX_END_NAMESPACE_VERSION\n+} // namespace std\n+#endif // __cpp_lib_flat_map\n+#endif // _GLIBCXX_FLAT_MAP\ndiff --git a/libstdc++-v3/src/c++23/std.cc.in b/libstdc++-v3/src/c++23/std.cc.in\nindex 7a0ff8edad6e..0225badeaacc 100644\n--- a/libstdc++-v3/src/c++23/std.cc.in\n+++ b/libstdc++-v3/src/c++23/std.cc.in\n@@ -1263,6 +1263,16 @@ export namespace std::filesystem\n #endif // __cpp_lib_filesystem\n \n // <flat_map>\n+#if __cpp_lib_flat_map\n+export namespace std\n+{\n+ using std::flat_map;\n+ using std::sorted_equivalent;\n+ using std::sorted_equivalent_t;\n+ using std::sorted_unique;\n+ using std::sorted_unique_t;\n+}\n+#endif\n \n // <flat_set>\n \ndiff --git a/libstdc++-v3/testsuite/23_containers/flat_map/1.cc b/libstdc++-v3/testsuite/23_containers/flat_map/1.cc\nnew file mode 100644\nindex 000000000000..494c96159367\n--- /dev/null\n+++ b/libstdc++-v3/testsuite/23_containers/flat_map/1.cc\n@@ -0,0 +1,166 @@\n+// { dg-do run { target c++23 } }\n+\n+#include <flat_map>\n+\n+#if __cpp_lib_flat_map != 202207L\n+# error \"Feature-test macro __cpp_lib_flat_map has wrong value in <flat_map>\"\n+#endif\n+\n+#include <deque>\n+#include <vector>\n+#include <testsuite_allocator.h>\n+#include <testsuite_hooks.h>\n+\n+template<template<typename> class KeyContainer, template<typename> class MappedContainer>\n+void\n+test01()\n+{\n+ std::flat_map<int, int, std::less<int>, KeyContainer<int>, MappedContainer<int>> m;\n+ static_assert( std::ranges::random_access_range<decltype(m)> );\n+\n+ m.insert({1,-1});\n+ m.insert({2,-2});\n+ m.insert({3,-3});\n+ m.insert({1,-4});\n+ m.insert({2,-5});\n+ m.insert({3,-6});\n+ m.insert({0, 0});\n+ VERIFY( m.size() == 4 );\n+ VERIFY( std::ranges::equal(m.keys(), (int[]){0, 1, 2, 3}) );\n+ VERIFY( std::ranges::equal(m.values(), (int[]){0, -1, -2, -3}) );\n+\n+ for (int i = 0; i < 4; i++)\n+ {\n+ m.clear();\n+\n+ int j = i;\n+ m.insert(m.end(), {j,-j});\n+ j = (j + 1) % 4;\n+ m.insert(m.end(), {j,-j});\n+ j = (j + 1) % 4;\n+ m.insert(m.end(), {j,-j});\n+ j = (j + 1) % 4;\n+ m.insert(m.end(), {j,-j});\n+\n+ m.insert(m.begin() + i, {1,-4});\n+ m.insert(m.begin() + i, {2,-5});\n+ m.insert(m.begin() + i, {3,-6});\n+ m.insert(m.begin() + i, {0,-7});\n+ VERIFY( std::ranges::equal(m.keys(), (int[]){0, 1, 2, 3}) );\n+ VERIFY( std::ranges::equal(m.values(), (int[]){0, -1, -2, -3}) );\n+ }\n+\n+ m.clear();\n+ m = {{10,0},{10,1}};\n+ VERIFY( m.size() == 1 );\n+ m.insert({{11,2},{12,3},{11,4}});\n+ VERIFY( m.size() == 3 );\n+ VERIFY( m[10] == 0 );\n+ VERIFY( m[11] == 2 );\n+ VERIFY( m[12] == 3 );\n+ m[20] = 42;\n+ VERIFY( m[20] == 42 );\n+ VERIFY( m.end()[-1] == std::pair(20,42) );\n+}\n+\n+void\n+test02()\n+{\n+ std::flat_map<int, int, std::greater<int>> m;\n+ static_assert( std::ranges::random_access_range<decltype(m)> );\n+\n+ auto r = m.insert({1,-1});\n+ VERIFY( r.first->first == 1 && r.first->second == -1 && r.second );\n+ r = m.insert({2,-2});\n+ VERIFY( r.first->first == 2 && r.first->second == -2 && r.second );\n+ r = m.insert({3,-3});\n+ VERIFY( r.first->first == 3 && r.first->second == -3 && r.second );\n+ r = m.insert({1,-4});\n+ VERIFY( r.first->first == 1 && r.first->second == -1 && !r.second );\n+ r = m.insert({2,-5});\n+ VERIFY( r.first->first == 2 && r.first->second == -2 && !r.second );\n+ r = m.insert({3,-6});\n+ VERIFY( r.first->first == 3 && r.first->second == -3 && !r.second );\n+ r = m.insert_or_assign(0, 0);\n+ VERIFY( r.first->first == 0 && r.first->second == 0 && r.second );\n+ r = m.insert_or_assign(0, 1);\n+ VERIFY( r.first->first == 0 && r.first->second == 1 && !r.second );\n+ VERIFY( *m.insert_or_assign(m.end(), 0, 2) == std::pair(0, 2) );\n+ VERIFY( m.size() == 4 );\n+ VERIFY( std::ranges::equal(m.keys(), (int[]){3, 2, 1, 0}) );\n+ VERIFY( std::ranges::equal(m.values(), (int[]){-3, -2, -1, 2}) );\n+\n+ VERIFY( m.contains(3) && !m.contains(7) );\n+ VERIFY( m.count(3) == 1 );\n+}\n+\n+void\n+test03()\n+{\n+ std::flat_map<int, int> m;\n+ m = {std::pair(1, 2), {3, 4}, {5, 6}};\n+ m.insert({std::pair(7, 8), {9, 10}});\n+\n+ auto it = m.find(0);\n+ VERIFY( it == m.end() );\n+ it = m.find(9);\n+ VERIFY( it->second == 10 );\n+\n+ const auto n = m;\n+ VERIFY( m == m );\n+ VERIFY( m == n );\n+\n+ m.erase(m.begin());\n+ m.erase(5);\n+ m.erase(m.end()-2, m.end());\n+ VERIFY( std::ranges::equal(m, (std::pair<int, int>[]){{3, 4}}) );\n+ VERIFY( m != n );\n+ VERIFY( n < m );\n+\n+ m = n;\n+ erase_if(m, [](const auto& x) { auto [k, v] = x; return k < 5 || k > 5; });\n+ VERIFY( std::ranges::equal(m, (std::pair<int, int>[]){{5, 6}}) );\n+}\n+\n+void\n+test04()\n+{\n+ using vector = std::vector<int, __gnu_test::uneq_allocator<int>>;\n+ vector v1 = {1, 2, 3};\n+ vector v2 = {4, 5, 6};\n+ __gnu_test::uneq_allocator<int> alloc(42);\n+\n+ using flat_map = std::flat_map<int, int, std::less<int>, vector, vector>;\n+ flat_map m1(alloc);\n+ VERIFY( m1.keys().get_allocator().get_personality() == 42 );\n+ VERIFY( m1.values().get_allocator().get_personality() == 42 );\n+\n+ flat_map m2(v1, v2, alloc);\n+ VERIFY( m2.keys().get_allocator().get_personality() == 42 );\n+ VERIFY( m2.values().get_allocator().get_personality() == 42 );\n+\n+ flat_map m3(std::sorted_unique_t{}, v1, v2, alloc);\n+ VERIFY( m2.keys().get_allocator().get_personality() == 42 );\n+ VERIFY( m2.values().get_allocator().get_personality() == 42 );\n+\n+ alloc = __gnu_test::uneq_allocator<int>(43);\n+ flat_map m4(m3, alloc);\n+ VERIFY( m4.keys().get_allocator().get_personality() == 43 );\n+ VERIFY( m4.values().get_allocator().get_personality() == 43 );\n+\n+ alloc = __gnu_test::uneq_allocator<int>(44);\n+ flat_map m5(std::move(m4), alloc);\n+ VERIFY( m5.keys().get_allocator().get_personality() == 44 );\n+ VERIFY( m5.values().get_allocator().get_personality() == 44 );\n+}\n+\n+int\n+main()\n+{\n+ test01<std::vector, std::vector>();\n+ test01<std::deque, std::deque>();\n+ test01<std::vector, std::deque>();\n+ test02();\n+ test03();\n+ test04();\n+}\ndiff --git a/libstdc++-v3/testsuite/23_containers/flat_multimap/1.cc b/libstdc++-v3/testsuite/23_containers/flat_multimap/1.cc\nnew file mode 100644\nindex 000000000000..f82402754777\n--- /dev/null\n+++ b/libstdc++-v3/testsuite/23_containers/flat_multimap/1.cc\n@@ -0,0 +1,141 @@\n+// { dg-do run { target c++23 } }\n+\n+#include <flat_map>\n+#include <deque>\n+#include <vector>\n+#include <testsuite_allocator.h>\n+#include <testsuite_hooks.h>\n+\n+template<template<class> class Sequence>\n+void\n+test01()\n+{\n+ std::flat_multimap<int, int, std::less<int>, Sequence<int>, Sequence<int>> m;\n+ static_assert( std::ranges::random_access_range<decltype(m)> );\n+\n+ m.insert({1,-1});\n+ m.insert({2,-2});\n+ m.insert({3,-3});\n+ m.insert({1,-4});\n+ m.insert({2,-5});\n+ m.insert({3,-6});\n+ m.insert({0, 0});\n+ VERIFY( m.size() == 7 );\n+ VERIFY( std::ranges::equal(m.keys(), (int[]){0, 1, 1, 2, 2, 3, 3}) );\n+ VERIFY( std::ranges::equal(m.values(), (int[]){0, -1, -4, -2, -5, -3, -6}) );\n+\n+ m.clear();\n+ m.insert(m.begin(), {0, 0});\n+ m.insert(m.begin(), {1,-1});\n+ m.insert(m.begin(), {2,-2});\n+ m.insert(m.begin(), {3,-3});\n+ m.insert(m.begin(), {1,-4});\n+ m.insert(m.begin(), {2,-5});\n+ m.insert(m.begin(), {3,-6});\n+ m.insert(m.begin(), {0,-7});\n+ VERIFY( std::ranges::equal(m.keys(), (int[]){0, 0, 1, 1, 2, 2, 3, 3}) );\n+ VERIFY( std::ranges::equal(m.values(), (int[]){-7, 0, -4, -1, -5, -2, -6, -3}) );\n+\n+ m.clear();\n+ m = {{10,0},{10,1}};\n+ VERIFY( m.size() == 2 );\n+ m.insert({{11,2},{12,3},{11,4}});\n+ VERIFY( m.size() == 5 );\n+ VERIFY( m.end()[-1] == std::pair(12,3) );\n+}\n+\n+void\n+test02()\n+{\n+ std::flat_multimap<int, int, std::greater<int>> m;\n+ static_assert( std::ranges::random_access_range<decltype(m)> );\n+\n+ auto r = m.insert({1,-1});\n+ VERIFY( r->first == 1 && r->second == -1 );\n+ r = m.insert({2,-2});\n+ VERIFY( r->first == 2 && r->second == -2 );\n+ r = m.insert({3,-3});\n+ VERIFY( r->first == 3 && r->second == -3 );\n+ r = m.insert({1,-4});\n+ VERIFY( r->first == 1 && r->second == -4 );\n+ r = m.insert({2,-5});\n+ VERIFY( r->first == 2 && r->second == -5 );\n+ r = m.insert({3,-6});\n+ VERIFY( r->first == 3 && r->second == -6 );\n+ VERIFY( m.size() == 6 );\n+ VERIFY( std::ranges::equal(m.keys(), (int[]){3, 3, 2, 2, 1, 1}) );\n+ VERIFY( std::ranges::equal(m.values(), (int[]){-3, -6, -2, -5, -1, -4}) );\n+\n+ VERIFY( m.contains(3) && !m.contains(7) );\n+ VERIFY( m.count(3) == 2 );\n+}\n+\n+void\n+test03()\n+{\n+ std::flat_multimap<int, int> m;\n+ m = {std::pair(1, 2), {3, 4}, {5, 6}};\n+ m.insert({std::pair(7, 8), {9, 10}});\n+\n+ auto it = m.find(0);\n+ VERIFY( it == m.end() );\n+ it = m.find(9);\n+ VERIFY( it->second == 10 );\n+\n+ const auto n = m;\n+ VERIFY( m == m );\n+ VERIFY( m == n );\n+\n+ m.erase(m.begin());\n+ m.erase(5);\n+ m.erase(m.end()-2, m.end());\n+ VERIFY( std::ranges::equal(m, (std::pair<int, int>[]){{3, 4}}) );\n+ VERIFY( m != n );\n+ VERIFY( n < m );\n+\n+ m = n;\n+ erase_if(m, [](const auto& x) { auto [k, v] = x; return k < 5 || k > 5; });\n+ VERIFY( std::ranges::equal(m, (std::pair<int, int>[]){{5, 6}}) );\n+}\n+\n+void\n+test04()\n+{\n+ using vector = std::vector<int, __gnu_test::uneq_allocator<int>>;\n+ vector v1 = {1, 2, 3};\n+ vector v2 = {4, 5, 6};\n+ __gnu_test::uneq_allocator<int> alloc(42);\n+\n+ using flat_multimap = std::flat_multimap<int, int, std::less<int>, vector, vector>;\n+ flat_multimap m1(alloc);\n+ VERIFY( m1.keys().get_allocator().get_personality() == 42 );\n+ VERIFY( m1.values().get_allocator().get_personality() == 42 );\n+\n+ flat_multimap m2(v1, v2, alloc);\n+ VERIFY( m2.keys().get_allocator().get_personality() == 42 );\n+ VERIFY( m2.values().get_allocator().get_personality() == 42 );\n+\n+ flat_multimap m3(std::sorted_equivalent_t{}, v1, v2, alloc);\n+ VERIFY( m2.keys().get_allocator().get_personality() == 42 );\n+ VERIFY( m2.values().get_allocator().get_personality() == 42 );\n+\n+ alloc = __gnu_test::uneq_allocator<int>(43);\n+ flat_multimap m4(m2, alloc);\n+ VERIFY( m4.keys().get_allocator().get_personality() == 43 );\n+ VERIFY( m4.values().get_allocator().get_personality() == 43 );\n+\n+ alloc = __gnu_test::uneq_allocator<int>(44);\n+ flat_multimap m5(std::move(m4), alloc);\n+ VERIFY( m5.keys().get_allocator().get_personality() == 44 );\n+ VERIFY( m5.values().get_allocator().get_personality() == 44 );\n+}\n+\n+int\n+main()\n+{\n+ test01<std::vector>();\n+ test01<std::deque>();\n+ test02();\n+ test03();\n+ test04();\n+}\n", "prefixes": [ "v1", "2/3" ] }