Why std::stable_sort does not compile when std::sort does?

Question

The code below fails to compile on GCC and CLang (msvc fails because of the experimental/propagate_const).

It is just PoC. Imagine the type X being complex, comparison operator meaningful and vector m non-empty.

#include <ranges>
#include <vector>
#include <experimental/propagate_const>
#include <memory>
#include <algorithm>

class X {};

std::shared_ptr<X> simplify(std::experimental::propagate_const<std::shared_ptr<X>>& i) {
   return get_underlying(i);
}

int operator<=>(const std::shared_ptr<X>& lhs, const std::shared_ptr<X>& rhs) {
   return 0;
}

void swap(std::shared_ptr<X> lhs, std::shared_ptr<X> rhs) {
   std::swap(lhs, rhs);
}

int main() {
   std::vector<std::experimental::propagate_const<std::shared_ptr<X>>> m;
   decltype(m | std::views::transform(simplify)) r = m | std::views::transform(simplify);
   std::sort(r.begin(), r.end()); // compiles
   std::stable_sort(r.begin(), r.end()); // ERROR: no matching function for call to ‘__rotate`...
}

https://godbolt.org/z/oWP7G1Ths

What is so special in std::stable_sort that it prevents compilation? How should I implement the __rotate?

Answer 1

std::rotate/std::ranges::rotate needs references to be able to swap elements, but your transform_view return copies (via simplify).

The requirements for std::rotate:

• ForwardIt must be ValueSwappable.
• The type of *first must be MoveConstructible.
• The type of *first must be MoveAssignable.

This fails for copies since you can't move assign a temporary. std::sort has the same requirements so the usage of std::sort in your program has undefined behavior - even though it seems to work.

Make simplify return a reference:

std::shared_ptr<X>& simplify(std::experimental::propagate_const<std::shared_ptr<X>>& i) {
//                ^
    return get_underlying(i);
}

Demo