Hello,These two patches complete the implementation of P2562R1 for C++26 (the paper is called "constexpr Stable Sorting", but these other permutation algorithms are also included).
You can also find them on Forgejo here: https://forge.sourceware.org/gcc/gcc-TEST/pulls/44 with some additional comments/questions.This first patch adds support for constexpr inplace_merge, which is relatively easy -- use if consteval to dispatch to a constexpr-friendly implementation.
Thank you, -- Giuseppe D'Angelo
From 40ae5ace0385ae0136ae1fe6b687aef0582a9348 Mon Sep 17 00:00:00 2001
From: Giuseppe D'Angelo <giuseppe.dang...@kdab.com>
Date: Fri, 14 Mar 2025 15:47:10 +0100
Subject: [PATCH 1/2] libstdc++: add constexpr inplace_merge
This commit adds support for constexpr inplace_merge, added by P2562R1
for C++26. The implementation strategy is the same as for constexpr
stable_sort: use if consteval to detect if we're in constant evaluation,
and dispatch to a suitable path (same one as freestanding).
libstdc++-v3/ChangeLog:
* include/bits/algorithmfwd.h (inplace_merge): Mark it as
constexpr for C++26.
* include/bits/ranges_algo.h (__inplace_merge_fn): Likewise.
* include/bits/stl_algo.h (inplace_merge): Mark it as constexpr;
during constant evaluation, dispatch to the non-allocating
codepath.
* testsuite/25_algorithms/headers/algorithm/synopsis.cc
(inplace_merge): Add constexpr.
* testsuite/25_algorithms/inplace_merge/constexpr.cc: New test.
Signed-off-by: Giuseppe D'Angelo <giuseppe.dang...@kdab.com>
---
libstdc++-v3/include/bits/algorithmfwd.h | 2 +
libstdc++-v3/include/bits/ranges_algo.h | 2 +
libstdc++-v3/include/bits/stl_algo.h | 9 +++
.../headers/algorithm/synopsis.cc | 2 +
.../25_algorithms/inplace_merge/constexpr.cc | 72 +++++++++++++++++++
5 files changed, 87 insertions(+)
create mode 100644 libstdc++-v3/testsuite/25_algorithms/inplace_merge/constexpr.cc
diff --git a/libstdc++-v3/include/bits/algorithmfwd.h b/libstdc++-v3/include/bits/algorithmfwd.h
index 3e81bca0348..05894b58002 100644
--- a/libstdc++-v3/include/bits/algorithmfwd.h
+++ b/libstdc++-v3/include/bits/algorithmfwd.h
@@ -315,10 +315,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
includes(_IIter1, _IIter1, _IIter2, _IIter2, _Compare);
template<typename _BIter>
+ _GLIBCXX26_CONSTEXPR
void
inplace_merge(_BIter, _BIter, _BIter);
template<typename _BIter, typename _Compare>
+ _GLIBCXX26_CONSTEXPR
void
inplace_merge(_BIter, _BIter, _BIter, _Compare);
diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index d3644a83f80..2814d90061c 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -2598,6 +2598,7 @@ namespace ranges
typename _Comp = ranges::less,
typename _Proj = identity>
requires sortable<_Iter, _Comp, _Proj>
+ _GLIBCXX26_CONSTEXPR
_Iter
operator()(_Iter __first, _Iter __middle, _Sent __last,
_Comp __comp = {}, _Proj __proj = {}) const
@@ -2611,6 +2612,7 @@ namespace ranges
template<bidirectional_range _Range,
typename _Comp = ranges::less, typename _Proj = identity>
requires sortable<iterator_t<_Range>, _Comp, _Proj>
+ _GLIBCXX26_CONSTEXPR
borrowed_iterator_t<_Range>
operator()(_Range&& __r, iterator_t<_Range> __middle,
_Comp __comp = {}, _Proj __proj = {}) const
diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index c3fea76014c..bb7dbfbd8e0 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -2465,6 +2465,7 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
}
template<typename _BidirectionalIterator, typename _Compare>
+ _GLIBCXX26_CONSTEXPR
void
__inplace_merge(_BidirectionalIterator __first,
_BidirectionalIterator __middle,
@@ -2483,6 +2484,12 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
const _DistanceType __len2 = std::distance(__middle, __last);
#if _GLIBCXX_HOSTED
+# if __glibcxx_constexpr_algorithms >= 202306L // >= C++26
+ if consteval {
+ return std::__merge_without_buffer
+ (__first, __middle, __last, __len1, __len2, __comp);
+ }
+# endif
typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
// __merge_adaptive will use a buffer for the smaller of
// [first,middle) and [middle,last).
@@ -2523,6 +2530,7 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
* distance(__first,__last).
*/
template<typename _BidirectionalIterator>
+ _GLIBCXX26_CONSTEXPR
inline void
inplace_merge(_BidirectionalIterator __first,
_BidirectionalIterator __middle,
@@ -2564,6 +2572,7 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
* the function used for the initial sort.
*/
template<typename _BidirectionalIterator, typename _Compare>
+ _GLIBCXX26_CONSTEXPR
inline void
inplace_merge(_BidirectionalIterator __first,
_BidirectionalIterator __middle,
diff --git a/libstdc++-v3/testsuite/25_algorithms/headers/algorithm/synopsis.cc b/libstdc++-v3/testsuite/25_algorithms/headers/algorithm/synopsis.cc
index 5000b18fc42..8d5c1fb7ac7 100644
--- a/libstdc++-v3/testsuite/25_algorithms/headers/algorithm/synopsis.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/headers/algorithm/synopsis.cc
@@ -458,10 +458,12 @@ namespace std
merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare);
template<typename _BIter>
+ _GLIBCXX26_CONSTEXPR
void
inplace_merge(_BIter, _BIter, _BIter);
template<typename _BIter, typename _Compare>
+ _GLIBCXX26_CONSTEXPR
void
inplace_merge(_BIter, _BIter, _BIter, _Compare);
diff --git a/libstdc++-v3/testsuite/25_algorithms/inplace_merge/constexpr.cc b/libstdc++-v3/testsuite/25_algorithms/inplace_merge/constexpr.cc
new file mode 100644
index 00000000000..0bc4ed463d0
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/inplace_merge/constexpr.cc
@@ -0,0 +1,72 @@
+// { dg-do compile { target c++26 } }
+
+#include <algorithm>
+#include <array>
+#include <functional>
+#include <utility>
+
+// returns a pair [array, index of partitioning point]
+constexpr auto
+create_array()
+{
+ return std::make_pair(
+ std::to_array({0, 2, 2, 2, 4, 6, 1, 2, 3, 3, 4, 4, 5}),
+ 6);
+}
+
+constexpr bool
+test01()
+{
+ auto [ar, index] = create_array();
+ std::inplace_merge(ar.begin(), ar.begin() + index, ar.end());
+ return std::is_sorted(ar.begin(), ar.end());
+}
+
+static_assert(test01());
+
+constexpr bool
+test02()
+{
+ auto [ar, index] = create_array();
+ auto index_it = ar.begin() + index;
+ std::reverse(ar.begin(), index_it);
+ std::reverse(index_it, ar.end());
+ std::inplace_merge(ar.begin(), index_it, ar.end(), std::greater<>());
+ return std::is_sorted(ar.begin(), ar.end(), std::greater<>());
+}
+
+static_assert(test02());
+
+constexpr bool
+test03()
+{
+ auto [ar, index] = create_array();
+ std::ranges::inplace_merge(ar, ar.begin() + index);
+ return std::ranges::is_sorted(ar);
+}
+
+static_assert(test03());
+
+constexpr bool
+test04()
+{
+ auto [ar, index] = create_array();
+ auto index_it = ar.begin() + index;
+ std::ranges::reverse(ar.begin(), index_it);
+ std::ranges::reverse(index_it, ar.end());
+ std::ranges::inplace_merge(ar, index_it, std::ranges::greater());
+ return std::ranges::is_sorted(ar, std::ranges::greater());
+}
+
+static_assert(test04());
+
+constexpr bool
+test05()
+{
+ auto [ar, index] = create_array();
+ auto proj = [](int i) { return -i; };
+ std::ranges::inplace_merge(ar, ar.begin() + index, std::ranges::greater(), proj);
+ return std::ranges::is_sorted(ar, std::ranges::greater(), proj);
+}
+
+static_assert(test05());
--
2.34.1
smime.p7s
Description: S/MIME Cryptographic Signature
