| Message ID | 20241001034358.1375479-2-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_set and > std::flat_multiset from P1222R4. The implementation is essentially > an simpler and pared down version of std::flat_map. > > The main known issues are: > > * exception safety is likely incomplete/buggy > * unimplemented from_range_t constructors and insert_range function > * the main worthouse function _M_try_emplace is probably buggy > wrt its handling of the hint parameter and could be simplified > * more extensive testcases are a WIP Here's v2 which adds somewhat more tests and uses 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_set>. * include/Makefile.in: Regenerate. * include/bits/version.def (__cpp_flat_set): Define. * include/bits/version.h: Regenerate * include/std/flat_set: New file. * testsuite/23_containers/flat_multiset/1.cc: New test. * testsuite/23_containers/flat_set/1.cc: New test. --- libstdc++-v3/include/Makefile.am | 1 + libstdc++-v3/include/Makefile.in | 1 + libstdc++-v3/include/bits/version.def | 8 + libstdc++-v3/include/bits/version.h | 10 + libstdc++-v3/include/std/flat_set | 972 ++++++++++++++++++ .../23_containers/flat_multiset/1.cc | 102 ++ .../testsuite/23_containers/flat_set/1.cc | 111 ++ 7 files changed, 1205 insertions(+) create mode 100644 libstdc++-v3/include/std/flat_set create mode 100644 libstdc++-v3/testsuite/23_containers/flat_multiset/1.cc create mode 100644 libstdc++-v3/testsuite/23_containers/flat_set/1.cc diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am index 632bbafa63e..e49cdb23c55 100644 --- a/libstdc++-v3/include/Makefile.am +++ b/libstdc++-v3/include/Makefile.am @@ -71,6 +71,7 @@ std_headers = \ ${std_srcdir}/execution \ ${std_srcdir}/filesystem \ ${std_srcdir}/flat_map \ + ${std_srcdir}/flat_set \ ${std_srcdir}/format \ ${std_srcdir}/forward_list \ ${std_srcdir}/fstream \ diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in index 1ac963c4415..8e6ee44cc0e 100644 --- a/libstdc++-v3/include/Makefile.in +++ b/libstdc++-v3/include/Makefile.in @@ -427,6 +427,7 @@ std_freestanding = \ @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/execution \ @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/filesystem \ @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/flat_map \ +@GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/flat_set \ @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/format \ @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/forward_list \ @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/fstream \ diff --git a/libstdc++-v3/include/bits/version.def b/libstdc++-v3/include/bits/version.def index 6f1958ac705..7d12cdf07f1 100644 --- a/libstdc++-v3/include/bits/version.def +++ b/libstdc++-v3/include/bits/version.def @@ -1666,6 +1666,14 @@ ftms = { }; }; +ftms = { + name = flat_set; + values = { + v = 202207; + cxxmin = 23; + }; +}; + ftms = { name = formatters; values = { diff --git a/libstdc++-v3/include/bits/version.h b/libstdc++-v3/include/bits/version.h index ecead3edb26..76a88a17351 100644 --- a/libstdc++-v3/include/bits/version.h +++ b/libstdc++-v3/include/bits/version.h @@ -1840,6 +1840,16 @@ #endif /* !defined(__cpp_lib_flat_map) && defined(__glibcxx_want_flat_map) */ #undef __glibcxx_want_flat_map +#if !defined(__cpp_lib_flat_set) +# if (__cplusplus >= 202100L) +# define __glibcxx_flat_set 202207L +# if defined(__glibcxx_want_all) || defined(__glibcxx_want_flat_set) +# define __cpp_lib_flat_set 202207L +# endif +# endif +#endif /* !defined(__cpp_lib_flat_set) && defined(__glibcxx_want_flat_set) */ +#undef __glibcxx_want_flat_set + #if !defined(__cpp_lib_formatters) # if (__cplusplus >= 202100L) && _GLIBCXX_HOSTED # define __glibcxx_formatters 202302L diff --git a/libstdc++-v3/include/std/flat_set b/libstdc++-v3/include/std/flat_set new file mode 100644 index 00000000000..53bda6e03a3 --- /dev/null +++ b/libstdc++-v3/include/std/flat_set @@ -0,0 +1,972 @@ +// <flat_set> -*- 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_set + * This is a Standard C++ Library header. + */ + +#ifndef _GLIBCXX_FLAT_SET +#define _GLIBCXX_FLAT_SET 1 + +#ifdef _GLIBCXX_SYSHDR +#pragma GCC system_header +#endif + +#define __glibcxx_want_flat_set +#include <bits/version.h> + +#ifdef __cpp_lib_flat_set // >= 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 _Compare, + typename _KeyContainer> + class flat_set; + + template<typename _Key, typename _Compare, + typename _KeyContainer> + class flat_multiset; + + template<typename _Key, typename _Compare, typename _KeyContainer, bool _Multi> + class _Flat_set_impl + { + static_assert(is_same_v<_Key, typename _KeyContainer::value_type>); + static_assert(is_nothrow_swappable_v<_KeyContainer>); + + using _Derived = __conditional_t<_Multi, + flat_multiset<_Key, _Compare, _KeyContainer>, + flat_set<_Key, _Compare, _KeyContainer>>; + using __sorted_t = __conditional_t<_Multi, sorted_equivalent_t, sorted_unique_t>; + + public: + using key_type = _Key; + using value_type = _Key; + using key_compare = _Compare; + using value_compare = _Compare; + using reference = value_type&; + using const_reference = const value_type&; + using size_type = typename _KeyContainer::size_type; + using difference_type = typename _KeyContainer::difference_type; + using iterator = typename _KeyContainer::const_iterator; + using const_iterator = typename _KeyContainer::const_iterator; + using reverse_iterator = std::reverse_iterator<iterator>; + using const_reverse_iterator = std::reverse_iterator<const_iterator>; + using container_type = _KeyContainer; + + private: + using __emplace_result_t = __conditional_t<_Multi, iterator, pair<iterator, bool>>; + + public: + // constructors + _Flat_set_impl() : _Flat_set_impl(key_compare()) { } + + explicit + _Flat_set_impl(const key_compare& __comp) + : _M_cont(), _M_comp(__comp) + { } + + _Flat_set_impl(container_type __cont, const key_compare& __comp = key_compare()) + : _M_cont(std::move(__cont)), _M_comp(__comp) + { _M_sort_uniq(); } + + _Flat_set_impl(__sorted_t, + container_type __cont, const key_compare& __comp = key_compare()) + : _M_cont(std::move(__cont)), _M_comp(__comp) + { } + + template<typename _InputIterator, + typename = _RequireInputIter<_InputIterator>> + _Flat_set_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_set_impl(__sorted_t __s, + _InputIterator __first, _InputIterator __last, + const key_compare& __comp = key_compare()) + : _M_cont(), _M_comp(__comp) + { insert(__s, __first, __last); } + + // TODO: Implement from_range_t constructors. + + _Flat_set_impl(initializer_list<value_type> __il, + const key_compare& __comp = key_compare()) + : _Flat_set_impl(__il.begin(), __il.end(), __comp) + { } + + _Flat_set_impl(__sorted_t __s, + initializer_list<value_type> __il, + const key_compare& __comp = key_compare()) + : _Flat_set_impl(__s, __il.begin(), __il.end(), __comp) + { } + + // constructors with allocators + + template<typename _Alloc> + explicit + _Flat_set_impl(const _Alloc& __a) + : _Flat_set_impl(key_compare(), __a) + { } + + template<typename _Alloc> + _Flat_set_impl(const key_compare& __comp, const _Alloc& __a) + : _M_cont(std::make_obj_using_allocator<container_type>(__a)), + _M_comp(__comp) + { } + + template<typename _Alloc> + _Flat_set_impl(const container_type& __cont, const _Alloc& __a) + : _Flat_set_impl(__cont, key_compare(), __a) + { } + + template<typename _Alloc> + _Flat_set_impl(const container_type& __cont, const key_compare& __comp, + const _Alloc& __a) + : _M_cont(std::make_obj_using_allocator<container_type>(__a, __cont)), + _M_comp(__comp) + { _M_sort_uniq(); } + + template<typename _Alloc> + _Flat_set_impl(__sorted_t __s, const container_type& __cont, const _Alloc& __a) + : _Flat_set_impl(__s, __cont, key_compare(), __a) + { } + + template<typename _Alloc> + _Flat_set_impl(__sorted_t __s, + const container_type& __cont, const key_compare& __comp, + const _Alloc& __a) + : _M_comp(__comp), + _M_cont(std::make_obj_using_allocator<container_type>(__a, __cont)) + { } + + template<typename _Alloc> + _Flat_set_impl(const _Derived& __x, const _Alloc& __a) + : _M_comp(__x._M_comp), + _M_cont(std::make_obj_using_allocator<container_type>(__a, + __x._M_cont)) + { } + + template<typename _Alloc> + _Flat_set_impl(_Derived&& __x, const _Alloc& __a) + : _M_comp(__x._M_comp), + _M_cont(std::make_obj_using_allocator<container_type>(__a, std::move(__x._M_cont))) + { } + + template<typename _InputIterator, typename _Alloc, + typename = _RequireInputIter<_InputIterator>> + _Flat_set_impl(_InputIterator __first, _InputIterator __last, + const _Alloc& __a) + : _Flat_set_impl(std::move(__first), std::move(__last), key_compare(), __a) + { } + + template<typename _InputIterator, typename _Alloc, + typename = _RequireInputIter<_InputIterator>> + _Flat_set_impl(_InputIterator __first, _InputIterator __last, + const key_compare& __comp, + const _Alloc& __a) + : _Flat_set_impl(__comp, __a) + { insert(__first, __last); } + + template<typename _InputIterator, typename _Alloc, + typename = _RequireInputIter<_InputIterator>> + _Flat_set_impl(__sorted_t __s, + _InputIterator __first, _InputIterator __last, + const _Alloc& __a) + : _Flat_set_impl(__s, std::move(__first), std::move(__last), key_compare(), __a) + { } + + template<typename _InputIterator, typename _Alloc, + typename = _RequireInputIter<_InputIterator>> + _Flat_set_impl(__sorted_t __s, + _InputIterator __first, _InputIterator __last, + const key_compare& __comp, + const _Alloc& __a) + : _Flat_set_impl(__comp, __a) + { insert(__s, __first, __last); } + + // TODO: Implement allocator-aware from_range_t constructors. + + template<typename _Alloc> + _Flat_set_impl(initializer_list<value_type> __il, + const _Alloc& __a) + : _Flat_set_impl(__il, key_compare(), __a) + { } + + template<typename _Alloc> + _Flat_set_impl(initializer_list<value_type> __il, + const key_compare& __comp, + const _Alloc& __a) + : _Flat_set_impl(__il.begin(), __il.end(), __comp, __a) + { } + + template<typename _Alloc> + _Flat_set_impl(__sorted_t __s, + initializer_list<value_type> __il, + const _Alloc& __a) + : _Flat_set_impl(__s, __il.begin(), __il.end(), key_compare(), __a) + { } + + template<typename _Alloc> + _Flat_set_impl(__sorted_t __s, + initializer_list<value_type> __il, + const key_compare& __comp, + const _Alloc& __a) + : _Flat_set_impl(__s, __il.begin(), __il.end(), __comp, __a) + { } + + _Derived& + operator=(initializer_list<value_type> __il) + { + clear(); + insert(__il); + return static_cast<_Derived&>(*this); + } + + // iterators + const_iterator + begin() const noexcept + { return _M_cont.begin(); } + + const_iterator + end() const noexcept + { return _M_cont.end(); } + + const_reverse_iterator + rbegin() const noexcept + { return const_reverse_iterator(end()); } + + const_reverse_iterator + rend() const noexcept + { return const_reverse_iterator(begin()); } + + const_iterator + cbegin() const noexcept + { return begin(); } + + const_iterator + cend() const noexcept + { return end(); } + + const_reverse_iterator + crbegin() const noexcept + { return rbegin(); } + + const_reverse_iterator + crend() const noexcept + { return rend(); } + + // capacity + [[nodiscard]] bool + empty() const noexcept + { return _M_cont.empty(); } + + size_type + size() const noexcept + { return _M_cont.size(); } + + size_type + max_size() const noexcept + { return _M_cont.max_size(); } + + // modifiers + template<typename... _Args> + pair<iterator, bool> + _M_try_emplace(optional<const_iterator> __hint, _Args&&... __args) + { + // TODO: Simplify and audit the hint handling. + value_type __k(std::forward<_Args>(__args)...); + typename container_type::iterator __it; + int __r = -1, __s = -1; + if (__hint.has_value() + && (__hint == cbegin() + || (__r = !_M_comp(__k, (*__hint)[-1]))) // k >= hint[-1] + && (__hint == cend() + || (__s = !_M_comp((*__hint)[0], __k)))) // k <= hint[0] + { + __it = _M_cont.begin() + (*__hint - begin()); + if constexpr (!_Multi) + if (__r == 1 && !_M_comp(__it[-1], __k)) // k == hint[-1] + return {__it - 1, false}; + } + else + { + auto __first = _M_cont.begin(); + auto __last = _M_cont.end(); + if (__r == 1) // k >= hint[-1] + __first += *__hint - _M_cont.begin(); + else if (__r == 0) // k < __hint[-1] + __last = __first + (*__hint - _M_cont.begin()); + if constexpr (_Multi) + { + if (__s == 0) // hint[0] < k + // Insert before the leftmost equivalent key. + __it = std::lower_bound(__first, __last, __k, _M_comp); + else + // Insert after the rightmost equivalent key. + __it = std::upper_bound(std::make_reverse_iterator(__last), + std::make_reverse_iterator(__first), + __k, std::not_fn(_M_comp)).base(); + } + else + __it = std::lower_bound(__first, __last, __k, _M_comp); + } + + if constexpr (!_Multi) + if (__it != _M_cont.end() && !_M_comp(__k, __it[0])) + return {__it, false}; + + __it = _M_cont.insert(__it, std::move(__k)); + return {__it, true}; + } + + template<typename... _Args> + requires is_constructible_v<value_type, _Args...> + __emplace_result_t + emplace(_Args&&... __args) + { + auto __r = _M_try_emplace(nullopt, std::forward<_Args>(__args)...); + if constexpr (_Multi) + return __r.first; + else + return __r; + } + + template<typename... _Args> + iterator + emplace_hint(const_iterator __position, _Args&&... __args) + { return _M_try_emplace(__position, std::forward<_Args>(__args)...).first; } + + __emplace_result_t + insert(const value_type& __x) + { return emplace(__x); } + + __emplace_result_t + insert(value_type&& __x) + { return emplace(std::move(__x)); } + + iterator + insert(const_iterator __position, const value_type& __x) + { return emplace_hint(__position, __x); } + + iterator + insert(const_iterator __position, value_type&& __x) + { return emplace_hint(__position, std::move(__x)); } + + template<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) + { + auto __it = _M_cont.insert(_M_cont.end(), __first, __last); + std::sort(__it, _M_cont.end(), _M_comp); + std::inplace_merge(_M_cont.begin(), __it, _M_cont.end(), _M_comp); + if constexpr (!_Multi) + _M_unique(); + } + + template<typename _InputIterator, typename = _RequireInputIter<_InputIterator>> + void + insert(__sorted_t, _InputIterator __first, _InputIterator __last) + { + auto __it = _M_cont.insert(_M_cont.end(), __first, __last); + std::inplace_merge(_M_cont.begin(), __it, _M_cont.end(), _M_comp); + if constexpr (!_Multi) + _M_unique(); + } + + // 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()); } + + container_type + extract() && + { + struct _Guard + { + _Guard(_Flat_set_impl* __m) : _M_m(__m) { } + + ~_Guard() { _M_m->clear(); } + + _Flat_set_impl* _M_m; + } __clear_guard = {this}; + return std::move(_M_cont); + } + + void + replace(container_type&& __cont) + { + __try + { + _M_cont = std::move(__cont); + } + __catch(...) + { + clear(); + __throw_exception_again; + } + } + + iterator + erase(const_iterator __position) + { return _M_cont.erase(__position); } + + size_type + erase(const key_type& __x) + { return erase<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) + { return _M_cont.erase(__first, __last); } + + void + swap(_Derived& __x) noexcept + { + using std::swap; + swap(_M_cont, __x._M_cont); + swap(_M_comp, __x._M_comp); + } + + void + clear() noexcept + { _M_cont.clear(); } + + // observers + key_compare + key_comp() const + { return _M_comp; } + + value_compare + value_comp() const + { return _M_comp; } + + // map operations + iterator + find(const key_type& __x) + { return find<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)) + 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)) + 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) + { return std::lower_bound(begin(), end(), __x, _M_comp); } + + template<typename _Key2> + requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> + const_iterator + lower_bound(const _Key2& __x) const + { return std::lower_bound(begin(), end(), __x, _M_comp); } + + iterator + upper_bound(const key_type& __x) + { return upper_bound<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) + { return std::upper_bound(begin(), end(), __x, _M_comp); } + + template<typename _Key2> + requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> + const_iterator + upper_bound(const _Key2& __x) const + { return std::upper_bound(begin(), end(), __x, _M_comp); } + + pair<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) + { return std::equal_range(begin(), end(), __x, _M_comp); } + + template<typename _Key2> + requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> + pair<const_iterator, const_iterator> + equal_range(const _Key2& __x) const + { return std::equal_range(begin(), end(), __x, _M_comp); } + + friend bool + operator==(const _Derived& __x, const _Derived& __y) + { return 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) + { + auto __first = __c._M_cont.begin(); + auto __last = __c._M_cont.end(); + __first = std::remove_if(__first, __last, __pred); + auto __n = __last - __first; + __c.erase(__first, __last); + return __n; + } + + private: + container_type _M_cont; + [[no_unique_address]] _Compare _M_comp; + + void + _M_sort_uniq() + { + std::sort(_M_cont.begin(), _M_cont.end(), _M_comp); + 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, __y) && !_M_comp(__y, __x); } + + [[no_unique_address]] key_compare _M_comp; + }; + + auto __first = _M_cont.begin(); + auto __last = _M_cont.end(); + __first = std::unique(__first, __last, __key_equiv(_M_comp)); + _M_cont.erase(__first, __last); + } + }; + + /* Class template flat_set - container adaptor + * + * @ingroup + */ + template<typename _Key, typename _Compare = less<_Key>, + typename _KeyContainer = vector<_Key>> + class flat_set + : private _Flat_set_impl<_Key, _Compare, _KeyContainer, false> + { + using _Impl = _Flat_set_impl<_Key, _Compare, _KeyContainer, false>; + friend _Impl; + + public: + // types + using typename _Impl::key_type; + using typename _Impl::value_type; + using typename _Impl::key_compare; + using typename _Impl::reference; + using typename _Impl::const_reference; + using typename _Impl::size_type; + using typename _Impl::difference_type; + using typename _Impl::iterator; + using typename _Impl::const_iterator; + using typename _Impl::reverse_iterator; + using typename _Impl::const_reverse_iterator; + using typename _Impl::container_type; + using typename _Impl::value_compare; + + // constructors + using _Impl::_Impl; + + // iterators + using _Impl::begin; + using _Impl::end; + using _Impl::rbegin; + using _Impl::rend; + + using _Impl::cbegin; + using _Impl::cend; + using _Impl::crbegin; + using _Impl::crend; + + // capacity + using _Impl::empty; + using _Impl::size; + using _Impl::max_size; + + // modifiers + using _Impl::emplace; + using _Impl::emplace_hint; + using _Impl::insert; + // using _Impl::insert_range; + using _Impl::extract; + using _Impl::replace; + using _Impl::erase; + using _Impl::swap; + using _Impl::clear; + + // observers + using _Impl::key_comp; + using _Impl::value_comp; + + // map operations + using _Impl::find; + using _Impl::count; + using _Impl::contains; + using _Impl::lower_bound; + using _Impl::upper_bound; + using _Impl::equal_range; + }; + + template<typename _KeyContainer, + typename _Compare = less<typename _KeyContainer::value_type>, + typename = _RequireNotAllocator<_Compare>> + flat_set(_KeyContainer, _Compare = _Compare()) + -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>; + + template<typename _KeyContainer, typename _Alloc, + typename = _RequireAllocator<_Alloc>> + flat_set(_KeyContainer, _Alloc) + -> flat_set<typename _KeyContainer::value_type, + less<typename _KeyContainer::value_type>, _KeyContainer>; + + template<typename _KeyContainer, typename _Compare, typename _Alloc, + typename = _RequireNotAllocator<_Compare>, + typename = _RequireAllocator<_Alloc>> + flat_set(_KeyContainer, _Compare, _Alloc) + -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>; + + template<typename _KeyContainer, + typename _Compare = less<typename _KeyContainer::value_type>, + typename = _RequireNotAllocator<_Compare>> + flat_set(sorted_unique_t, _KeyContainer, _Compare = _Compare()) + -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>; + + template<typename _KeyContainer, typename _Alloc, + typename = _RequireAllocator<_Alloc>> + flat_set(sorted_unique_t, _KeyContainer, _Alloc) + -> flat_set<typename _KeyContainer::value_type, + less<typename _KeyContainer::value_type>, _KeyContainer>; + + template<typename _KeyContainer, typename _Compare, typename _Alloc, + typename = _RequireNotAllocator<_Compare>, + typename = _RequireAllocator<_Alloc>> + flat_set(sorted_unique_t, _KeyContainer, _Compare, _Alloc) + -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>; + + template<typename _InputIterator, typename _Compare = less<__iter_key_t<_InputIterator>>, + typename = _RequireInputIter<_InputIterator>, + typename = _RequireNotAllocator<_Compare>> + flat_set(_InputIterator, _InputIterator, _Compare = _Compare()) + -> flat_set<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>; + + template<typename _InputIterator, typename _Compare = less<__iter_key_t<_InputIterator>>, + typename = _RequireInputIter<_InputIterator>, + typename = _RequireNotAllocator<_Compare>> + flat_set(sorted_unique_t, _InputIterator, _InputIterator, _Compare = _Compare()) + -> flat_set<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>; + + // TODO: Implement from_range_t deduction guides. + + template<typename _Key, typename _Compare = less<_Key>, + typename = _RequireNotAllocator<_Compare>> + flat_set(initializer_list<_Key>, _Compare = _Compare()) + -> flat_set<_Key, _Compare>; + + template<typename _Key, typename _Compare = less<_Key>, + typename = _RequireNotAllocator<_Compare>> + flat_set(sorted_unique_t, initializer_list<_Key>, _Compare = _Compare()) + -> flat_set<_Key, _Compare>; + + template<typename _Key, typename _Compare, + typename _KeyContainer, typename _Alloc> + struct uses_allocator<flat_set<_Key, _Compare, _KeyContainer>, _Alloc> + : bool_constant<uses_allocator_v<_KeyContainer, _Alloc>> + { }; + + /* Class template flat_multiset - container adaptor + * + * @ingroup + */ + template<typename _Key, typename _Compare = less<_Key>, + typename _KeyContainer = vector<_Key>> + class flat_multiset + : private _Flat_set_impl<_Key, _Compare, _KeyContainer, true> + { + using _Impl = _Flat_set_impl<_Key, _Compare, _KeyContainer, true>; + friend _Impl; + + public: + // types + using typename _Impl::key_type; + using typename _Impl::value_type; + using typename _Impl::key_compare; + using typename _Impl::reference; + using typename _Impl::const_reference; + using typename _Impl::size_type; + using typename _Impl::difference_type; + using typename _Impl::iterator; + using typename _Impl::const_iterator; + using typename _Impl::reverse_iterator; + using typename _Impl::const_reverse_iterator; + using typename _Impl::container_type; + using typename _Impl::value_compare; + + // constructors + using _Impl::_Impl; + + // iterators + using _Impl::begin; + using _Impl::end; + using _Impl::rbegin; + using _Impl::rend; + + using _Impl::cbegin; + using _Impl::cend; + using _Impl::crbegin; + using _Impl::crend; + + // capacity + using _Impl::empty; + using _Impl::size; + using _Impl::max_size; + + // modifiers + using _Impl::emplace; + using _Impl::emplace_hint; + using _Impl::insert; + // using _Impl::insert_range; + using _Impl::extract; + using _Impl::replace; + using _Impl::erase; + using _Impl::swap; + using _Impl::clear; + + // observers + using _Impl::key_comp; + using _Impl::value_comp; + + // map operations + using _Impl::find; + using _Impl::count; + using _Impl::contains; + using _Impl::lower_bound; + using _Impl::upper_bound; + using _Impl::equal_range; + }; + + template<typename _KeyContainer, + typename _Compare = less<typename _KeyContainer::value_type>, + typename = _RequireNotAllocator<_Compare>> + flat_multiset(_KeyContainer, _Compare = _Compare()) + -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>; + + template<typename _KeyContainer, typename _Alloc, + typename = _RequireAllocator<_Alloc>> + flat_multiset(_KeyContainer, _Alloc) + -> flat_multiset<typename _KeyContainer::value_type, + less<typename _KeyContainer::value_type>, _KeyContainer>; + + template<typename _KeyContainer, typename _Compare, typename _Alloc, + typename = _RequireNotAllocator<_Compare>, + typename = _RequireAllocator<_Alloc>> + flat_multiset(_KeyContainer, _Compare, _Alloc) + -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>; + + template<typename _KeyContainer, + typename _Compare = less<typename _KeyContainer::value_type>, + typename = _RequireNotAllocator<_Compare>> + flat_multiset(sorted_equivalent_t, _KeyContainer, _Compare = _Compare()) + -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>; + + template<typename _KeyContainer, typename _Alloc, + typename = _RequireAllocator<_Alloc>> + flat_multiset(sorted_equivalent_t, _KeyContainer, _Alloc) + -> flat_multiset<typename _KeyContainer::value_type, + less<typename _KeyContainer::value_type>, _KeyContainer>; + + template<typename _KeyContainer, typename _Compare, typename _Alloc, + typename = _RequireNotAllocator<_Compare>, + typename = _RequireAllocator<_Alloc>> + flat_multiset(sorted_equivalent_t, _KeyContainer, _Compare, _Alloc) + -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>; + + template<typename _InputIterator, typename _Compare = less<__iter_key_t<_InputIterator>>, + typename = _RequireInputIter<_InputIterator>, + typename = _RequireNotAllocator<_Compare>> + flat_multiset(_InputIterator, _InputIterator, _Compare = _Compare()) + -> flat_multiset<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>; + + template<typename _InputIterator, typename _Compare = less<__iter_key_t<_InputIterator>>, + typename = _RequireInputIter<_InputIterator>, + typename = _RequireNotAllocator<_Compare>> + flat_multiset(sorted_equivalent_t, _InputIterator, _InputIterator, _Compare = _Compare()) + -> flat_multiset<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>; + + // TODO: Implement from_range_t deduction guides. + + template<typename _Key, typename _Compare = less<_Key>, + typename = _RequireNotAllocator<_Compare>> + flat_multiset(initializer_list<_Key>, _Compare = _Compare()) + -> flat_multiset<_Key, _Compare>; + + template<typename _Key, typename _Compare = less<_Key>, + typename = _RequireNotAllocator<_Compare>> + flat_multiset(sorted_equivalent_t, initializer_list<_Key>, _Compare = _Compare()) + -> flat_multiset<_Key, _Compare>; + + template<typename _Key, typename _Compare, + typename _KeyContainer, typename _Alloc> + struct uses_allocator<flat_multiset<_Key, _Compare, _KeyContainer>, _Alloc> + : bool_constant<uses_allocator_v<_KeyContainer, _Alloc>> + { }; + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace std +#endif // __cpp_lib_flat_set +#endif // _GLIBCXX_FLAT_SET diff --git a/libstdc++-v3/testsuite/23_containers/flat_multiset/1.cc b/libstdc++-v3/testsuite/23_containers/flat_multiset/1.cc new file mode 100644 index 00000000000..af85b92e250 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/flat_multiset/1.cc @@ -0,0 +1,102 @@ +// { dg-do run { target c++23 } } + +#include <flat_set> +#include <deque> +#include <testsuite_hooks.h> + +template<template<class> class Sequence> +void +test01() +{ + std::flat_multiset<int, std::less<int>, Sequence<int>> m; + static_assert( std::ranges::random_access_range<decltype(m)> ); + + m.insert(1); + m.insert(2); + m.insert(3); + m.insert(1); + m.insert(2); + m.insert(3); + m.insert(0); + VERIFY( m.size() == 7 ); + VERIFY( std::ranges::equal(m, (int[]){0, 1, 1, 2, 2, 3, 3}) ); + + m.clear(); + m.insert(m.begin(), 0); + m.insert(m.begin(), 1); + m.insert(m.begin(), 2); + m.insert(m.begin(), 3); + m.insert(m.begin(), 1); + m.insert(m.begin(), 2); + m.insert(m.begin(), 3); + m.insert(m.begin(), 0); + VERIFY( std::ranges::equal(m, (int[]){0, 0, 1, 1, 2, 2, 3, 3}) ); + + m.clear(); + m = {10,10}; + VERIFY( m.size() == 2 ); + m.insert({11,12,11}); + VERIFY( m.size() == 5 ); +} + +void +test02() +{ + std::flat_multiset<int, std::greater<int>> m; + static_assert( std::ranges::random_access_range<decltype(m)> ); + + auto r = m.insert(1); + VERIFY( *r == 1 ); + r = m.insert(2); + VERIFY( *r == 2 ); + r = m.insert(3); + VERIFY( *r == 3 ); + r = m.insert(1); + VERIFY( *r == 1 ); + r = m.insert(2); + VERIFY( *r == 2 ); + r = m.insert(3); + VERIFY( *r == 3 ); + VERIFY( m.size() == 6 ); + VERIFY( std::ranges::equal(m, (int[]){3, 3, 2, 2, 1, 1}) ); + + VERIFY( m.contains(3) && !m.contains(7) ); + VERIFY( m.count(3) == 2 ); +} + +void +test03() +{ + std::flat_set<int> m; + m = {1, 3, 5}; + m.insert({7, 9}); + + auto it = m.find(0); + VERIFY( it == m.end() ); + it = m.find(9); + VERIFY( it == m.end()-1 ); + + 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, (int[]){3}) ); + VERIFY( m != n ); + VERIFY( n < m ); + + m = n; + erase_if(m, [](const auto& k) { return k < 5 || k > 5; }); + VERIFY( std::ranges::equal(m, (int[]){5}) ); +} + +int +main() +{ + test01<std::vector>(); + test01<std::deque>(); + test02(); + test03(); +} diff --git a/libstdc++-v3/testsuite/23_containers/flat_set/1.cc b/libstdc++-v3/testsuite/23_containers/flat_set/1.cc new file mode 100644 index 00000000000..d80def24005 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/flat_set/1.cc @@ -0,0 +1,111 @@ +// { dg-do run { target c++23 } } + +#include <flat_set> +#include <deque> +#include <testsuite_hooks.h> + +#if __cpp_lib_flat_set != 202207L +# error "Feature-test macro __cpp_lib_flat_set has wrong value in <flat_set>" +#endif + +template<template<class> class Sequence> +void +test01() +{ + std::flat_set<int, std::less<int>, Sequence<int>> m; + static_assert( std::ranges::random_access_range<decltype(m)> ); + + m.insert(1); + m.insert(2); + m.insert(3); + m.insert(1); + m.insert(2); + m.insert(3); + m.insert(0); + VERIFY( m.size() == 4 ); + VERIFY( std::ranges::equal(m, (int[]){0, 1, 2, 3}) ); + + for (int i = 0; i < 4; i++) + { + m.clear(); + m.insert(m.end(), 0); + m.insert(m.end(), 1); + m.insert(m.end(), 2); + m.insert(m.end(), 3); + m.insert(m.begin() + i, 1); + m.insert(m.begin() + i, 2); + m.insert(m.begin() + i, 3); + m.insert(m.begin() + i, 0); + VERIFY( std::ranges::equal(m, (int[]){0, 1, 2, 3}) ); + } + + m.clear(); + m = {10,10}; + VERIFY( m.size() == 1 ); + m.insert({11, 12, 11}); + VERIFY( m.size() == 3 ); + VERIFY( m.end()[-1] == 12 ); +} + +void +test02() +{ + std::flat_set<int, std::greater<int>> m; + static_assert( std::ranges::random_access_range<decltype(m)> ); + + auto r = m.insert(1); + VERIFY( *r.first == 1 && r.second ); + r = m.insert(2); + VERIFY( *r.first == 2 && r.second ); + r = m.insert(3); + VERIFY( *r.first == 3 && r.second ); + r = m.insert(1); + VERIFY( *r.first == 1 && !r.second ); + r = m.insert(2); + VERIFY( *r.first == 2 && !r.second ); + r = m.insert(3); + VERIFY( *r.first == 3 && !r.second ); + m.insert(0); + VERIFY( m.size() == 4 ); + VERIFY( std::ranges::equal(m, (int[]){3, 2, 1, 0}) ); + + VERIFY( m.contains(3) && !m.contains(7) ); + VERIFY( m.count(3) == 1 ); +} + +void +test03() +{ + std::flat_set<int> m; + m = {1, 3, 5}; + m.insert({7, 9}); + + auto it = m.find(0); + VERIFY( it == m.end() ); + it = m.find(9); + VERIFY( it == m.end()-1 ); + + 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, (int[]){3}) ); + VERIFY( m != n ); + VERIFY( n < m ); + + m = n; + erase_if(m, [](const auto& k) { return k < 5 || k > 5; }); + VERIFY( std::ranges::equal(m, (int[]){5}) ); +} + +int +main() +{ + test01<std::vector>(); + test01<std::deque>(); + test02(); + test03(); +}
diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am index 632bbafa63e..e49cdb23c55 100644 --- a/libstdc++-v3/include/Makefile.am +++ b/libstdc++-v3/include/Makefile.am @@ -71,6 +71,7 @@ std_headers = \ ${std_srcdir}/execution \ ${std_srcdir}/filesystem \ ${std_srcdir}/flat_map \ + ${std_srcdir}/flat_set \ ${std_srcdir}/format \ ${std_srcdir}/forward_list \ ${std_srcdir}/fstream \ diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in index 1ac963c4415..8e6ee44cc0e 100644 --- a/libstdc++-v3/include/Makefile.in +++ b/libstdc++-v3/include/Makefile.in @@ -427,6 +427,7 @@ std_freestanding = \ @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/execution \ @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/filesystem \ @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/flat_map \ +@GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/flat_set \ @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/format \ @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/forward_list \ @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/fstream \ diff --git a/libstdc++-v3/include/bits/version.def b/libstdc++-v3/include/bits/version.def index 631eca7beac..827582cf2ea 100644 --- a/libstdc++-v3/include/bits/version.def +++ b/libstdc++-v3/include/bits/version.def @@ -1666,6 +1666,14 @@ ftms = { }; }; +ftms = { + name = flat_set; + values = { + v = 202207; + cxxmin = 23; + }; +}; + ftms = { name = formatters; values = { diff --git a/libstdc++-v3/include/bits/version.h b/libstdc++-v3/include/bits/version.h index 1f3040fcbde..311586461e3 100644 --- a/libstdc++-v3/include/bits/version.h +++ b/libstdc++-v3/include/bits/version.h @@ -1840,6 +1840,16 @@ #endif /* !defined(__cpp_lib_flat_map) && defined(__glibcxx_want_flat_map) */ #undef __glibcxx_want_flat_map +#if !defined(__cpp_lib_flat_set) +# if (__cplusplus >= 202100L) +# define __glibcxx_flat_set 202207L +# if defined(__glibcxx_want_all) || defined(__glibcxx_want_flat_set) +# define __cpp_lib_flat_set 202207L +# endif +# endif +#endif /* !defined(__cpp_lib_flat_set) && defined(__glibcxx_want_flat_set) */ +#undef __glibcxx_want_flat_set + #if !defined(__cpp_lib_formatters) # if (__cplusplus >= 202100L) && _GLIBCXX_HOSTED # define __glibcxx_formatters 202302L diff --git a/libstdc++-v3/include/std/flat_set b/libstdc++-v3/include/std/flat_set new file mode 100644 index 00000000000..bbb63408cc2 --- /dev/null +++ b/libstdc++-v3/include/std/flat_set @@ -0,0 +1,968 @@ +// <flat_set> -*- 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_set + * This is a Standard C++ Library header. + */ + +#ifndef _GLIBCXX_FLAT_SET +#define _GLIBCXX_FLAT_SET 1 + +#ifdef _GLIBCXX_SYSHDR +#pragma GCC system_header +#endif + +#define __glibcxx_want_flat_set +#include <bits/version.h> + +#ifdef __cpp_lib_flat_set // >= 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 _Compare, + typename _KeyContainer> + class flat_set; + + template<typename _Key, typename _Compare, + typename _KeyContainer> + class flat_multiset; + + template<typename _Key, typename _Compare, typename _KeyContainer, bool _Multi> + class _Flat_set_impl + { + static_assert(is_same_v<_Key, typename _KeyContainer::value_type>); + static_assert(is_nothrow_swappable_v<_KeyContainer>); + + using _Derived = __conditional_t<_Multi, + flat_multiset<_Key, _Compare, _KeyContainer>, + flat_set<_Key, _Compare, _KeyContainer>>; + using __sorted_t = __conditional_t<_Multi, sorted_equivalent_t, sorted_unique_t>; + + public: + using key_type = _Key; + using value_type = _Key; + using key_compare = _Compare; + using value_compare = _Compare; + using reference = value_type&; + using const_reference = const value_type&; + using size_type = typename _KeyContainer::size_type; + using difference_type = typename _KeyContainer::difference_type; + using iterator = typename _KeyContainer::const_iterator; + using const_iterator = typename _KeyContainer::const_iterator; + using reverse_iterator = std::reverse_iterator<iterator>; + using const_reverse_iterator = std::reverse_iterator<const_iterator>; + using container_type = _KeyContainer; + + private: + using __emplace_result_t = __conditional_t<_Multi, iterator, pair<iterator, bool>>; + + public: + // constructors + _Flat_set_impl() : _Flat_set_impl(key_compare()) { } + + explicit + _Flat_set_impl(const key_compare& __comp) + : _M_cont(), _M_comp(__comp) + { } + + _Flat_set_impl(container_type __cont, const key_compare& __comp = key_compare()) + : _M_cont(std::move(__cont)), _M_comp(__comp) + { _M_sort_uniq(); } + + _Flat_set_impl(__sorted_t, + container_type __cont, const key_compare& __comp = key_compare()) + : _M_cont(std::move(__cont)), _M_comp(__comp) + { } + + template<typename _InputIterator, + typename = _RequireInputIter<_InputIterator>> + _Flat_set_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_set_impl(__sorted_t __s, + _InputIterator __first, _InputIterator __last, + const key_compare& __comp = key_compare()) + : _M_cont(), _M_comp(__comp) + { insert(__s, __first, __last); } + + // TODO: Implement from_range_t constructors. + + _Flat_set_impl(initializer_list<value_type> __il, + const key_compare& __comp = key_compare()) + : _Flat_set_impl(__il.begin(), __il.end(), __comp) + { } + + _Flat_set_impl(__sorted_t __s, + initializer_list<value_type> __il, + const key_compare& __comp = key_compare()) + : _Flat_set_impl(__s, __il.begin(), __il.end(), __comp) + { } + + // constructors with allocators + + template<typename _Alloc> + explicit + _Flat_set_impl(const _Alloc& __a) + : _Flat_set_impl(key_compare(), __a) + { } + + template<typename _Alloc> + _Flat_set_impl(const key_compare& __comp, const _Alloc& __a) + : _M_cont(std::make_obj_using_allocator<container_type>(__a)), + _M_comp(__comp) + { } + + template<typename _Alloc> + _Flat_set_impl(const container_type& __cont, const _Alloc& __a) + : _Flat_set_impl(__cont, key_compare(), __a) + { } + + template<typename _Alloc> + _Flat_set_impl(const container_type& __cont, const key_compare& __comp, + const _Alloc& __a) + : _M_cont(std::make_obj_using_allocator<container_type>(__a, __cont)), + _M_comp(__comp) + { _M_sort_uniq(); } + + template<typename _Alloc> + _Flat_set_impl(__sorted_t __s, const container_type& __cont, const _Alloc& __a) + : _Flat_set_impl(__s, __cont, key_compare(), __a) + { } + + template<typename _Alloc> + _Flat_set_impl(__sorted_t __s, + const container_type& __cont, const key_compare& __comp, + const _Alloc& __a) + : _M_comp(__comp), + _M_cont(std::make_obj_using_allocator<container_type>(__a, __cont)) + { } + + template<typename _Alloc> + _Flat_set_impl(const _Derived& __x, const _Alloc& __a) + : _M_comp(__x._M_comp), + _M_cont(std::make_obj_using_allocator<container_type>(__a, + __x._M_cont)) + { } + + template<typename _Alloc> + _Flat_set_impl(_Derived&& __x, const _Alloc& __a) + : _M_comp(__x._M_comp), + _M_cont(std::make_obj_using_allocator<container_type>(__a, std::move(__x._M_cont))) + { } + + template<typename _InputIterator, typename _Alloc, + typename = _RequireInputIter<_InputIterator>> + _Flat_set_impl(_InputIterator __first, _InputIterator __last, + const _Alloc& __a) + : _Flat_set_impl(std::move(__first), std::move(__last), key_compare(), __a) + { } + + template<typename _InputIterator, typename _Alloc, + typename = _RequireInputIter<_InputIterator>> + _Flat_set_impl(_InputIterator __first, _InputIterator __last, + const key_compare& __comp, + const _Alloc& __a) + : _Flat_set_impl(__comp, __a) + { insert(__first, __last); } + + template<typename _InputIterator, typename _Alloc, + typename = _RequireInputIter<_InputIterator>> + _Flat_set_impl(__sorted_t __s, + _InputIterator __first, _InputIterator __last, + const _Alloc& __a) + : _Flat_set_impl(__s, std::move(__first), std::move(__last), key_compare(), __a) + { } + + template<typename _InputIterator, typename _Alloc, + typename = _RequireInputIter<_InputIterator>> + _Flat_set_impl(__sorted_t __s, + _InputIterator __first, _InputIterator __last, + const key_compare& __comp, + const _Alloc& __a) + : _Flat_set_impl(__comp, __a) + { insert(__s, __first, __last); } + + // TODO: Implement allocator-aware from_range_t constructors. + + template<typename _Alloc> + _Flat_set_impl(initializer_list<value_type> __il, + const _Alloc& __a) + : _Flat_set_impl(__il, key_compare(), __a) + { } + + template<typename _Alloc> + _Flat_set_impl(initializer_list<value_type> __il, + const key_compare& __comp, + const _Alloc& __a) + : _Flat_set_impl(__il.begin(), __il.end(), __comp, __a) + { } + + template<typename _Alloc> + _Flat_set_impl(__sorted_t __s, + initializer_list<value_type> __il, + const _Alloc& __a) + : _Flat_set_impl(__s, __il.begin(), __il.end(), key_compare(), __a) + { } + + template<typename _Alloc> + _Flat_set_impl(__sorted_t __s, + initializer_list<value_type> __il, + const key_compare& __comp, + const _Alloc& __a) + : _Flat_set_impl(__s, __il.begin(), __il.end(), __comp, __a) + { } + + _Derived& + operator=(initializer_list<value_type> __il) + { + clear(); + insert(__il); + return static_cast<_Derived&>(*this); + } + + // iterators + const_iterator + begin() const noexcept + { return _M_cont.begin(); } + + const_iterator + end() const noexcept + { return _M_cont.end(); } + + const_reverse_iterator + rbegin() const noexcept + { return const_reverse_iterator(end()); } + + const_reverse_iterator + rend() const noexcept + { return const_reverse_iterator(begin()); } + + const_iterator + cbegin() const noexcept + { return begin(); } + + const_iterator + cend() const noexcept + { return end(); } + + const_reverse_iterator + crbegin() const noexcept + { return rbegin(); } + + const_reverse_iterator + crend() const noexcept + { return rend(); } + + // capacity + [[nodiscard]] bool + empty() const noexcept + { return _M_cont.empty(); } + + size_type + size() const noexcept + { return _M_cont.size(); } + + size_type + max_size() const noexcept + { return _M_cont.max_size(); } + + // modifiers + template<typename... _Args> + pair<iterator, bool> + _M_try_emplace(optional<const_iterator> __hint, _Args&&... __args) + { + // TODO: Simplify and audit the hint handling. + value_type __k(std::forward<_Args>(__args)...); + typename container_type::iterator __it; + int __r = -1, __s = -1; + if (__hint.has_value() + && (__hint == cbegin() + || (__r = !_M_comp(__k, (*__hint)[-1]))) // k >= hint[-1] + && (__hint == cend() + || (__s = !_M_comp((*__hint)[0], __k)))) // k <= hint[0] + { + __it = _M_cont.begin() + (*__hint - begin()); + if constexpr (!_Multi) + if (__r == 1 && !_M_comp(__it[-1], __k)) // k == hint[-1] + return {__it - 1, false}; + } + else + { + auto __first = _M_cont.begin(); + auto __last = _M_cont.end(); + if (__r == 1) // k >= hint[-1] + __first += *__hint - _M_cont.begin(); + else if (__r == 0) // k < __hint[-1] + __last = __first + (*__hint - _M_cont.begin()); + if constexpr (_Multi) + { + if (__s == 0) // hint[0] < k + // Insert before the leftmost equivalent key. + __it = std::lower_bound(__first, __last, __k, _M_comp); + else + // Insert after the rightmost equivalent key. + __it = std::upper_bound(std::make_reverse_iterator(__last), + std::make_reverse_iterator(__first), + __k, std::not_fn(_M_comp)).base(); + } + else + __it = std::lower_bound(__first, __last, __k, _M_comp); + } + + if constexpr (!_Multi) + if (__it != _M_cont.end() && !_M_comp(__k, __it[0])) + return {__it, false}; + + __it = _M_cont.insert(__it, std::move(__k)); + return {__it, true}; + } + + template<typename... _Args> + requires is_constructible_v<value_type, _Args...> + __emplace_result_t + emplace(_Args&&... __args) + { + auto __r = _M_try_emplace(nullopt, std::forward<_Args>(__args)...); + if constexpr (_Multi) + return __r.first; + else + return __r; + } + + template<typename... _Args> + iterator + emplace_hint(const_iterator __position, _Args&&... __args) + { return _M_try_emplace(__position, std::forward<_Args>(__args)...).first; } + + __emplace_result_t + insert(const value_type& __x) + { return emplace(__x); } + + __emplace_result_t + insert(value_type&& __x) + { return emplace(std::move(__x)); } + + iterator + insert(const_iterator __position, const value_type& __x) + { return emplace_hint(__position, __x); } + + iterator + insert(const_iterator __position, value_type&& __x) + { return emplace_hint(__position, std::move(__x)); } + + template<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) + { + auto __it = _M_cont.insert(_M_cont.end(), __first, __last); + std::sort(__it, _M_cont.end(), _M_comp); + std::inplace_merge(_M_cont.begin(), __it, _M_cont.end(), _M_comp); + _M_unique(); + } + + template<typename _InputIterator, typename = _RequireInputIter<_InputIterator>> + void + insert(__sorted_t, _InputIterator __first, _InputIterator __last) + { + auto __it = _M_cont.insert(_M_cont.end(), __first, __last); + std::inplace_merge(_M_cont.begin(), __it, _M_cont.end(), _M_comp); + _M_unique(); + } + + // TODO: Implement insert_range. + + void + insert(initializer_list<value_type> __il) + { insert(__il.begin(), __il.end()); } + + void + insert(__sorted_t __s, initializer_list<value_type> __il) + { insert(__s, __il.begin(), __il.end()); } + + container_type + extract() && + { + struct _Guard + { + _Guard(_Flat_set_impl* __m) : _M_m(__m) { } + + ~_Guard() { _M_m->clear(); } + + _Flat_set_impl* _M_m; + } __clear_guard = {this}; + return std::move(_M_cont); + } + + void + replace(container_type&& __cont) + { + __try + { + _M_cont = std::move(__cont); + } + __catch(...) + { + clear(); + __throw_exception_again; + } + } + + iterator + erase(const_iterator __position) + { return _M_cont.erase(__position); } + + size_type + erase(const key_type& __x) + { return erase<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) + { return _M_cont.erase(__first, __last); } + + void + swap(_Derived& __x) noexcept + { + using std::swap; + swap(_M_cont, __x._M_cont); + swap(_M_comp, __x._M_comp); + } + + void + clear() noexcept + { _M_cont.clear(); } + + // observers + key_compare + key_comp() const + { return _M_comp; } + + value_compare + value_comp() const + { return _M_comp; } + + // map operations + iterator + find(const key_type& __x) + { return find<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)) + 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)) + 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) + { return std::lower_bound(begin(), end(), __x, _M_comp); } + + template<typename _Key2> + requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> + const_iterator + lower_bound(const _Key2& __x) const + { return std::lower_bound(begin(), end(), __x, _M_comp); } + + iterator + upper_bound(const key_type& __x) + { return upper_bound<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) + { return std::upper_bound(begin(), end(), __x, _M_comp); } + + template<typename _Key2> + requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> + const_iterator + upper_bound(const _Key2& __x) const + { return std::upper_bound(begin(), end(), __x, _M_comp); } + + pair<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) + { return std::equal_range(begin(), end(), __x, _M_comp); } + + template<typename _Key2> + requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> + pair<const_iterator, const_iterator> + equal_range(const _Key2& __x) const + { return std::equal_range(begin(), end(), __x, _M_comp); } + + friend bool + operator==(const _Derived& __x, const _Derived& __y) + { return ranges::equal(__x, __y); } + + template<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) + { + auto [__first, __last] = ranges::remove_if(__c._M_cont, __pred); + auto __n = __last - __first; + __c.erase(__first, __last); + return __n; + } + + private: + container_type _M_cont; + [[no_unique_address]] _Compare _M_comp; + + void + _M_sort_uniq() + { + std::sort(_M_cont.begin(), _M_cont.end(), _M_comp); + _M_unique(); + } + + void + _M_unique() + { + if constexpr (!_Multi) + { + struct __key_equiv + { + __key_equiv(key_compare __c) : _M_comp(__c) { } + + bool + operator()(const_reference __x, const_reference __y) const + { return !_M_comp(__x, __y) && !_M_comp(__y, __x); } + + [[no_unique_address]] key_compare _M_comp; + }; + + auto [__first, __last] = ranges::unique(_M_cont, __key_equiv(_M_comp)); + _M_cont.erase(__first, __last); + } + } + }; + + /* Class template flat_set - container adaptor + * + * @ingroup + */ + template<typename _Key, typename _Compare = less<_Key>, + typename _KeyContainer = vector<_Key>> + class flat_set + : private _Flat_set_impl<_Key, _Compare, _KeyContainer, false> + { + using _Impl = _Flat_set_impl<_Key, _Compare, _KeyContainer, false>; + friend _Impl; + + public: + // types + using typename _Impl::key_type; + using typename _Impl::value_type; + using typename _Impl::key_compare; + using typename _Impl::reference; + using typename _Impl::const_reference; + using typename _Impl::size_type; + using typename _Impl::difference_type; + using typename _Impl::iterator; + using typename _Impl::const_iterator; + using typename _Impl::reverse_iterator; + using typename _Impl::const_reverse_iterator; + using typename _Impl::container_type; + using typename _Impl::value_compare; + + // constructors + using _Impl::_Impl; + + // iterators + using _Impl::begin; + using _Impl::end; + using _Impl::rbegin; + using _Impl::rend; + + using _Impl::cbegin; + using _Impl::cend; + using _Impl::crbegin; + using _Impl::crend; + + // capacity + using _Impl::empty; + using _Impl::size; + using _Impl::max_size; + + // modifiers + using _Impl::emplace; + using _Impl::emplace_hint; + using _Impl::insert; + // using _Impl::insert_range; + using _Impl::extract; + using _Impl::replace; + using _Impl::erase; + using _Impl::swap; + using _Impl::clear; + + // observers + using _Impl::key_comp; + using _Impl::value_comp; + + // map operations + using _Impl::find; + using _Impl::count; + using _Impl::contains; + using _Impl::lower_bound; + using _Impl::upper_bound; + using _Impl::equal_range; + }; + + template<typename _KeyContainer, + typename _Compare = less<typename _KeyContainer::value_type>, + typename = _RequireNotAllocator<_Compare>> + flat_set(_KeyContainer, _Compare = _Compare()) + -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>; + + template<typename _KeyContainer, typename _Alloc, + typename = _RequireAllocator<_Alloc>> + flat_set(_KeyContainer, _Alloc) + -> flat_set<typename _KeyContainer::value_type, + less<typename _KeyContainer::value_type>, _KeyContainer>; + + template<typename _KeyContainer, typename _Compare, typename _Alloc, + typename = _RequireNotAllocator<_Compare>, + typename = _RequireAllocator<_Alloc>> + flat_set(_KeyContainer, _Compare, _Alloc) + -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>; + + template<typename _KeyContainer, + typename _Compare = less<typename _KeyContainer::value_type>, + typename = _RequireNotAllocator<_Compare>> + flat_set(sorted_unique_t, _KeyContainer, _Compare = _Compare()) + -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>; + + template<typename _KeyContainer, typename _Alloc, + typename = _RequireAllocator<_Alloc>> + flat_set(sorted_unique_t, _KeyContainer, _Alloc) + -> flat_set<typename _KeyContainer::value_type, + less<typename _KeyContainer::value_type>, _KeyContainer>; + + template<typename _KeyContainer, typename _Compare, typename _Alloc, + typename = _RequireNotAllocator<_Compare>, + typename = _RequireAllocator<_Alloc>> + flat_set(sorted_unique_t, _KeyContainer, _Compare, _Alloc) + -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>; + + template<typename _InputIterator, typename _Compare = less<__iter_key_t<_InputIterator>>, + typename = _RequireInputIter<_InputIterator>, + typename = _RequireNotAllocator<_Compare>> + flat_set(_InputIterator, _InputIterator, _Compare = _Compare()) + -> flat_set<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>; + + template<typename _InputIterator, typename _Compare = less<__iter_key_t<_InputIterator>>, + typename = _RequireInputIter<_InputIterator>, + typename = _RequireNotAllocator<_Compare>> + flat_set(sorted_unique_t, _InputIterator, _InputIterator, _Compare = _Compare()) + -> flat_set<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>; + + // TODO: Implement from_range_t deduction guides. + + template<typename _Key, typename _Compare = less<_Key>, + typename = _RequireNotAllocator<_Compare>> + flat_set(initializer_list<_Key>, _Compare = _Compare()) + -> flat_set<_Key, _Compare>; + + template<typename _Key, typename _Compare = less<_Key>, + typename = _RequireNotAllocator<_Compare>> + flat_set(sorted_unique_t, initializer_list<_Key>, _Compare = _Compare()) + -> flat_set<_Key, _Compare>; + + template<typename _Key, typename _Compare, + typename _KeyContainer, typename _Alloc> + struct uses_allocator<flat_set<_Key, _Compare, _KeyContainer>, _Alloc> + : bool_constant<uses_allocator_v<_KeyContainer, _Alloc>> + { }; + + /* Class template flat_multiset - container adaptor + * + * @ingroup + */ + template<typename _Key, typename _Compare = less<_Key>, + typename _KeyContainer = vector<_Key>> + class flat_multiset + : private _Flat_set_impl<_Key, _Compare, _KeyContainer, true> + { + using _Impl = _Flat_set_impl<_Key, _Compare, _KeyContainer, true>; + friend _Impl; + + public: + // types + using typename _Impl::key_type; + using typename _Impl::value_type; + using typename _Impl::key_compare; + using typename _Impl::reference; + using typename _Impl::const_reference; + using typename _Impl::size_type; + using typename _Impl::difference_type; + using typename _Impl::iterator; + using typename _Impl::const_iterator; + using typename _Impl::reverse_iterator; + using typename _Impl::const_reverse_iterator; + using typename _Impl::container_type; + using typename _Impl::value_compare; + + // constructors + using _Impl::_Impl; + + // iterators + using _Impl::begin; + using _Impl::end; + using _Impl::rbegin; + using _Impl::rend; + + using _Impl::cbegin; + using _Impl::cend; + using _Impl::crbegin; + using _Impl::crend; + + // capacity + using _Impl::empty; + using _Impl::size; + using _Impl::max_size; + + // modifiers + using _Impl::emplace; + using _Impl::emplace_hint; + using _Impl::insert; + // using _Impl::insert_range; + using _Impl::extract; + using _Impl::replace; + using _Impl::erase; + using _Impl::swap; + using _Impl::clear; + + // observers + using _Impl::key_comp; + using _Impl::value_comp; + + // map operations + using _Impl::find; + using _Impl::count; + using _Impl::contains; + using _Impl::lower_bound; + using _Impl::upper_bound; + using _Impl::equal_range; + }; + + template<typename _KeyContainer, + typename _Compare = less<typename _KeyContainer::value_type>, + typename = _RequireNotAllocator<_Compare>> + flat_multiset(_KeyContainer, _Compare = _Compare()) + -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>; + + template<typename _KeyContainer, typename _Alloc, + typename = _RequireAllocator<_Alloc>> + flat_multiset(_KeyContainer, _Alloc) + -> flat_multiset<typename _KeyContainer::value_type, + less<typename _KeyContainer::value_type>, _KeyContainer>; + + template<typename _KeyContainer, typename _Compare, typename _Alloc, + typename = _RequireNotAllocator<_Compare>, + typename = _RequireAllocator<_Alloc>> + flat_multiset(_KeyContainer, _Compare, _Alloc) + -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>; + + template<typename _KeyContainer, + typename _Compare = less<typename _KeyContainer::value_type>, + typename = _RequireNotAllocator<_Compare>> + flat_multiset(sorted_equivalent_t, _KeyContainer, _Compare = _Compare()) + -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>; + + template<typename _KeyContainer, typename _Alloc, + typename = _RequireAllocator<_Alloc>> + flat_multiset(sorted_equivalent_t, _KeyContainer, _Alloc) + -> flat_multiset<typename _KeyContainer::value_type, + less<typename _KeyContainer::value_type>, _KeyContainer>; + + template<typename _KeyContainer, typename _Compare, typename _Alloc, + typename = _RequireNotAllocator<_Compare>, + typename = _RequireAllocator<_Alloc>> + flat_multiset(sorted_equivalent_t, _KeyContainer, _Compare, _Alloc) + -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>; + + template<typename _InputIterator, typename _Compare = less<__iter_key_t<_InputIterator>>, + typename = _RequireInputIter<_InputIterator>, + typename = _RequireNotAllocator<_Compare>> + flat_multiset(_InputIterator, _InputIterator, _Compare = _Compare()) + -> flat_multiset<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>; + + template<typename _InputIterator, typename _Compare = less<__iter_key_t<_InputIterator>>, + typename = _RequireInputIter<_InputIterator>, + typename = _RequireNotAllocator<_Compare>> + flat_multiset(sorted_equivalent_t, _InputIterator, _InputIterator, _Compare = _Compare()) + -> flat_multiset<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>; + + // TODO: Implement from_range_t deduction guides. + + template<typename _Key, typename _Compare = less<_Key>, + typename = _RequireNotAllocator<_Compare>> + flat_multiset(initializer_list<_Key>, _Compare = _Compare()) + -> flat_multiset<_Key, _Compare>; + + template<typename _Key, typename _Compare = less<_Key>, + typename = _RequireNotAllocator<_Compare>> + flat_multiset(sorted_equivalent_t, initializer_list<_Key>, _Compare = _Compare()) + -> flat_multiset<_Key, _Compare>; + + template<typename _Key, typename _Compare, + typename _KeyContainer, typename _Alloc> + struct uses_allocator<flat_multiset<_Key, _Compare, _KeyContainer>, _Alloc> + : bool_constant<uses_allocator_v<_KeyContainer, _Alloc>> + { }; + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace std +#endif // __cpp_lib_flat_set +#endif // _GLIBCXX_FLAT_SET diff --git a/libstdc++-v3/testsuite/23_containers/flat_multiset/1.cc b/libstdc++-v3/testsuite/23_containers/flat_multiset/1.cc new file mode 100644 index 00000000000..97368cc5609 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/flat_multiset/1.cc @@ -0,0 +1,73 @@ +// { dg-do run { target c++23 } } + +#include <flat_set> +#include <deque> +#include <testsuite_hooks.h> + +template<template<class> class Sequence> +void +test01() +{ + std::flat_multiset<int, std::less<int>, Sequence<int>> m; + static_assert( std::ranges::random_access_range<decltype(m)> ); + + m.insert(1); + m.insert(2); + m.insert(3); + m.insert(1); + m.insert(2); + m.insert(3); + m.insert(0); + VERIFY( m.size() == 7 ); + VERIFY( std::ranges::equal(m, (int[]){0, 1, 1, 2, 2, 3, 3}) ); + + m.clear(); + m.insert(m.begin(), 0); + m.insert(m.begin(), 1); + m.insert(m.begin(), 2); + m.insert(m.begin(), 3); + m.insert(m.begin(), 1); + m.insert(m.begin(), 2); + m.insert(m.begin(), 3); + m.insert(m.begin(), 0); + VERIFY( std::ranges::equal(m, (int[]){0, 0, 1, 1, 2, 2, 3, 3}) ); + + m.clear(); + m = {10,10}; + VERIFY( m.size() == 2 ); + m.insert({11,12,11}); + VERIFY( m.size() == 5 ); +} + +void +test02() +{ + std::flat_multiset<int, std::greater<int>> m; + static_assert( std::ranges::random_access_range<decltype(m)> ); + + auto r = m.insert(1); + VERIFY( *r == 1 ); + r = m.insert(2); + VERIFY( *r == 2 ); + r = m.insert(3); + VERIFY( *r == 3 ); + r = m.insert(1); + VERIFY( *r == 1 ); + r = m.insert(2); + VERIFY( *r == 2 ); + r = m.insert(3); + VERIFY( *r == 3 ); + VERIFY( m.size() == 6 ); + VERIFY( std::ranges::equal(m, (int[]){3, 3, 2, 2, 1, 1}) ); + + VERIFY( m.contains(3) && !m.contains(7) ); + VERIFY( m.count(3) == 2 ); +} + +int +main() +{ + test01<std::vector>(); + test01<std::deque>(); + test02(); +} diff --git a/libstdc++-v3/testsuite/23_containers/flat_set/1.cc b/libstdc++-v3/testsuite/23_containers/flat_set/1.cc new file mode 100644 index 00000000000..dd52f5de80b --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/flat_set/1.cc @@ -0,0 +1,78 @@ +// { dg-do run { target c++23 } } + +#include <flat_set> +#include <deque> +#include <testsuite_hooks.h> + +template<template<class> class Sequence> +void +test01() +{ + std::flat_set<int, std::less<int>, Sequence<int>> m; + static_assert( std::ranges::random_access_range<decltype(m)> ); + + m.insert(1); + m.insert(2); + m.insert(3); + m.insert(1); + m.insert(2); + m.insert(3); + m.insert(0); + VERIFY( m.size() == 4 ); + VERIFY( std::ranges::equal(m, (int[]){0, 1, 2, 3}) ); + + for (int i = 0; i < 4; i++) + { + m.clear(); + m.insert(m.end(), 0); + m.insert(m.end(), 1); + m.insert(m.end(), 2); + m.insert(m.end(), 3); + m.insert(m.begin() + i, 1); + m.insert(m.begin() + i, 2); + m.insert(m.begin() + i, 3); + m.insert(m.begin() + i, 0); + VERIFY( std::ranges::equal(m, (int[]){0, 1, 2, 3}) ); + } + + m.clear(); + m = {10,10}; + VERIFY( m.size() == 1 ); + m.insert({11, 12, 11}); + VERIFY( m.size() == 3 ); + VERIFY( m.end()[-1] == 12 ); +} + +void +test02() +{ + std::flat_set<int, std::greater<int>> m; + static_assert( std::ranges::random_access_range<decltype(m)> ); + + auto r = m.insert(1); + VERIFY( *r.first == 1 && r.second ); + r = m.insert(2); + VERIFY( *r.first == 2 && r.second ); + r = m.insert(3); + VERIFY( *r.first == 3 && r.second ); + r = m.insert(1); + VERIFY( *r.first == 1 && !r.second ); + r = m.insert(2); + VERIFY( *r.first == 2 && !r.second ); + r = m.insert(3); + VERIFY( *r.first == 3 && !r.second ); + m.insert(0); + VERIFY( m.size() == 4 ); + VERIFY( std::ranges::equal(m, (int[]){3, 2, 1, 0}) ); + + VERIFY( m.contains(3) && !m.contains(7) ); + VERIFY( m.count(3) == 1 ); +} + +int +main() +{ + test01<std::vector>(); + test01<std::deque>(); + test02(); +}
This implements the C++23 container adaptors std::flat_set and std::flat_multiset from P1222R4. The implementation is essentially an simpler and pared down version of std::flat_map. The main known issues are: * exception safety is likely incomplete/buggy * unimplemented from_range_t constructors and insert_range function * the main worthouse function _M_try_emplace is probably buggy wrt its handling of the hint parameter and could be simplified * more extensive testcases are a WIP libstdc++-v3/ChangeLog: * include/Makefile.am: Add new header <flat_set>. * include/Makefile.in: Regenerate. * include/bits/version.def (__cpp_flat_set): Define. * include/bits/version.h: Regenerate * include/std/flat_set: New file. * testsuite/23_containers/flat_multiset/1.cc: New test. * testsuite/23_containers/flat_set/1.cc: New test. --- libstdc++-v3/include/Makefile.am | 1 + libstdc++-v3/include/Makefile.in | 1 + libstdc++-v3/include/bits/version.def | 8 + libstdc++-v3/include/bits/version.h | 10 + libstdc++-v3/include/std/flat_set | 968 ++++++++++++++++++ .../23_containers/flat_multiset/1.cc | 73 ++ .../testsuite/23_containers/flat_set/1.cc | 78 ++ 7 files changed, 1139 insertions(+) create mode 100644 libstdc++-v3/include/std/flat_set create mode 100644 libstdc++-v3/testsuite/23_containers/flat_multiset/1.cc create mode 100644 libstdc++-v3/testsuite/23_containers/flat_set/1.cc