Hello world, This patch adds constexpr support to flat_map and flat_multiset in accordance with P3372R3. I have also added test cases to verify the new constexpr functionality. Tested on x86_64-linux. Please take a look when you have time. Thanks!
Yuao
From 45df14aa6d639c8ce20b742eb43e6725aa575058 Mon Sep 17 00:00:00 2001 From: Yuao Ma <[email protected]> Date: Wed, 26 Nov 2025 22:04:46 +0800 Subject: [PATCH] libstdc++: constexpr flat_set and flat_multiset This patch makes flat_map and flat_multiset constexpr as part of P3372R3. libstdc++-v3/ChangeLog: * include/bits/version.def: Add FTM. * include/bits/version.h: Regenerate. * include/std/flat_set: Add constexpr. * testsuite/23_containers/flat_multiset/constexpr.cc: New test. * testsuite/23_containers/flat_set/constexpr.cc: New test. --- libstdc++-v3/include/bits/version.def | 9 + libstdc++-v3/include/bits/version.h | 10 + libstdc++-v3/include/std/flat_set | 103 ++++++- .../23_containers/flat_multiset/constexpr.cc | 239 +++++++++++++++++ .../23_containers/flat_set/constexpr.cc | 253 ++++++++++++++++++ 5 files changed, 611 insertions(+), 3 deletions(-) create mode 100644 libstdc++-v3/testsuite/23_containers/flat_multiset/constexpr.cc create mode 100644 libstdc++-v3/testsuite/23_containers/flat_set/constexpr.cc diff --git a/libstdc++-v3/include/bits/version.def b/libstdc++-v3/include/bits/version.def index 1fde9eef9d3..93965e914d5 100644 --- a/libstdc++-v3/include/bits/version.def +++ b/libstdc++-v3/include/bits/version.def @@ -1347,6 +1347,15 @@ ftms = { }; }; +ftms = { + name = constexpr_flat_set; + values = { + v = 202502; + cxxmin = 26; + hosted = yes; + }; +}; + ftms = { name = constexpr_string; values = { diff --git a/libstdc++-v3/include/bits/version.h b/libstdc++-v3/include/bits/version.h index 2ebc48b234b..dce8351b7d6 100644 --- a/libstdc++-v3/include/bits/version.h +++ b/libstdc++-v3/include/bits/version.h @@ -1495,6 +1495,16 @@ #endif /* !defined(__cpp_lib_constexpr_dynamic_alloc) */ #undef __glibcxx_want_constexpr_dynamic_alloc +#if !defined(__cpp_lib_constexpr_flat_set) +# if (__cplusplus > 202302L) && _GLIBCXX_HOSTED +# define __glibcxx_constexpr_flat_set 202502L +# if defined(__glibcxx_want_all) || defined(__glibcxx_want_constexpr_flat_set) +# define __cpp_lib_constexpr_flat_set 202502L +# endif +# endif +#endif /* !defined(__cpp_lib_constexpr_flat_set) */ +#undef __glibcxx_want_constexpr_flat_set + #if !defined(__cpp_lib_constexpr_string) # if (__cplusplus >= 202002L) && _GLIBCXX_USE_CXX11_ABI && _GLIBCXX_HOSTED && (defined(__glibcxx_is_constant_evaluated)) # define __glibcxx_constexpr_string 201907L diff --git a/libstdc++-v3/include/std/flat_set b/libstdc++-v3/include/std/flat_set index c48340d7980..3a1f5ba10da 100644 --- a/libstdc++-v3/include/std/flat_set +++ b/libstdc++-v3/include/std/flat_set @@ -33,6 +33,7 @@ #pragma GCC system_header #endif +#define __glibcxx_want_constexpr_flat_set #define __glibcxx_want_flat_set #include <bits/version.h> @@ -100,50 +101,60 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { container_type* _M_cont; + _GLIBCXX26_CONSTEXPR _ClearGuard(container_type& __cont) : _M_cont(std::__addressof(__cont)) { } + _GLIBCXX26_CONSTEXPR ~_ClearGuard() { if (_M_cont) _M_cont->clear(); } + _GLIBCXX26_CONSTEXPR void _M_disable() { _M_cont = nullptr; } }; + _GLIBCXX26_CONSTEXPR _ClearGuard _M_make_clear_guard() { return _ClearGuard{this->_M_cont}; } public: // constructors + _GLIBCXX26_CONSTEXPR _Flat_set_impl() : _Flat_set_impl(key_compare()) { } + _GLIBCXX26_CONSTEXPR explicit _Flat_set_impl(const key_compare& __comp) : _M_cont(), _M_comp(__comp) { } + _GLIBCXX26_CONSTEXPR _Flat_set_impl(container_type __cont, const key_compare& __comp = key_compare()) : _M_cont(std::move(__cont)), _M_comp(__comp) { _M_sort_uniq(); } + _GLIBCXX26_CONSTEXPR _Flat_set_impl(__sorted_t, container_type __cont, const key_compare& __comp = key_compare()) : _M_cont(std::move(__cont)), _M_comp(__comp) { _GLIBCXX_DEBUG_ASSERT(ranges::is_sorted(_M_cont, _M_comp)); } template<__has_input_iter_cat _InputIterator> + _GLIBCXX26_CONSTEXPR _Flat_set_impl(_InputIterator __first, _InputIterator __last, const key_compare& __comp = key_compare()) : _M_cont(), _M_comp(__comp) { insert(__first, __last); } template<__has_input_iter_cat _InputIterator> + _GLIBCXX26_CONSTEXPR _Flat_set_impl(__sorted_t __s, _InputIterator __first, _InputIterator __last, const key_compare& __comp = key_compare()) @@ -151,20 +162,24 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { insert(__s, __first, __last); } template<__detail::__container_compatible_range<value_type> _Rg> + _GLIBCXX26_CONSTEXPR _Flat_set_impl(from_range_t, _Rg&& __rg) : _Flat_set_impl(from_range, std::forward<_Rg>(__rg), key_compare()) { } template<__detail::__container_compatible_range<value_type> _Rg> + _GLIBCXX26_CONSTEXPR _Flat_set_impl(from_range_t, _Rg&& __rg, const key_compare& __comp) : _Flat_set_impl(__comp) { insert_range(std::forward<_Rg>(__rg)); } + _GLIBCXX26_CONSTEXPR _Flat_set_impl(initializer_list<value_type> __il, const key_compare& __comp = key_compare()) : _Flat_set_impl(__il.begin(), __il.end(), __comp) { } + _GLIBCXX26_CONSTEXPR _Flat_set_impl(__sorted_t __s, initializer_list<value_type> __il, const key_compare& __comp = key_compare()) @@ -174,23 +189,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // constructors with allocators template<__allocator_for<container_type> _Alloc> + _GLIBCXX26_CONSTEXPR explicit _Flat_set_impl(const _Alloc& __a) : _Flat_set_impl(key_compare(), __a) { } template<__allocator_for<container_type> _Alloc> + _GLIBCXX26_CONSTEXPR _Flat_set_impl(const key_compare& __comp, const _Alloc& __a) : _M_cont(std::make_obj_using_allocator<container_type>(__a)), _M_comp(__comp) { } template<__allocator_for<container_type> _Alloc> + _GLIBCXX26_CONSTEXPR _Flat_set_impl(const container_type& __cont, const _Alloc& __a) : _Flat_set_impl(__cont, key_compare(), __a) { } template<__allocator_for<container_type> _Alloc> + _GLIBCXX26_CONSTEXPR _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)), @@ -198,11 +217,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { _M_sort_uniq(); } template<__allocator_for<container_type> _Alloc> + _GLIBCXX26_CONSTEXPR _Flat_set_impl(__sorted_t __s, const container_type& __cont, const _Alloc& __a) : _Flat_set_impl(__s, __cont, key_compare(), __a) { } template<__allocator_for<container_type> _Alloc> + _GLIBCXX26_CONSTEXPR _Flat_set_impl(__sorted_t, const container_type& __cont, const key_compare& __comp, const _Alloc& __a) : _M_cont(std::make_obj_using_allocator<container_type>(__a, __cont)), @@ -210,24 +231,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { _GLIBCXX_DEBUG_ASSERT(ranges::is_sorted(_M_cont, _M_comp)); } template<__allocator_for<container_type> _Alloc> + _GLIBCXX26_CONSTEXPR _Flat_set_impl(const _Derived& __x, const _Alloc& __a) : _M_cont(std::make_obj_using_allocator<container_type>(__a, __x._M_cont)), _M_comp(__x._M_comp) { } template<__allocator_for<container_type> _Alloc> + _GLIBCXX26_CONSTEXPR _Flat_set_impl(_Derived&& __x, const _Alloc& __a) : _M_cont(std::make_obj_using_allocator<container_type>(__a, std::move(__x._M_cont))), _M_comp(__x._M_comp) { } template<__has_input_iter_cat _InputIterator, __allocator_for<container_type> _Alloc> + _GLIBCXX26_CONSTEXPR _Flat_set_impl(_InputIterator __first, _InputIterator __last, const _Alloc& __a) : _Flat_set_impl(std::move(__first), std::move(__last), key_compare(), __a) { } template<__has_input_iter_cat _InputIterator, __allocator_for<container_type> _Alloc> + _GLIBCXX26_CONSTEXPR _Flat_set_impl(_InputIterator __first, _InputIterator __last, const key_compare& __comp, const _Alloc& __a) @@ -235,6 +260,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { insert(__first, __last); } template<__has_input_iter_cat _InputIterator, __allocator_for<container_type> _Alloc> + _GLIBCXX26_CONSTEXPR _Flat_set_impl(__sorted_t __s, _InputIterator __first, _InputIterator __last, const _Alloc& __a) @@ -242,6 +268,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { } template<__has_input_iter_cat _InputIterator, __allocator_for<container_type> _Alloc> + _GLIBCXX26_CONSTEXPR _Flat_set_impl(__sorted_t __s, _InputIterator __first, _InputIterator __last, const key_compare& __comp, @@ -251,6 +278,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<__detail::__container_compatible_range<value_type> _Rg, __allocator_for<container_type> _Alloc> + _GLIBCXX26_CONSTEXPR _Flat_set_impl(from_range_t, _Rg&& __rg, const _Alloc& __a) : _Flat_set_impl(from_range, std::forward<_Rg>(__rg), key_compare(), __a) @@ -258,6 +286,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<__detail::__container_compatible_range<value_type> _Rg, __allocator_for<container_type> _Alloc> + _GLIBCXX26_CONSTEXPR _Flat_set_impl(from_range_t, _Rg&& __rg, const key_compare& __comp, const _Alloc& __a) @@ -265,12 +294,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { insert_range(std::forward<_Rg>(__rg)); } template<__allocator_for<container_type> _Alloc> + _GLIBCXX26_CONSTEXPR _Flat_set_impl(initializer_list<value_type> __il, const _Alloc& __a) : _Flat_set_impl(__il, key_compare(), __a) { } template<__allocator_for<container_type> _Alloc> + _GLIBCXX26_CONSTEXPR _Flat_set_impl(initializer_list<value_type> __il, const key_compare& __comp, const _Alloc& __a) @@ -278,6 +309,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { } template<__allocator_for<container_type> _Alloc> + _GLIBCXX26_CONSTEXPR _Flat_set_impl(__sorted_t __s, initializer_list<value_type> __il, const _Alloc& __a) @@ -285,6 +317,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { } template<__allocator_for<container_type> _Alloc> + _GLIBCXX26_CONSTEXPR _Flat_set_impl(__sorted_t __s, initializer_list<value_type> __il, const key_compare& __comp, @@ -292,6 +325,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION : _Flat_set_impl(__s, __il.begin(), __il.end(), __comp, __a) { } + _GLIBCXX26_CONSTEXPR _Derived& operator=(initializer_list<value_type> __il) { @@ -303,54 +337,66 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } // iterators + _GLIBCXX26_CONSTEXPR const_iterator begin() const noexcept { return _M_cont.begin(); } + _GLIBCXX26_CONSTEXPR const_iterator end() const noexcept { return _M_cont.end(); } + _GLIBCXX26_CONSTEXPR const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); } + _GLIBCXX26_CONSTEXPR const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); } + _GLIBCXX26_CONSTEXPR const_iterator cbegin() const noexcept { return begin(); } + _GLIBCXX26_CONSTEXPR const_iterator cend() const noexcept { return end(); } + _GLIBCXX26_CONSTEXPR const_reverse_iterator crbegin() const noexcept { return rbegin(); } + _GLIBCXX26_CONSTEXPR const_reverse_iterator crend() const noexcept { return rend(); } // capacity [[nodiscard]] + _GLIBCXX26_CONSTEXPR bool empty() const noexcept { return _M_cont.empty(); } + _GLIBCXX26_CONSTEXPR size_type size() const noexcept { return _M_cont.size(); } + _GLIBCXX26_CONSTEXPR size_type max_size() const noexcept { return _M_cont.max_size(); } // modifiers template<typename _Arg, typename... _Args> + _GLIBCXX26_CONSTEXPR pair<iterator, bool> _M_try_emplace(optional<const_iterator> __hint, _Arg&& __arg, _Args&&... __args) { @@ -410,12 +456,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template<typename... _Args> + _GLIBCXX26_CONSTEXPR pair<iterator, bool> _M_try_emplace(optional<const_iterator> __hint) { return _M_try_emplace(__hint, value_type()); } template<typename... _Args> requires is_constructible_v<value_type, _Args...> + _GLIBCXX26_CONSTEXPR __emplace_result_t emplace(_Args&&... __args) { @@ -427,39 +475,47 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template<typename... _Args> + _GLIBCXX26_CONSTEXPR iterator emplace_hint(const_iterator __position, _Args&&... __args) { return _M_try_emplace(__position, std::forward<_Args>(__args)...).first; } + _GLIBCXX26_CONSTEXPR __emplace_result_t insert(const value_type& __x) { return emplace(__x); } + _GLIBCXX26_CONSTEXPR __emplace_result_t insert(value_type&& __x) { return emplace(std::move(__x)); } + _GLIBCXX26_CONSTEXPR iterator insert(const_iterator __position, const value_type& __x) { return emplace_hint(__position, __x); } + _GLIBCXX26_CONSTEXPR 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> + _GLIBCXX26_CONSTEXPR __emplace_result_t insert(_Arg&& __x) { return emplace(std::forward<_Arg>(__x)); } template<typename _Arg> requires is_constructible_v<value_type, _Arg> + _GLIBCXX26_CONSTEXPR iterator insert(const_iterator __position, _Arg&& __x) { return emplace_hint(__position, std::forward<_Arg>(__x)); } template<__has_input_iter_cat _InputIterator> + _GLIBCXX26_CONSTEXPR void insert(_InputIterator __first, _InputIterator __last) { @@ -473,6 +529,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template<__has_input_iter_cat _InputIterator> + _GLIBCXX26_CONSTEXPR void insert(__sorted_t, _InputIterator __first, _InputIterator __last) { @@ -485,6 +542,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template<__detail::__container_compatible_range<value_type> _Rg> + _GLIBCXX26_CONSTEXPR void insert_range(_Rg&& __rg) { @@ -511,14 +569,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __guard._M_disable(); } + _GLIBCXX26_CONSTEXPR void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); } + _GLIBCXX26_CONSTEXPR void insert(__sorted_t __s, initializer_list<value_type> __il) { insert(__s, __il.begin(), __il.end()); } + _GLIBCXX26_CONSTEXPR container_type extract() && { @@ -526,6 +587,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return std::move(_M_cont); } + _GLIBCXX26_CONSTEXPR void replace(container_type&& __cont) { @@ -535,10 +597,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __guard._M_disable(); } + _GLIBCXX26_CONSTEXPR iterator erase(const_iterator __position) { return _M_cont.erase(__position); } + _GLIBCXX26_CONSTEXPR size_type erase(const key_type& __x) { return erase<const key_type&>(__x); } @@ -548,6 +612,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION || (__transparent_comparator<_Compare> && !is_convertible_v<_Key2, iterator> && !is_convertible_v<_Key2, const_iterator>) + _GLIBCXX26_CONSTEXPR size_type erase(_Key2&& __x) { @@ -557,10 +622,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return __n; } + _GLIBCXX26_CONSTEXPR iterator erase(const_iterator __first, const_iterator __last) { return _M_cont.erase(__first, __last); } + _GLIBCXX26_CONSTEXPR void swap(_Derived& __x) noexcept { @@ -569,28 +636,33 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION swap(_M_comp, __x._M_comp); } + _GLIBCXX26_CONSTEXPR void clear() noexcept { _M_cont.clear(); } // observers [[nodiscard]] + _GLIBCXX26_CONSTEXPR key_compare key_comp() const { return _M_comp; } [[nodiscard]] + _GLIBCXX26_CONSTEXPR value_compare value_comp() const { return _M_comp; } // set operations [[nodiscard]] + _GLIBCXX26_CONSTEXPR iterator find(const key_type& __x) { return find<key_type>(__x); } [[nodiscard]] + _GLIBCXX26_CONSTEXPR const_iterator find(const key_type& __x) const { return find<key_type>(__x); } @@ -598,6 +670,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _Key2> requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> [[nodiscard]] + _GLIBCXX26_CONSTEXPR iterator find(const _Key2& __x) { @@ -611,6 +684,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _Key2> requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> [[nodiscard]] + _GLIBCXX26_CONSTEXPR const_iterator find(const _Key2& __x) const { @@ -622,6 +696,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } [[nodiscard]] + _GLIBCXX26_CONSTEXPR size_type count(const key_type& __x) const { return count<key_type>(__x); } @@ -629,6 +704,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _Key2> requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> [[nodiscard]] + _GLIBCXX26_CONSTEXPR size_type count(const _Key2& __x) const { @@ -642,6 +718,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } [[nodiscard]] + _GLIBCXX26_CONSTEXPR bool contains(const key_type& __x) const { return contains<key_type>(__x); } @@ -649,16 +726,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _Key2> requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> [[nodiscard]] + _GLIBCXX26_CONSTEXPR bool contains(const _Key2& __x) const { return find(__x) != cend(); } [[nodiscard]] + _GLIBCXX26_CONSTEXPR iterator lower_bound(const key_type& __x) { return lower_bound<key_type>(__x); } [[nodiscard]] + _GLIBCXX26_CONSTEXPR const_iterator lower_bound(const key_type& __x) const { return lower_bound<key_type>(__x); } @@ -666,6 +746,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _Key2> requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> [[nodiscard]] + _GLIBCXX26_CONSTEXPR iterator lower_bound(const _Key2& __x) { return std::lower_bound(begin(), end(), __x, _M_comp); } @@ -673,16 +754,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _Key2> requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> [[nodiscard]] + _GLIBCXX26_CONSTEXPR const_iterator lower_bound(const _Key2& __x) const { return std::lower_bound(begin(), end(), __x, _M_comp); } [[nodiscard]] + _GLIBCXX26_CONSTEXPR iterator upper_bound(const key_type& __x) { return upper_bound<key_type>(__x); } [[nodiscard]] + _GLIBCXX26_CONSTEXPR const_iterator upper_bound(const key_type& __x) const { return upper_bound<key_type>(__x); } @@ -690,6 +774,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _Key2> requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> [[nodiscard]] + _GLIBCXX26_CONSTEXPR iterator upper_bound(const _Key2& __x) { return std::upper_bound(begin(), end(), __x, _M_comp); } @@ -697,16 +782,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _Key2> requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> [[nodiscard]] + _GLIBCXX26_CONSTEXPR const_iterator upper_bound(const _Key2& __x) const { return std::upper_bound(begin(), end(), __x, _M_comp); } [[nodiscard]] + _GLIBCXX26_CONSTEXPR pair<iterator, iterator> equal_range(const key_type& __x) { return equal_range<key_type>(__x); } [[nodiscard]] + _GLIBCXX26_CONSTEXPR pair<const_iterator, const_iterator> equal_range(const key_type& __x) const { return equal_range<key_type>(__x); } @@ -714,6 +802,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _Key2> requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> [[nodiscard]] + _GLIBCXX26_CONSTEXPR pair<iterator, iterator> equal_range(const _Key2& __x) { return std::equal_range(begin(), end(), __x, _M_comp); } @@ -721,18 +810,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _Key2> requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> [[nodiscard]] + _GLIBCXX26_CONSTEXPR pair<const_iterator, const_iterator> equal_range(const _Key2& __x) const { return std::equal_range(begin(), end(), __x, _M_comp); } [[nodiscard]] - friend bool + friend _GLIBCXX26_CONSTEXPR bool operator==(const _Derived& __x, const _Derived& __y) { return std::equal(__x.begin(), __x.end(), __y.begin(), __y.end()); } template<typename _Up = value_type> [[nodiscard]] - friend __detail::__synth3way_t<_Up> + friend _GLIBCXX26_CONSTEXPR __detail::__synth3way_t<_Up> operator<=>(const _Derived& __x, const _Derived& __y) { return std::lexicographical_compare_three_way(__x.begin(), __x.end(), @@ -740,11 +830,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __detail::__synth3way); } - friend void + friend _GLIBCXX26_CONSTEXPR void swap(_Derived& __x, _Derived& __y) noexcept { return __x.swap(__y); } template<typename _Predicate> + _GLIBCXX26_CONSTEXPR size_type _M_erase_if(_Predicate __pred) { @@ -762,6 +853,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION container_type _M_cont; [[no_unique_address]] _Compare _M_comp; + _GLIBCXX26_CONSTEXPR void _M_sort_uniq() { @@ -770,13 +862,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_unique(); } + _GLIBCXX26_CONSTEXPR void _M_unique() requires (!_Multi) { struct __key_equiv { + _GLIBCXX26_CONSTEXPR __key_equiv(key_compare __c) : _M_comp(__c) { } + _GLIBCXX26_CONSTEXPR bool operator()(const_reference __x, const_reference __y) const { return !_M_comp(__x, __y) && !_M_comp(__y, __x); } @@ -934,6 +1029,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _Key, typename _Compare, typename _KeyContainer, typename _Predicate> + _GLIBCXX26_CONSTEXPR typename flat_set<_Key, _Compare, _KeyContainer>::size_type erase_if(flat_set<_Key, _Compare, _KeyContainer>& __c, _Predicate __pred) { return __c._M_erase_if(std::move(__pred)); } @@ -1081,6 +1177,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _Key, typename _Compare, typename _KeyContainer, typename _Predicate> + _GLIBCXX26_CONSTEXPR typename flat_multiset<_Key, _Compare, _KeyContainer>::size_type erase_if(flat_multiset<_Key, _Compare, _KeyContainer>& __c, _Predicate __pred) { return __c._M_erase_if(std::move(__pred)); } diff --git a/libstdc++-v3/testsuite/23_containers/flat_multiset/constexpr.cc b/libstdc++-v3/testsuite/23_containers/flat_multiset/constexpr.cc new file mode 100644 index 00000000000..860b7660809 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/flat_multiset/constexpr.cc @@ -0,0 +1,239 @@ +// { dg-do run { target c++26 } } + +#include <flat_set> +#include <ranges> +#include <vector> + +#include <testsuite_allocator.h> +#include <testsuite_hooks.h> + +template <template <class> class Sequence> constexpr 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); +} + +constexpr 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); +} + +constexpr 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})); +} + +constexpr void test04() { + using vector = std::vector<int, __gnu_test::uneq_allocator<int>>; + vector v = {1, 2, 3}; + __gnu_test::uneq_allocator<int> alloc(42); + + using flat_multiset = std::flat_multiset<int, std::less<int>, vector>; + flat_multiset m1(alloc); + VERIFY(std::move(m1).extract().get_allocator().get_personality() == 42); + + flat_multiset m2(v, alloc); + VERIFY(std::move(m2).extract().get_allocator().get_personality() == 42); + + flat_multiset m3(std::sorted_equivalent_t{}, v, alloc); + VERIFY(std::move(m3).extract().get_allocator().get_personality() == 42); + + alloc = __gnu_test::uneq_allocator<int>(43); + flat_multiset m4(m3, alloc); + VERIFY(std::move(m4).extract().get_allocator().get_personality() == 43); + + alloc = __gnu_test::uneq_allocator<int>(44); + flat_multiset m5(std::move(m4), alloc); + VERIFY(std::move(m5).extract().get_allocator().get_personality() == 44); +} + +constexpr void test05() { + std::flat_multiset<int> s; + auto r = std::views::iota(1) | std::views::take(5); + static_assert(!std::ranges::common_range<decltype(r)>); + s.insert_range(r); + VERIFY(std::ranges::equal(s, (int[]){1, 2, 3, 4, 5})); + s.clear(); + s.insert_range(r | std::views::reverse); + VERIFY(std::ranges::equal(s, (int[]){1, 2, 3, 4, 5})); +} + +template <typename T> struct NoInsertRange : std::vector<T> { + using std::vector<T>::vector; + + template <typename It, typename R> + void insert_range(typename std::vector<T>::const_iterator, R &&) = delete; +}; + +struct NoCatIterator { + using difference_type = int; + using value_type = int; + + constexpr NoCatIterator() : v(0) {} + constexpr NoCatIterator(int x) : v(x) {} + + constexpr int operator*() const { return v; } + + constexpr NoCatIterator &operator++() { + ++v; + return *this; + } + + constexpr NoCatIterator operator++(int) { + ++v; + return NoCatIterator(v - 1); + } + + constexpr bool operator==(const NoCatIterator &rhs) const { + return v == rhs.v; + } + +private: + int v; +}; + +template <> struct std::iterator_traits<NoCatIterator> { + using difference_type = int; + using value_type = int; + using iterator_concept = std::input_iterator_tag; +}; + +constexpr void test06() { + std::flat_multiset<int> s; + std::flat_multiset<int, std::less<int>, NoInsertRange<int>> s2; + + auto r = std::ranges::subrange<NoCatIterator>(1, 6); + s.insert_range(r); + VERIFY(std::ranges::equal(s, (int[]){1, 2, 3, 4, 5})); + s2.insert_range(r); + VERIFY(std::ranges::equal(s2, (int[]){1, 2, 3, 4, 5})); + +#ifdef __SIZEOF_INT128__ + auto r2 = std::views::iota(__int128(1), __int128(6)); + s.clear(); + s.insert_range(r2); + VERIFY(std::ranges::equal(s, (int[]){1, 2, 3, 4, 5})); + + s2.clear(); + s2.insert_range(r2); + VERIFY(std::ranges::equal(s2, (int[]){1, 2, 3, 4, 5})); +#endif +} + +constexpr void test07() { + int copy_counter = 0; + + struct A { + int *counter; + constexpr A(int &c) : counter(&c) {} + + constexpr A(const A &other) : counter(other.counter) { ++(*counter); } + + constexpr A &operator=(const A &other) { + counter = other.counter; + ++(*counter); + return *this; + } + + constexpr auto operator<=>(const A &) const = default; + }; + + std::vector<A> v; + v.reserve(2); + std::flat_multiset<A> s(std::move(v)); + A a(copy_counter); + s.emplace(a); + VERIFY(copy_counter == 1); + s.emplace(a); + VERIFY(copy_counter == 2); +} + +constexpr void test08() { + std::flat_multiset<int> s = {1, 1, 2, 2, 3, 4, 5}; + auto n = std::erase_if(s, [](int x) { return x % 2 != 0; }); + VERIFY(n == 4); + VERIFY(std::ranges::equal(s, (int[]){2, 2, 4})); +} + +constexpr bool test() { + test01<std::vector>(); + test02(); + test03(); + test04(); + test05(); + test06(); + test07(); + test08(); + return true; +} + +int main() { + VERIFY(test()); + static_assert(test()); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/flat_set/constexpr.cc b/libstdc++-v3/testsuite/23_containers/flat_set/constexpr.cc new file mode 100644 index 00000000000..a5291e7a26f --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/flat_set/constexpr.cc @@ -0,0 +1,253 @@ +// { dg-do run { target c++26 } } + +#include <flat_set> +#include <ranges> +#include <vector> + +#include <testsuite_allocator.h> +#include <testsuite_hooks.h> + +#if __cpp_lib_constexpr_flat_set != 202502L +#error "Feature-test macro __cpp_lib_constexpr_flat_set has wrong value in <flat_set>" +#endif + +template <template <typename> class KeyContainer> constexpr void test01() { + std::flat_set<int, std::less<int>, KeyContainer<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(), (i + 0) % 4); + m.insert(m.end(), (i + 1) % 4); + m.insert(m.end(), (i + 2) % 4); + m.insert(m.end(), (i + 3) % 4); + 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); + + auto m_copy = m; + VERIFY(m_copy == m); + m_copy.operator=({12, 11, 10}); + VERIFY(m_copy == m); +} + +constexpr 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); +} + +constexpr 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})); +} + +constexpr void test04() { + using vector = std::vector<int, __gnu_test::uneq_allocator<int>>; + vector v = {1, 2, 3}; + __gnu_test::uneq_allocator<int> alloc(42); + + using flat_set = std::flat_set<int, std::less<int>, vector>; + flat_set m1(alloc); + VERIFY(std::move(m1).extract().get_allocator().get_personality() == 42); + + flat_set m2(v, alloc); + VERIFY(std::move(m2).extract().get_allocator().get_personality() == 42); + + flat_set m3(std::sorted_unique_t{}, v, alloc); + VERIFY(std::move(m3).extract().get_allocator().get_personality() == 42); + + alloc = __gnu_test::uneq_allocator<int>(43); + flat_set m4(m3, alloc); + VERIFY(std::move(m4).extract().get_allocator().get_personality() == 43); + + alloc = __gnu_test::uneq_allocator<int>(44); + flat_set m5(std::move(m4), alloc); + VERIFY(std::move(m5).extract().get_allocator().get_personality() == 44); +} + +constexpr void test05() { + std::flat_set<int> s; + auto r = std::views::iota(1) | std::views::take(5); + static_assert(!std::ranges::common_range<decltype(r)>); + s.insert_range(r); + VERIFY(std::ranges::equal(s, (int[]){1, 2, 3, 4, 5})); + s.clear(); + s.insert_range(r | std::views::reverse); + VERIFY(std::ranges::equal(s, (int[]){1, 2, 3, 4, 5})); +} + +template <typename T> struct NoInsertRange : std::vector<T> { + using std::vector<T>::vector; + + template <typename It, typename R> + void insert_range(typename std::vector<T>::const_iterator, R &&) = delete; +}; + +struct NoCatIterator { + using difference_type = int; + using value_type = int; + + constexpr NoCatIterator() : v(0) {} + constexpr NoCatIterator(int x) : v(x) {} + + constexpr int operator*() const { return v; } + + constexpr NoCatIterator &operator++() { + ++v; + return *this; + } + + constexpr NoCatIterator operator++(int) { + ++v; + return NoCatIterator(v - 1); + } + + constexpr bool operator==(const NoCatIterator &rhs) const { + return v == rhs.v; + } + +private: + int v; +}; + +template <> struct std::iterator_traits<NoCatIterator> { + using difference_type = int; + using value_type = int; + using iterator_concept = std::input_iterator_tag; +}; + +constexpr void test06() { + std::flat_set<int> s; + std::flat_set<int, std::less<int>, NoInsertRange<int>> s2; + + auto r = std::ranges::subrange<NoCatIterator>(1, 6); + s.insert_range(r); + VERIFY(std::ranges::equal(s, (int[]){1, 2, 3, 4, 5})); + s2.insert_range(r); + VERIFY(std::ranges::equal(s2, (int[]){1, 2, 3, 4, 5})); + +#ifdef __SIZEOF_INT128__ + auto r2 = std::views::iota(__int128(1), __int128(6)); + s.clear(); + s.insert_range(r2); + VERIFY(std::ranges::equal(s, (int[]){1, 2, 3, 4, 5})); + + s2.clear(); + s2.insert_range(r2); + VERIFY(std::ranges::equal(s2, (int[]){1, 2, 3, 4, 5})); +#endif +} + +constexpr void test07() { + int copy_counter = 0; + + struct A { + int *counter; + constexpr A(int &c) : counter(&c) {} + + constexpr A(const A &other) : counter(other.counter) { ++(*counter); } + + constexpr A &operator=(const A &other) { + counter = other.counter; + ++(*counter); + return *this; + } + + constexpr auto operator<=>(const A &) const = default; + }; + + std::flat_set<A> s; + + A a(copy_counter); + + s.emplace(a); + VERIFY(copy_counter == 1); + + s.emplace(a); + VERIFY(copy_counter == 1); +} + +constexpr void test08() { + std::flat_set<int> s = {1, 2, 3, 4, 5}; + auto n = std::erase_if(s, [](int x) { return x % 2 != 0; }); + VERIFY(n == 3); + VERIFY(std::ranges::equal(s, (int[]){2, 4})); +} + +constexpr bool test() { + test01<std::vector>(); + test02(); + test03(); + test04(); + test05(); + test06(); + test07(); + test08(); + return true; +} + +int main() { + VERIFY(test()); + static_assert(test()); + return 0; +} -- 2.52.0
