| Message ID | 20241001034358.1375479-1-ppalka@redhat.com |
|---|---|
| State | New |
| Headers | show |
| Series | [1/2] libstdc++: Implement C++23 <flat_map> (P0429R9) | expand |
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. -- >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(); +}
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 > > -- >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 >
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 f2e28175b08..631eca7beac 100644 --- a/libstdc++-v3/include/bits/version.def +++ b/libstdc++-v3/include/bits/version.def @@ -1658,6 +1658,14 @@ ftms = { }; }; +ftms = { + name = flat_map; + values = { + v = 202207; + cxxmin = 23; + }; +}; + ftms = { name = formatters; values = { diff --git a/libstdc++-v3/include/bits/version.h b/libstdc++-v3/include/bits/version.h index dcd93fd432d..1f3040fcbde 100644 --- a/libstdc++-v3/include/bits/version.h +++ b/libstdc++-v3/include/bits/version.h @@ -1830,6 +1830,16 @@ #endif /* !defined(__cpp_lib_adaptor_iterator_pair_constructor) && defined(__glibcxx_want_adaptor_iterator_pair_constructor) */ #undef __glibcxx_want_adaptor_iterator_pair_constructor +#if !defined(__cpp_lib_flat_map) +# if (__cplusplus >= 202100L) +# define __glibcxx_flat_map 202207L +# if defined(__glibcxx_want_all) || defined(__glibcxx_want_flat_map) +# define __cpp_lib_flat_map 202207L +# endif +# endif +#endif /* !defined(__cpp_lib_flat_map) && defined(__glibcxx_want_flat_map) */ +#undef __glibcxx_want_flat_map + #if !defined(__cpp_lib_formatters) # if (__cplusplus >= 202100L) && _GLIBCXX_HOSTED # define __glibcxx_formatters 202302L diff --git a/libstdc++-v3/include/std/flat_map b/libstdc++-v3/include/std/flat_map new file mode 100644 index 00000000000..83bb9c19d84 --- /dev/null +++ b/libstdc++-v3/include/std/flat_map @@ -0,0 +1,1477 @@ +// <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 = ranges::lower_bound(__first, __last, __k, _M_comp); + else + // Insert after the rightmost equivalent key. + __key_it = ranges::upper_bound(std::make_reverse_iterator(__last), + std::make_reverse_iterator(__first), + __k, std::not_fn(_M_comp)).base(); + } + else + __key_it = ranges::lower_bound(__first, __last, __k, _M_comp); + } + + if constexpr (!_Multi) + if (__key_it != _M_cont.keys.end() && !_M_comp(__k, __key_it[0])) + return {iterator{this, __key_it}, false}; + + __key_it = _M_cont.keys.insert(__key_it, std::move(__k)); + __try + { + auto __value_it = _M_cont.values.begin() + (__key_it - _M_cont.keys.begin()); + _M_cont.values.emplace(__value_it, std::forward<_Args>(__args)...); + } + __catch(...) + { + _M_cont.keys.erase(__key_it); + __throw_exception_again; + } + return {iterator{this, __key_it}, true}; + } + + template<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 + { + if constexpr (_Multi) + return count<key_type>(__x); + else + return contains(__x); + } + + template<typename _Key2> + requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> + size_type + count(const _Key2& __x) const + { + auto [__first, __last] = equal_range(__x); + return __last - __first; + } + + bool + contains(const key_type& __x) const + { return contains<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] = ranges::equal_range(_M_cont.keys, __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] = ranges::equal_range(_M_cont.keys, __x, _M_comp); + return {{this, __first}, {this, __last}}; + } + + friend bool + operator==(const _Derived& __x, const _Derived& __y) + { + return ranges::equal(__x._M_cont.keys, __y._M_cont.keys) + && ranges::equal(__x._M_cont.values, __y._M_cont.values); + } + + template<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(const _Iterator&) = default; + _Iterator& operator=(const _Iterator&) = default; + + // Allow conversion from iterator to const_iterator + _Iterator(const _Iterator<false>& __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..e56ac5394f3 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/flat_map/1.cc @@ -0,0 +1,90 @@ +// { dg-do run { target c++23 } } + +#include <flat_map> +#include <deque> +#include <testsuite_hooks.h> + +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 ); +} + +int +main() +{ + test01<std::vector>(); + test01<std::deque>(); + test02(); +} diff --git a/libstdc++-v3/testsuite/23_containers/flat_multimap/1.cc b/libstdc++-v3/testsuite/23_containers/flat_multimap/1.cc new file mode 100644 index 00000000000..3a245b94ebe --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/flat_multimap/1.cc @@ -0,0 +1,77 @@ +// { dg-do run { target c++23 } } + +#include <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 ); +} + +int +main() +{ + test01<std::vector>(); + test01<std::deque>(); + test02(); +}
This implements the C++23 container adaptors std::flat_map and std::flat_multimap from P0429R9. The implementation is shared as much as possible between the two adaptors via a common base class that's parameterized according to key uniqueness. The main known issues are: * the range insert() overload exceeds its complexity requirements since an idiomatic efficient implementation needs a non-buggy ranges::inplace_merge * exception safety is likely incomplete/buggy * unimplemented from_range_t constructors and insert_range function * the main workhorse function _M_try_emplace is probably buggy buggy wrt its handling of the hint parameter and could be simplified * more extensive testcases are a WIP The iterator type is encoded as a {pointer, index} pair instead of an {iterator, iterator} pair. I'm not sure which encoding is preferable? It seems the latter would allow for better debuggability when the underlying iterators are debug iterators. libstdc++-v3/ChangeLog: * include/Makefile.am: Add new header. * include/Makefile.in: Regenerate. * include/bits/stl_function.h (__transparent_comparator): Define. * include/bits/utility.h (sorted_unique_t): Define for C++23. (sorted_unique): Likewise. (sorted_equivalent_t): Likewise. (sorted_equivalent): Likewise. * include/bits/version.def (flat_map): Define. * include/bits/version.h: Regenerate. * include/std/flat_map: New file. * testsuite/23_containers/flat_map/1.cc: New test. * testsuite/23_containers/flat_multimap/1.cc: New test. --- libstdc++-v3/include/Makefile.am | 1 + libstdc++-v3/include/Makefile.in | 1 + libstdc++-v3/include/bits/stl_function.h | 6 + libstdc++-v3/include/bits/utility.h | 8 + libstdc++-v3/include/bits/version.def | 8 + libstdc++-v3/include/bits/version.h | 10 + libstdc++-v3/include/std/flat_map | 1477 +++++++++++++++++ .../testsuite/23_containers/flat_map/1.cc | 90 + .../23_containers/flat_multimap/1.cc | 77 + 9 files changed, 1678 insertions(+) create mode 100644 libstdc++-v3/include/std/flat_map create mode 100644 libstdc++-v3/testsuite/23_containers/flat_map/1.cc create mode 100644 libstdc++-v3/testsuite/23_containers/flat_multimap/1.cc