[PATCH] Fix const constraint in std::stable_sort and std::inplace_merge

[François Dumont]

Hi

Once https://gcc.gnu.org/pipermail/libstdc++/2024-September/059568.html 
will be accepted we will be able fix this long lasting issue that 
std::stable_sort and std::inplace_merge are forcing the functor to take 
const& parameters even when iterators used in range are not const ones.

This patch fixes this problem in post-C++11.

    libstdc++: Remove const contraint on std::inplace_merge/stable_sort

    __lower_bound/__upper_bound have been designed as implementation 
details of
    respectively std::lower_bound/std::upper_bound. For this reason 
they are taking
    the value argument as a const&. It's being used in algos 
std::inplace_merge
    and std::stable_sort and so forces functor used in those algos to 
take const&.

    Using a rvalue reference __lower_bound/__upper_bound will 
automatically adapt
    to the usage context.

    libstdc++/ChangeLog:

            * include/bits/stl_algobase.h (__lower_bound): Use 
_GLIBCXX_FWDCREF to specify
            type of __val parameter.
            * include/bits/stl_algo.h (__upper_bound): Likewise.
            (__merge_adaptive_resize, __merge_without_buffer): Adapt.


François
diff --git a/libstdc++-v3/include/bits/stl_algo.h 
b/libstdc++-v3/include/bits/stl_algo.h
index 5eb22ed98e1..daff2416a45 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -2021,7 +2021,7 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
     _GLIBCXX20_CONSTEXPR
     _ForwardIterator
     __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
-                 const _Tp& __val, _GLIBCXX_FWDREF(_Compare) __comp)
+                 _GLIBCXX_FWDCREF(_Tp) __val, _GLIBCXX_FWDREF(_Compare) __comp)
     {
       typedef typename iterator_traits<_ForwardIterator>::difference_type
        _DistanceType;
@@ -2436,8 +2436,6 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
          __len1, __len2, __buffer, _GLIBCXX_FORWARD(_Compare, __comp));
       else
        {
-         typedef typename
-           std::iterator_traits<_BidirectionalIterator>::value_type _Val;
          _BidirectionalIterator __first_cut = __first;
          _BidirectionalIterator __second_cut = __middle;
          _Distance __len11 = 0;
@@ -2446,18 +2444,16 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
            {
              __len11 = __len1 / 2;
              std::advance(__first_cut, __len11);
-             const _Val& __val = *__first_cut;
              __second_cut
-               = std::__lower_bound(__middle, __last, __val, __comp);
+               = std::__lower_bound(__middle, __last, *__first_cut, __comp);
              __len22 = std::distance(__middle, __second_cut);
            }
          else
            {
              __len22 = __len2 / 2;
              std::advance(__second_cut, __len22);
-             const _Val& __val = *__second_cut;
              __first_cut
-               = std::__upper_bound(__first, __middle, __val, __comp);
+               = std::__upper_bound(__first, __middle, *__second_cut, __comp);
              __len11 = std::distance(__first, __first_cut);
            }
 
@@ -2496,8 +2492,6 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
          return;
        }
 
-      typedef
-       typename std::iterator_traits<_BidirectionalIterator>::value_type _Val;
       _BidirectionalIterator __first_cut = __first;
       _BidirectionalIterator __second_cut = __middle;
       _Distance __len11 = 0;
@@ -2506,18 +2500,16 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
        {
          __len11 = __len1 / 2;
          std::advance(__first_cut, __len11);
-         const _Val& __val = *__first_cut;
          __second_cut
-           = std::__lower_bound(__middle, __last, __val, __comp);
+           = std::__lower_bound(__middle, __last, *__first_cut, __comp);
          __len22 = std::distance(__middle, __second_cut);
        }
       else
        {
          __len22 = __len2 / 2;
          std::advance(__second_cut, __len22);
-         const _Val& __val = *__second_cut;
          __first_cut
-           = std::__upper_bound(__first, __middle, __val, __comp);
+           = std::__upper_bound(__first, __middle, *__second_cut, __comp);
          __len11 = std::distance(__first, __first_cut);
        }
 
diff --git a/libstdc++-v3/include/bits/stl_algobase.h 
b/libstdc++-v3/include/bits/stl_algobase.h
index c370581de19..284139372a7 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -1515,7 +1515,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
     _GLIBCXX20_CONSTEXPR
     _ForwardIterator
     __lower_bound(_ForwardIterator __first, _ForwardIterator __last,
-                 const _Tp& __val, _GLIBCXX_FWDREF(_Compare) __comp)
+                 _GLIBCXX_FWDCREF(_Tp) __val, _GLIBCXX_FWDREF(_Compare) __comp)
     {
       typedef typename iterator_traits<_ForwardIterator>::difference_type
        _DistanceType;
diff --git a/libstdc++-v3/testsuite/25_algorithms/stable_sort/1.cc 
b/libstdc++-v3/testsuite/25_algorithms/stable_sort/1.cc
index 0d62611eae2..71644b6e7d3 100644
--- a/libstdc++-v3/testsuite/25_algorithms/stable_sort/1.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/stable_sort/1.cc
@@ -84,6 +84,26 @@ test3()
     VERIFY(array[i].j == i % 2);
 }
 
+struct NotConstLess
+{
+  bool
+  operator()(S& s1, S& s2)
+  { return s1.i < s2.i; }
+};
+
+void
+test4()
+{
+#if __cplusplus >= 201103L
+  NotConstLess less;
+  S array[] = { -1, -2, 1, 2, -3 ,-5 ,3 , -4, 5, 4 };
+  test_container<S, random_access_iterator_wrapper> con(array,array + 10);
+  stable_sort(con.begin(), con.end(), less);
+  for(int i = 0; i < 10; ++i)
+    VERIFY(array[i].j == i % 2);
+#endif
+}
+
 int 
 main()
 {
@@ -91,13 +111,17 @@ main()
   test2();
 
   test3();
+  test4();
 
   __gnu_test::set_new_limit(sizeof(S) * 5);
   test3();
+  test4();
 
   __gnu_test::set_new_limit(sizeof(S));
   test3();
+  test4();
 
   __gnu_test::set_new_limit(0);
   test3();
+  test4();
 }