https://gcc.gnu.org/g:698ef4b29d875b9ab8903e95633f1473a29c217b
commit r15-8969-g698ef4b29d875b9ab8903e95633f1473a29c217b
Author: Giuseppe D'Angelo <giuseppe.dang...@kdab.com>
Date: Fri Mar 14 15:47:10 2025 +0100
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.
Diff:
---
libstdc++-v3/include/bits/algorithmfwd.h | 2 +
libstdc++-v3/include/bits/ranges_algo.h | 2 +
libstdc++-v3/include/bits/stl_algo.h | 9 +++
.../25_algorithms/headers/algorithm/synopsis.cc | 2 +
.../25_algorithms/inplace_merge/constexpr.cc | 72 ++++++++++++++++++++++
5 files changed, 87 insertions(+)
diff --git a/libstdc++-v3/include/bits/algorithmfwd.h
b/libstdc++-v3/include/bits/algorithmfwd.h
index 3e81bca0348a..05894b580028 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 d3644a83f802..2814d90061cc 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 c3fea76014cb..bb7dbfbd8e04 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 5000b18fc42b..8d5c1fb7ac73 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 000000000000..0bc4ed463d0f
--- /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());
