On Fri, 25 Oct 2024, Patrick Palka wrote:
> On Wed, 16 Oct 2024, Patrick Palka wrote:
>
> > On Mon, 30 Sep 2024, Patrick Palka wrote:
> >
> > > 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.
> >
> > Here's v2 which adds somewhat more tests and uses the std:: algos
> > instead of ranges:: algos where possible, along with some other
> > very minor cleanups.
>
> Now also available in PR form at:
> https://forge.sourceware.org/gcc/gcc-TEST/pulls/9
Series pushed to trunk as r15-{6370,6371,6372}.
>
> >
> > -- >8 --
> >
> > libstdc++-v3/ChangeLog:
> >
> > * include/Makefile.am: Add new header <flat_map>.
> > * 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 | 1475 +++++++++++++++++
> > .../testsuite/23_containers/flat_map/1.cc | 123 ++
> > .../23_containers/flat_multimap/1.cc | 106 ++
> > 9 files changed, 1738 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<typename _Func, typename _SfinaeType>
> > using __has_is_transparent_t
> > = typename __has_is_transparent<_Func, _SfinaeType>::type;
> > +
> > +#if __cpp_concepts
> > + template<typename _Func>
> > + 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 4fa820a5a4a..6f1958ac705 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 fdbee8161d9..ecead3edb26 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..ff653e949db
> > --- /dev/null
> > +++ b/libstdc++-v3/include/std/flat_map
> > @@ -0,0 +1,1475 @@
> > +// <flat_map> -*- 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
> > +// <http://www.gnu.org/licenses/>.
> > +
> > +/** @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 <bits/version.h>
> > +
> > +#ifdef __cpp_lib_flat_map // >= C++23
> > +
> > +#include <compare>
> > +#include <initializer_list>
> > +
> > +#include <algorithm>
> > +#include <exception>
> > +#include <functional>
> > +#include <optional>
> > +#include <ranges>
> > +#include <type_traits>
> > +#include <vector>
> > +#include <bits/functexcept.h>
> > +#include <bits/stl_function.h> // std::less
> > +#include <bits/stl_pair.h>
> > +
> > +namespace std _GLIBCXX_VISIBILITY(default)
> > +{
> > +_GLIBCXX_BEGIN_NAMESPACE_VERSION
> > +
> > + template<typename _Key, typename _Tp, typename _Compare,
> > + typename _KeyContainer, typename _MappedContainer>
> > + class flat_map;
> > +
> > + template<typename _Key, typename _Tp, typename _Compare,
> > + typename _KeyContainer, typename _MappedContainer>
> > + class flat_multimap;
> > +
> > + template<typename _Key, typename _Tp, typename _Compare,
> > + typename _KeyContainer, typename _MappedContainer, bool _Multi>
> > + 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<bool _Const> struct _Iterator;
> > +
> > + using key_type = _Key;
> > + using mapped_type = _Tp;
> > + using value_type = pair<key_type, mapped_type>;
> > + using key_compare = _Compare;
> > + using reference = pair<const key_type&, mapped_type&>;
> > + using const_reference = pair<const key_type&, const
> > mapped_type&>;
> > + using size_type = size_t;
> > + using difference_type = ptrdiff_t;
> > + using iterator = _Iterator<false>;
> > + using const_iterator = _Iterator<true>;
> > + using reverse_iterator = std::reverse_iterator<iterator>;
> > + using const_reverse_iterator =
> > std::reverse_iterator<const_iterator>;
> > + using key_container_type = _KeyContainer;
> > + using mapped_container_type = _MappedContainer;
> > +
> > + private:
> > + using __emplace_result_t = __conditional_t<_Multi, iterator,
> > pair<iterator, bool>>;
> > +
> > + 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<typename _InputIterator,
> > + typename = _RequireInputIter<_InputIterator>>
> > + _Flat_map_impl(_InputIterator __first, _InputIterator __last,
> > + const key_compare& __comp = key_compare())
> > + : _M_cont(), _M_comp(__comp)
> > + { insert(__first, __last); }
> > +
> > + template<typename _InputIterator,
> > + typename = _RequireInputIter<_InputIterator>>
> > + _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<value_type> __il,
> > + const key_compare& __comp = key_compare())
> > + : _Flat_map_impl(__il.begin(), __il.end(), __comp)
> > + { }
> > +
> > + _Flat_map_impl(__sorted_t __s,
> > + initializer_list<value_type> __il,
> > + const key_compare& __comp = key_compare())
> > + : _Flat_map_impl(__s, __il.begin(), __il.end(), __comp)
> > + { }
> > +
> > + // constructors with allocators
> > +
> > + template<typename _Alloc>
> > + explicit
> > + _Flat_map_impl(const _Alloc& __a)
> > + : _Flat_map_impl(key_compare(), __a)
> > + { }
> > +
> > + template<typename _Alloc>
> > + _Flat_map_impl(const key_compare& __comp, const _Alloc& __a)
> > + : _M_cont(std::make_obj_using_allocator<key_container_type>(__a),
> > + std::make_obj_using_allocator<mapped_container_type>(__a)),
> > + _M_comp(__comp)
> > + { }
> > +
> > + template<typename _Alloc>
> > + _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<typename _Alloc>
> > + _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<key_container_type>(__a,
> > __key_cont),
> > + std::make_obj_using_allocator<mapped_container_type>(__a,
> > __mapped_cont)),
> > + _M_comp(__comp)
> > + {
> > + __glibcxx_assert(_M_cont.keys.size() == _M_cont.values.size());
> > + _M_sort_uniq();
> > + }
> > +
> > + template<typename _Alloc>
> > + _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<typename _Alloc>
> > + _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<key_container_type>(__a,
> > __key_cont),
> > + std::make_obj_using_allocator<mapped_container_type>(__a,
> > __mapped_cont))
> > + { __glibcxx_assert(_M_cont.keys.size() == _M_cont.values.size()); }
> > +
> > + template<typename _Alloc>
> > + _Flat_map_impl(const _Derived& __x, const _Alloc& __a)
> > + : _M_comp(__x._M_comp),
> > + _M_cont(std::make_obj_using_allocator<containers>(__a, __x._M_cont))
> > + { }
> > +
> > + template<typename _Alloc>
> > + _Flat_map_impl(_Derived&& __x, const _Alloc& __a)
> > + : _M_comp(__x._M_comp),
> > + _M_cont(std::make_obj_using_allocator<containers>(__a,
> > std::move(__x._M_cont)))
> > + { }
> > +
> > + template<typename _InputIterator, typename _Alloc,
> > + typename = _RequireInputIter<_InputIterator>>
> > + _Flat_map_impl(_InputIterator __first, _InputIterator __last,
> > + const _Alloc& __a)
> > + : _Flat_map_impl(std::move(__first), std::move(__last), key_compare(),
> > __a)
> > + { }
> > +
> > + template<typename _InputIterator, typename _Alloc,
> > + typename = _RequireInputIter<_InputIterator>>
> > + _Flat_map_impl(_InputIterator __first, _InputIterator __last,
> > + const key_compare& __comp,
> > + const _Alloc& __a)
> > + : _Flat_map_impl(__comp, __a)
> > + { insert(__first, __last); }
> > +
> > + template<typename _InputIterator, typename _Alloc,
> > + typename = _RequireInputIter<_InputIterator>>
> > + _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<typename _InputIterator, typename _Alloc,
> > + typename = _RequireInputIter<_InputIterator>>
> > + _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<typename _Alloc>
> > + _Flat_map_impl(initializer_list<value_type> __il,
> > + const _Alloc& __a)
> > + : _Flat_map_impl(__il, key_compare(), __a)
> > + { }
> > +
> > + template<typename _Alloc>
> > + _Flat_map_impl(initializer_list<value_type> __il,
> > + const key_compare& __comp,
> > + const _Alloc& __a)
> > + : _Flat_map_impl(__il.begin(), __il.end(), __comp, __a)
> > + { }
> > +
> > + template<typename _Alloc>
> > + _Flat_map_impl(__sorted_t __s,
> > + initializer_list<value_type> __il,
> > + const _Alloc& __a)
> > + : _Flat_map_impl(__s, __il.begin(), __il.end(), key_compare(), __a)
> > + { }
> > +
> > + template<typename _Alloc>
> > + _Flat_map_impl(__sorted_t __s,
> > + initializer_list<value_type> __il,
> > + const key_compare& __comp,
> > + const _Alloc& __a)
> > + : _Flat_map_impl(__s, __il.begin(), __il.end(), __comp, __a)
> > + { }
> > +
> > + _Derived&
> > + operator=(initializer_list<value_type> __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<size_type>(keys().max_size(),
> > values().max_size()); }
> > +
> > + // element access
> > + // operator[] and at defined directly in class flat_map only.
> > +
> > + // modifiers
> > + template<typename _Key2, typename... _Args>
> > + pair<iterator, bool>
> > + _M_try_emplace(optional<const_iterator> __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 = std::lower_bound(__first, __last, __k, _M_comp);
> > + else
> > + // Insert after the rightmost equivalent key.
> > + __key_it =
> > std::upper_bound(std::make_reverse_iterator(__last),
> > +
> > std::make_reverse_iterator(__first),
> > + __k,
> > std::not_fn(_M_comp)).base();
> > + }
> > + else
> > + __key_it = std::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<typename... _Args>
> > + requires is_constructible_v<value_type, _Args...>
> > + __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<typename... _Args>
> > + 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<typename _Arg>
> > + requires is_constructible_v<value_type, _Arg>
> > + __emplace_result_t
> > + insert(_Arg&& __x)
> > + { return emplace(std::forward<_Arg>(__x)); }
> > +
> > + template<typename _Arg>
> > + requires is_constructible_v<value_type, _Arg>
> > + iterator
> > + insert(const_iterator __position, _Arg&& __x)
> > + { return emplace_hint(__position, std::forward<_Arg>(__x)); }
> > +
> > + template<typename _InputIterator, typename =
> > _RequireInputIter<_InputIterator>>
> > + 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<typename _InputIterator, typename =
> > _RequireInputIter<_InputIterator>>
> > + 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<value_type> __il)
> > + { insert(__il.begin(), __il.end()); }
> > +
> > + void
> > + insert(__sorted_t __s, initializer_list<value_type> __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<const_iterator>(__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<const key_type&>(__x); }
> > +
> > + template<typename _Key2>
> > + requires same_as<remove_cvref_t<_Key2>, _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<key_type>(__x); }
> > +
> > + const_iterator
> > + find(const key_type& __x) const
> > + { return find<key_type>(__x); }
> > +
> > + template<typename _Key2>
> > + 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<typename _Key2>
> > + 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
> > + { return count<key_type>(__x); }
> > +
> > + template<typename _Key2>
> > + requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
> > + size_type
> > + count(const _Key2& __x) const
> > + {
> > + if constexpr (!_Multi && same_as<_Key2, _Key>)
> > + return contains(__x);
> > + else
> > + {
> > + auto [__first, __last] = equal_range(__x);
> > + return __last - __first;
> > + }
> > + }
> > +
> > + bool
> > + contains(const key_type& __x) const
> > + { return contains<key_type>(__x); }
> > +
> > + template<typename _Key2>
> > + 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<key_type>(__x); }
> > +
> > + const_iterator
> > + lower_bound(const key_type& __x) const
> > + { return lower_bound<key_type>(__x); }
> > +
> > + template<typename _Key2>
> > + 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<typename _Key2>
> > + 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<key_type>(__x); }
> > +
> > + const_iterator
> > + upper_bound(const key_type& __x) const
> > + { return upper_bound<key_type>(__x); }
> > +
> > + template<typename _Key2>
> > + 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<typename _Key2>
> > + 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<iterator, iterator>
> > + equal_range(const key_type& __x)
> > + { return equal_range<key_type>(__x); }
> > +
> > + pair<const_iterator, const_iterator>
> > + equal_range(const key_type& __x) const
> > + { return equal_range<key_type>(__x); }
> > +
> > + template<typename _Key2>
> > + requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
> > + pair<iterator, iterator>
> > + equal_range(const _Key2& __x)
> > + {
> > + auto [__first, __last] = std::equal_range(_M_cont.keys.begin(),
> > + _M_cont.keys.end(),
> > + __x, _M_comp);
> > + return {{this, __first}, {this, __last}};
> > + }
> > +
> > + template<typename _Key2>
> > + requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
> > + pair<const_iterator, const_iterator>
> > + equal_range(const _Key2& __x) const
> > + {
> > + auto [__first, __last] = std::equal_range(_M_cont.keys.begin(),
> > + _M_cont.keys.end(),
> > + __x, _M_comp);
> > + return {{this, __first}, {this, __last}};
> > + }
> > +
> > + friend bool
> > + operator==(const _Derived& __x, const _Derived& __y)
> > + { return std::equal(__x.begin(), __x.end(), __y.begin(), __y.end());
> > }
> > +
> > + template<typename _Up = value_type>
> > + 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<typename _Predicate>
> > + 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<typename _Key, typename _Tp, typename _Compare,
> > + typename _KeyContainer, typename _MappedContainer, bool _Multi>
> > + template<bool _Const>
> > + 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<const key_type, mapped_type>;
> > + using reference = pair<const key_type&,
> > + ranges::__maybe_const_t<_Const,
> > mapped_type>&>;
> > + using difference_type = ptrdiff_t;
> > +
> > + _Iterator() = default;
> > +
> > + _Iterator(_Iterator<!_Const> __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<!_Const>;
> > +
> > + _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 _Key, typename _Tp, typename _Compare = less<_Key>,
> > + 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[]<const key_type>(__x); }
> > +
> > + mapped_type&
> > + operator[](key_type&& __x)
> > + { return operator[]<key_type>(std::move(__x)); }
> > +
> > + template<typename _Key2>
> > + requires same_as<remove_cvref_t<_Key2>, _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<key_type>(__x); }
> > +
> > + const mapped_type&
> > + at(const key_type& __x) const
> > + { return at<key_type>(__x); }
> > +
> > + template<typename _Key2>
> > + 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<typename _Key2>
> > + 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<typename... _Args>
> > + requires is_constructible_v<mapped_type, _Args...>
> > + pair<iterator, bool>
> > + try_emplace(const key_type& __k, _Args&&... __args)
> > + { return _Impl::_M_try_emplace(nullopt, __k,
> > std::forward<_Args>(__args)...); }
> > +
> > + template<typename... _Args>
> > + requires is_constructible_v<mapped_type, _Args...>
> > + pair<iterator, bool>
> > + try_emplace(key_type&& __k, _Args&&... __args)
> > + {
> > + return _Impl::_M_try_emplace(nullopt, std::move(__k),
> > + std::forward<_Args>(__args)...);
> > + }
> > +
> > + template<typename _Key2, typename... _Args>
> > + requires __transparent_comparator<_Compare>
> > + && is_constructible_v<key_type, _Key2>
> > + && is_constructible_v<mapped_type, _Args...>
> > + && (!is_convertible_v<_Key2&&, const_iterator>)
> > + && (!is_convertible_v<_Key2&&, iterator>)
> > + pair<iterator, bool>
> > + try_emplace(_Key2&& __k, _Args&&... __args)
> > + {
> > + return _Impl::_M_try_emplace(nullopt, std::forward<_Key2>(__k),
> > + std::forward<_Args>(__args)...);
> > + }
> > +
> > + template<typename... _Args>
> > + requires is_constructible_v<mapped_type, _Args...>
> > + 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<typename... _Args>
> > + requires is_constructible_v<mapped_type, _Args...>
> > + 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<typename _Key2, typename... _Args>
> > + requires __transparent_comparator<_Compare>
> > + && is_constructible_v<key_type, _Key2>
> > + && is_constructible_v<mapped_type, _Args...>
> > + 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<typename _Mapped>
> > + requires is_assignable_v<mapped_type&, _Mapped>
> > + && is_constructible_v<mapped_type, _Mapped>
> > + pair<iterator, bool>
> > + insert_or_assign(const key_type& __k, _Mapped&& __obj)
> > + { return insert_or_assign<const key_type&, _Mapped>(__k,
> > std::forward<_Mapped>(__obj)); }
> > +
> > + template<typename _Mapped>
> > + requires is_assignable_v<mapped_type&, _Mapped>
> > + && is_constructible_v<mapped_type, _Mapped>
> > + pair<iterator, bool>
> > + insert_or_assign(key_type&& __k, _Mapped&& __obj)
> > + {
> > + return insert_or_assign<key_type, _Mapped>(std::move(__k),
> > +
> > std::forward<_Mapped>(__obj));
> > + }
> > +
> > + template<typename _Key2, typename _Mapped>
> > + requires (same_as<remove_cvref_t<_Key2>, _Key> ||
> > __transparent_comparator<_Compare>)
> > + && is_constructible_v<key_type, _Key2>
> > + && is_assignable_v<mapped_type&, _Mapped>
> > + && is_constructible_v<mapped_type, _Mapped>
> > + pair<iterator, bool>
> > + 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<typename _Mapped>
> > + requires is_assignable_v<mapped_type&, _Mapped>
> > + && is_constructible_v<mapped_type, _Mapped>
> > + iterator
> > + insert_or_assign(const_iterator __hint, const key_type& __k, _Mapped&&
> > __obj)
> > + {
> > + return insert_or_assign<const key_type&, _Mapped>(__hint, __k,
> > +
> > std::forward<_Mapped>(__obj));
> > + }
> > +
> > + template<typename _Mapped>
> > + requires is_assignable_v<mapped_type&, _Mapped>
> > + && is_constructible_v<mapped_type, _Mapped>
> > + iterator
> > + insert_or_assign(const_iterator __hint, key_type&& __k, _Mapped&& __obj)
> > + {
> > + return insert_or_assign<key_type, _Mapped>(__hint, std::move(__k),
> > +
> > std::forward<_Mapped>(__obj));
> > + }
> > +
> > + template<typename _Key2, typename _Mapped>
> > + requires (same_as<remove_cvref_t<_Key2>, _Key> ||
> > __transparent_comparator<_Compare>)
> > + && is_constructible_v<key_type, _Key2>
> > + && is_assignable_v<mapped_type&, _Mapped>
> > + && is_constructible_v<mapped_type, _Mapped>
> > + 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 _KeyContainer, typename _MappedContainer,
> > + typename _Compare = less<typename _KeyContainer::value_type>,
> > + typename = _RequireNotAllocator<_Compare>>
> > + flat_map(_KeyContainer, _MappedContainer, _Compare = _Compare())
> > + -> flat_map<typename _KeyContainer::value_type, typename
> > _MappedContainer::value_type,
> > + _Compare, _KeyContainer, _MappedContainer>;
> > +
> > + template<typename _KeyContainer, typename _MappedContainer, typename
> > _Alloc,
> > + typename = _RequireAllocator<_Alloc>>
> > + flat_map(_KeyContainer, _MappedContainer, _Alloc)
> > + -> flat_map<typename _KeyContainer::value_type, typename
> > _MappedContainer::value_type,
> > + less<typename _KeyContainer::value_type>, _KeyContainer,
> > _MappedContainer>;
> > +
> > + template<typename _KeyContainer, typename _MappedContainer, typename
> > _Compare, typename _Alloc,
> > + typename = _RequireNotAllocator<_Compare>,
> > + typename = _RequireAllocator<_Alloc>>
> > + flat_map(_KeyContainer, _MappedContainer, _Compare, _Alloc)
> > + -> flat_map<typename _KeyContainer::value_type, typename
> > _MappedContainer::value_type,
> > + _Compare, _KeyContainer, _MappedContainer>;
> > +
> > + template<typename _KeyContainer, typename _MappedContainer,
> > + typename _Compare = less<typename _KeyContainer::value_type>,
> > + typename = _RequireNotAllocator<_Compare>>
> > + flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Compare =
> > _Compare())
> > + -> flat_map<typename _KeyContainer::value_type, typename
> > _MappedContainer::value_type,
> > + _Compare, _KeyContainer, _MappedContainer>;
> > +
> > + template<typename _KeyContainer, typename _MappedContainer, typename
> > _Alloc,
> > + typename = _RequireAllocator<_Alloc>>
> > + flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Alloc)
> > + -> flat_map<typename _KeyContainer::value_type, typename
> > _MappedContainer::value_type,
> > + less<typename _KeyContainer::value_type>, _KeyContainer,
> > _MappedContainer>;
> > +
> > + template<typename _KeyContainer, typename _MappedContainer, typename
> > _Compare, typename _Alloc,
> > + typename = _RequireNotAllocator<_Compare>,
> > + typename = _RequireAllocator<_Alloc>>
> > + flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Compare,
> > _Alloc)
> > + -> flat_map<typename _KeyContainer::value_type, typename
> > _MappedContainer::value_type,
> > + _Compare, _KeyContainer, _MappedContainer>;
> > +
> > + template<typename _InputIterator, typename _Compare =
> > less<__iter_key_t<_InputIterator>>,
> > + 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 _InputIterator, typename _Compare =
> > less<__iter_key_t<_InputIterator>>,
> > + 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 _Key, typename _Tp, typename _Compare = less<_Key>,
> > + typename = _RequireNotAllocator<_Compare>>
> > + flat_map(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare())
> > + -> flat_map<_Key, _Tp, _Compare>;
> > +
> > + template<typename _Key, typename _Tp, typename _Compare = less<_Key>,
> > + typename = _RequireNotAllocator<_Compare>>
> > + flat_map(sorted_unique_t, initializer_list<pair<_Key, _Tp>>, _Compare
> > = _Compare())
> > + -> flat_map<_Key, _Tp, _Compare>;
> > +
> > + template<typename _Key, typename _Tp, typename _Compare,
> > + typename _KeyContainer, typename _MappedContainer, typename _Alloc>
> > + struct uses_allocator<flat_map<_Key, _Tp, _Compare, _KeyContainer,
> > _MappedContainer>, _Alloc>
> > + : bool_constant<uses_allocator_v<_KeyContainer, _Alloc>
> > + && uses_allocator_v<_MappedContainer, _Alloc>>
> > + { };
> > +
> > + /* Class template flat_multimap - container adaptor
> > + *
> > + * @ingroup
> > + */
> > + template<typename _Key, typename _Tp, typename _Compare = less<_Key>,
> > + 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 _KeyContainer, typename _MappedContainer,
> > + typename _Compare = less<typename _KeyContainer::value_type>,
> > + typename = _RequireNotAllocator<_Compare>>
> > + flat_multimap(_KeyContainer, _MappedContainer, _Compare = _Compare())
> > + -> flat_multimap<typename _KeyContainer::value_type, typename
> > _MappedContainer::value_type,
> > + _Compare, _KeyContainer, _MappedContainer>;
> > +
> > + template<typename _KeyContainer, typename _MappedContainer, typename
> > _Alloc,
> > + typename = _RequireAllocator<_Alloc>>
> > + flat_multimap(_KeyContainer, _MappedContainer, _Alloc)
> > + -> flat_multimap<typename _KeyContainer::value_type, typename
> > _MappedContainer::value_type,
> > + less<typename _KeyContainer::value_type>, _KeyContainer,
> > _MappedContainer>;
> > +
> > + template<typename _KeyContainer, typename _MappedContainer, typename
> > _Compare, typename _Alloc,
> > + typename = _RequireNotAllocator<_Compare>,
> > + typename = _RequireAllocator<_Alloc>>
> > + flat_multimap(_KeyContainer, _MappedContainer, _Compare, _Alloc)
> > + -> flat_multimap<typename _KeyContainer::value_type, typename
> > _MappedContainer::value_type,
> > + _Compare, _KeyContainer, _MappedContainer>;
> > +
> > + template<typename _KeyContainer, typename _MappedContainer,
> > + typename _Compare = less<typename _KeyContainer::value_type>,
> > + typename = _RequireNotAllocator<_Compare>>
> > + flat_multimap(sorted_equivalent_t, _KeyContainer, _MappedContainer,
> > _Compare = _Compare())
> > + -> flat_multimap<typename _KeyContainer::value_type, typename
> > _MappedContainer::value_type,
> > + _Compare, _KeyContainer, _MappedContainer>;
> > +
> > + template<typename _KeyContainer, typename _MappedContainer, typename
> > _Alloc,
> > + typename = _RequireAllocator<_Alloc>>
> > + flat_multimap(sorted_equivalent_t, _KeyContainer, _MappedContainer,
> > _Alloc)
> > + -> flat_multimap<typename _KeyContainer::value_type, typename
> > _MappedContainer::value_type,
> > + less<typename _KeyContainer::value_type>, _KeyContainer,
> > _MappedContainer>;
> > +
> > + template<typename _KeyContainer, typename _MappedContainer, typename
> > _Compare, typename _Alloc,
> > + typename = _RequireNotAllocator<_Compare>,
> > + typename = _RequireAllocator<_Alloc>>
> > + flat_multimap(sorted_equivalent_t, _KeyContainer, _MappedContainer,
> > _Compare, _Alloc)
> > + -> flat_multimap<typename _KeyContainer::value_type, typename
> > _MappedContainer::value_type,
> > + _Compare, _KeyContainer, _MappedContainer>;
> > +
> > + template<typename _InputIterator, typename _Compare =
> > less<__iter_key_t<_InputIterator>>,
> > + 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 _InputIterator, typename _Compare =
> > less<__iter_key_t<_InputIterator>>,
> > + 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 _Key, typename _Tp, typename _Compare = less<_Key>,
> > + typename = _RequireNotAllocator<_Compare>>
> > + flat_multimap(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare())
> > + -> flat_multimap<_Key, _Tp, _Compare>;
> > +
> > + template<typename _Key, typename _Tp, typename _Compare = less<_Key>,
> > + typename = _RequireNotAllocator<_Compare>>
> > + flat_multimap(sorted_equivalent_t, initializer_list<pair<_Key, _Tp>>,
> > _Compare = _Compare())
> > + -> flat_multimap<_Key, _Tp, _Compare>;
> > +
> > + template<typename _Key, typename _Tp, typename _Compare,
> > + typename _KeyContainer, typename _MappedContainer, typename _Alloc>
> > + struct uses_allocator<flat_multimap<_Key, _Tp, _Compare,
> > _KeyContainer, _MappedContainer>,
> > + _Alloc>
> > + : bool_constant<uses_allocator_v<_KeyContainer, _Alloc>
> > + && 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..1e387a3ad90
> > --- /dev/null
> > +++ b/libstdc++-v3/testsuite/23_containers/flat_map/1.cc
> > @@ -0,0 +1,123 @@
> > +// { dg-do run { target c++23 } }
> > +
> > +#include <flat_map>
> > +#include <deque>
> > +#include <testsuite_hooks.h>
> > +
> > +#if __cpp_lib_flat_map != 202207L
> > +# error "Feature-test macro __cpp_lib_flat_map has wrong value in
> > <flat_map>"
> > +#endif
> > +
> > +template<template<class> class Sequence>
> > +void
> > +test01()
> > +{
> > + std::flat_map<int, int, std::less<int>, Sequence<int>, Sequence<int>> m;
> > + static_assert( std::ranges::random_access_range<decltype(m)> );
> > +
> > + 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<int, int, std::greater<int>> m;
> > + static_assert( std::ranges::random_access_range<decltype(m)> );
> > +
> > + 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 );
> > +}
> > +
> > +void
> > +test03()
> > +{
> > + std::flat_map<int, int> m;
> > + m = {std::pair(1, 2), {3, 4}, {5, 6}};
> > + m.insert({std::pair(7, 8), {9, 10}});
> > +
> > + auto it = m.find(0);
> > + VERIFY( it == m.end() );
> > + it = m.find(9);
> > + VERIFY( it->second == 10 );
> > +
> > + const auto n = m;
> > + VERIFY( m == m );
> > + VERIFY( m == n );
> > +
> > + m.erase(m.begin());
> > + m.erase(5);
> > + m.erase(m.end()-2, m.end());
> > + VERIFY( std::ranges::equal(m, (std::pair<int, int>[]){{3, 4}}) );
> > + VERIFY( m != n );
> > + VERIFY( n < m );
> > +
> > + m = n;
> > + erase_if(m, [](const auto& x) { auto [k, v] = x; return k < 5 || k > 5;
> > });
> > + VERIFY( std::ranges::equal(m, (std::pair<int, int>[]){{5, 6}}) );
> > +}
> > +
> > +int
> > +main()
> > +{
> > + test01<std::vector>();
> > + test01<std::deque>();
> > + test02();
> > + test03();
> > +}
> > 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..d9732e2afa6
> > --- /dev/null
> > +++ b/libstdc++-v3/testsuite/23_containers/flat_multimap/1.cc
> > @@ -0,0 +1,106 @@
> > +// { dg-do run { target c++23 } }
> > +
> > +#include <flat_map>
> > +#include <deque>
> > +#include <testsuite_hooks.h>
> > +
> > +template<template<class> class Sequence>
> > +void
> > +test01()
> > +{
> > + std::flat_multimap<int, int, std::less<int>, Sequence<int>,
> > Sequence<int>> m;
> > + static_assert( std::ranges::random_access_range<decltype(m)> );
> > +
> > + 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<int, int, std::greater<int>> m;
> > + static_assert( std::ranges::random_access_range<decltype(m)> );
> > +
> > + 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 );
> > +}
> > +
> > +void
> > +test03()
> > +{
> > + std::flat_multimap<int, int> m;
> > + m = {std::pair(1, 2), {3, 4}, {5, 6}};
> > + m.insert({std::pair(7, 8), {9, 10}});
> > +
> > + auto it = m.find(0);
> > + VERIFY( it == m.end() );
> > + it = m.find(9);
> > + VERIFY( it->second == 10 );
> > +
> > + const auto n = m;
> > + VERIFY( m == m );
> > + VERIFY( m == n );
> > +
> > + m.erase(m.begin());
> > + m.erase(5);
> > + m.erase(m.end()-2, m.end());
> > + VERIFY( std::ranges::equal(m, (std::pair<int, int>[]){{3, 4}}) );
> > + VERIFY( m != n );
> > + VERIFY( n < m );
> > +
> > + m = n;
> > + erase_if(m, [](const auto& x) { auto [k, v] = x; return k < 5 || k > 5;
> > });
> > + VERIFY( std::ranges::equal(m, (std::pair<int, int>[]){{5, 6}}) );
> > +}
> > +
> > +int
> > +main()
> > +{
> > + test01<std::vector>();
> > + test01<std::deque>();
> > + test02();
> > + test03();
> > +}
> > --
> > 2.47.0.86.g15030f9556
> >
>
