为何std::stable_sort编译失败而std::sort可正常编译？

问题背景 #

以下代码在GCC和Clang环境下编译失败（MSVC编译失败源于experimental/propagate_const组件），std::sort可正常编译，但std::stable_sort报错提示找不到匹配的__rotate函数：

#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()); // 编译成功
   std::stable_sort(r.begin(), r.end()); // 编译失败：no matching function for call to ‘__rotate`...
}

一、std::stable_sort导致编译失败的特殊机制 #

1. 算法实现依赖差异：std::sort通常基于快速排序/内省排序实现，核心依赖元素交换（swap）操作；而std::stable_sort在GCC/Clang的标准库实现中，会使用旋转（rotate）操作来维持元素的相对顺序，旋转操作要求迭代器能够返回可修改的左值引用，以便完成元素的移动赋值。
2. 视图元素的引用类型问题：当前代码中std::views::transform(simplify)生成的视图，其迭代器的operator*()返回的是std::shared_ptr<X>临时对象（右值）——因为simplify函数返回的是底层shared_ptr的拷贝，而非引用。旋转操作需要对元素进行赋值（如*dest = std::move(*src)），但临时对象无法作为赋值操作的左值，导致标准库内部的__rotate找不到匹配的重载。

二、适配方案（无需自定义__rotate） #

解决问题的核心是让操作的范围提供可修改的左值引用，或转换为支持该操作的容器：

方案1：修改simplify返回引用

让simplify返回底层shared_ptr的引用，这样transform视图的迭代器会返回左值引用，满足旋转操作的要求：

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

注意：此方案会直接修改原vector<propagate_const<shared_ptr<X>>>中元素的底层shared_ptr顺序，因为排序操作会通过引用直接操作原容器的元素。

方案2：将视图转换为容器

如果不想修改原容器的元素，可以将transform视图的结果转换为一个实际容器（如std::vector），容器的迭代器天然返回左值引用，可正常支持stable_sort：

int main() {
   std::vector<std::experimental::propagate_const<std::shared_ptr<X>>> m;
   std::vector<std::shared_ptr<X>> r(m | std::views::transform(simplify));
   std::stable_sort(r.begin(), r.end()); // 编译成功
}

内容的提问来源于stack exchange，提问作者Adam Ryczkowski