https://gcc.gnu.org/g:aba3018af8e025a62a87c704ccad6714b13bc811
commit r15-8970-gaba3018af8e025a62a87c704ccad6714b13bc811
Author: Giuseppe D'Angelo <giuseppe.dang...@kdab.com>
Date: Sat Mar 15 00:15:36 2025 +0100
libstdc++: add constexpr stable_partition
This completes the implementation of P2562R1 for C++26.
Unlike the other constexpr algorithms of the same family,
stable_partition does not have a constexpr-friendly version "ready to
use" during constant evaluation. In fact, it is not even available on
freestanding, because it always allocates a temporary memory buffer.
This commit implements the simplest possible strategy: during constant
evaluation allocate a buffer of length 1 on the stack, and use that as
a working area.
libstdc++-v3/ChangeLog:
* include/bits/algorithmfwd.h (stable_partition): Mark it
as constexpr for C++26.
* include/bits/ranges_algo.h (__stable_partition_fn): Likewise.
* include/bits/stl_algo.h (stable_partition): Mark it as
constexpr for C++26; during constant evaluation use a new
codepath where a temporary buffer of 1 element is used.
* testsuite/25_algorithms/headers/algorithm/synopsis.cc
(stable_partition): Add constexpr.
* testsuite/25_algorithms/stable_partition/constexpr.cc: New test.
Diff:
---
libstdc++-v3/include/bits/algorithmfwd.h | 1 +
libstdc++-v3/include/bits/ranges_algo.h | 2 +
libstdc++-v3/include/bits/stl_algo.h | 21 ++++++++++-
.../25_algorithms/headers/algorithm/synopsis.cc | 1 +
.../25_algorithms/stable_partition/constexpr.cc | 44 ++++++++++++++++++++++
5 files changed, 67 insertions(+), 2 deletions(-)
diff --git a/libstdc++-v3/include/bits/algorithmfwd.h
b/libstdc++-v3/include/bits/algorithmfwd.h
index 05894b580028..a727b2783814 100644
--- a/libstdc++-v3/include/bits/algorithmfwd.h
+++ b/libstdc++-v3/include/bits/algorithmfwd.h
@@ -649,6 +649,7 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
#if _GLIBCXX_HOSTED
template<typename _BIter, typename _Predicate>
+ _GLIBCXX26_CONSTEXPR
_BIter
stable_partition(_BIter, _BIter, _Predicate);
#endif
diff --git a/libstdc++-v3/include/bits/ranges_algo.h
b/libstdc++-v3/include/bits/ranges_algo.h
index 2814d90061cc..f36e7dd59911 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -2389,6 +2389,7 @@ namespace ranges
typename _Proj = identity,
indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
requires permutable<_Iter>
+ _GLIBCXX26_CONSTEXPR
subrange<_Iter>
operator()(_Iter __first, _Sent __last,
_Pred __pred, _Proj __proj = {}) const
@@ -2404,6 +2405,7 @@ namespace ranges
indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
_Pred>
requires permutable<iterator_t<_Range>>
+ _GLIBCXX26_CONSTEXPR
borrowed_subrange_t<_Range>
operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
{
diff --git a/libstdc++-v3/include/bits/stl_algo.h
b/libstdc++-v3/include/bits/stl_algo.h
index bb7dbfbd8e04..71ead103d2bf 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -1447,6 +1447,7 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
/// move-assign an element onto itself.
template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
typename _Distance>
+ _GLIBCXX26_CONSTEXPR
_ForwardIterator
__stable_partition_adaptive(_ForwardIterator __first,
_ForwardIterator __last,
@@ -1507,6 +1508,7 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
}
template<typename _ForwardIterator, typename _Predicate>
+ _GLIBCXX26_CONSTEXPR
_ForwardIterator
__stable_partition(_ForwardIterator __first, _ForwardIterator __last,
_Predicate __pred)
@@ -1521,11 +1523,25 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
typedef typename iterator_traits<_ForwardIterator>::difference_type
_DistanceType;
+ const _DistanceType __len = std::distance(__first, __last);
+
+#if __glibcxx_constexpr_algorithms >= 202306L // >= C++26
+ if consteval {
+ // Simulate a _Temporary_buffer of length 1:
+ _ValueType __buf = std::move(*__first);
+ *__first = std::move(__buf);
+ return std::__stable_partition_adaptive(__first, __last, __pred,
+ __len,
+ &__buf,
+ _DistanceType(1));
+ }
+#endif
+
_Temporary_buffer<_ForwardIterator, _ValueType>
- __buf(__first, std::distance(__first, __last));
+ __buf(__first, __len);
return
std::__stable_partition_adaptive(__first, __last, __pred,
- _DistanceType(__buf.requested_size()),
+ __len,
__buf.begin(),
_DistanceType(__buf.size()));
}
@@ -1548,6 +1564,7 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
* relative ordering after calling @p stable_partition().
*/
template<typename _ForwardIterator, typename _Predicate>
+ _GLIBCXX26_CONSTEXPR
inline _ForwardIterator
stable_partition(_ForwardIterator __first, _ForwardIterator __last,
_Predicate __pred)
diff --git a/libstdc++-v3/testsuite/25_algorithms/headers/algorithm/synopsis.cc
b/libstdc++-v3/testsuite/25_algorithms/headers/algorithm/synopsis.cc
index 8d5c1fb7ac73..072dd0781046 100644
--- a/libstdc++-v3/testsuite/25_algorithms/headers/algorithm/synopsis.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/headers/algorithm/synopsis.cc
@@ -349,6 +349,7 @@ namespace std
partition(_BIter, _BIter, _Predicate);
template<typename _BIter, typename _Predicate>
+ _GLIBCXX26_CONSTEXPR
_BIter
stable_partition(_BIter, _BIter, _Predicate);
diff --git a/libstdc++-v3/testsuite/25_algorithms/stable_partition/constexpr.cc
b/libstdc++-v3/testsuite/25_algorithms/stable_partition/constexpr.cc
new file mode 100644
index 000000000000..8decc93eb827
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/stable_partition/constexpr.cc
@@ -0,0 +1,44 @@
+// { dg-do compile { target c++26 } }
+
+#include <algorithm>
+#include <array>
+
+constexpr auto
+create_array()
+{
+ return std::to_array({0, 10, 1, 2, 3, 3, 4, -1, -2, -4, 5, 6});
+}
+
+constexpr bool
+test01()
+{
+ auto ar = create_array();
+ auto pred = [](int i) { return i % 2 == 0; };
+ std::stable_partition(ar.begin(), ar.end(), pred);
+ return std::is_partitioned(ar.begin(), ar.end(), pred);
+}
+
+static_assert(test01());
+
+constexpr bool
+test02()
+{
+ auto ar = create_array();
+ auto pred = [](int i) { return i % 2 == 0; };
+ std::ranges::stable_partition(ar, pred);
+ return std::ranges::is_partitioned(ar, pred);
+}
+
+static_assert(test02());
+
+constexpr bool
+test03()
+{
+ auto ar = create_array();
+ auto pred = [](int i) { return i % 2 == 0; };
+ auto proj = [](int i) { return i + 1; };
+ std::ranges::stable_partition(ar, pred, proj);
+ return std::ranges::is_partitioned(ar, pred, proj);
+}
+
+static_assert(test03());
