我实现了快速排序算法。它在简单范围上工作正常，例如std::vector等。

template <typename R, typename Comp = std::ranges::less>
void quicksort(R&& range, Comp comp = {}) {
  namespace rng = std::ranges;

  if (rng::size(range) <= 1) {
    return;
  }

  auto pivot = HoarePartition(range, comp);

  quicksort(rng::subrange(rng::begin(range), pivot), comp);
  quicksort(rng::subrange(pivot + 1, rng::end(range)), comp);
}

template <typename R, typename Comp>
std::ranges::iterator_t<R> HoarePartition(R&& range, Comp comp) {
  namespace rng = std::ranges;

  auto pivot = rng::begin(range) + rng::size(range) / 2;  // NB: Median of Medians -> 3:7

  auto i = rng::begin(range);
  auto j = rng::begin(range) + rng::size(range) - 1;

  while (rng::distance(i, j) > 0) {
    while (comp(*i, *pivot)) {
      ++i;
    }
    while (comp(*pivot, *j)) {
      --j;
    }

    std::swap(*i, *j);  // <-- CE here

    if (pivot == i) {
      pivot = j;
      ++i;

    } else if (pivot == j) {
      pivot = i;
      --j;

    } else {
      ++i;
      --j;
    }
  }

  return pivot;
}

#include <iostream>
#include <vector>
#include <ranges>
#include <algorithm>

int main() {
  std::vector v = {3, 2, 4, 1, 5};

  std::vector u1 = v;
  quicksort(u1);  // OK

  auto u2 = v | std::views::transform([](auto x) { return x * 2; });
  quicksort(u2);  // CE
}

然而，当我用例如 std::views::transform 修改一个容器时，*j 处的错误提示说它是 cannot bind non-const lvalue reference of type ‘int&’ to an rvalue of type ‘int’。而 std::swap 处的错误则说 no matching function for call to ‘swap(int, int)’。为什么解引用后的值会同时被视为int引用和int？问题出在哪里？如何修复Hoare分区函数？

更有趣的是，它在 std::views::reverse 上也能工作。

解决方案

为什么解引用后的值会同时被视为int引用和int？

并不是。解引用后的值只有 int&。

编译器只是告诉你，如果存在签名 swap(int, int)，它就可以为那些 int& 工作。

问题出在哪里？

问题在于，你正在尝试对一个视图进行排序。

C++使用“视图”这个术语来描述一个范围，它在某些方面是只读的。

你可以对可变容器进行排序，但不能对只读视图进行排序。

如何修复Hoare分区函数？

一种办法是把你的新视图放到一个允许排序的容器中。

auto u2 = v
          | std::views::transform([](auto x) { return x * 2; })
          | std::ranges::to<std::vector>();

更有趣的是它在 std::views::reverse 上也能工作。

原因在于，在对其元素进行反向遍历时，你不需要对双向视图进行修改。这个任务比排序更容易。