C++20 std::ranges::sort 应该不需要支持 std::vector<bool> 吗？

Question

我注意到std::ranges::sort无法排序std::vector<bool>：

<source>:6:51: error: no match for call to '(const std::ranges::__sort_fn) (std::vector<bool, std::allocator<bool> >)'
6 |   std::ranges::sort(std::vector{false, true, true});
  |   

这是允许的吗？我们是否需要专门化std::ranges::sortfor std::vector<bool>？是否有关于委员会如何考虑这一点的任何信息？

Answer 1

正确的。

更一般地说，std::ranges::sort不能对代理引用进行排序。直接的原因是sort需要sortable（令人惊讶，对）如果我们遵循该链需要permutablewhich requires indirectly_movable_storablewhich requires indirectly_movablewhich requires indirectly_writable。

并且indirectly_writeable是一个非常奇特的概念。

template<class Out, class T>
  concept indirectly_writable =
    requires(Out&& o, T&& t) {
      *o = std::forward<T>(t);  // not required to be equality-preserving
      *std::forward<Out>(o) = std::forward<T>(t);   // not required to be equality-preserving
      const_cast<const iter_reference_t<Out>&&>(*o) =
        std::forward<T>(t);     // not required to be equality-preserving
      const_cast<const iter_reference_t<Out>&&>(*std::forward<Out>(o)) =
        std::forward<T>(t);     // not required to be equality-preserving
    };

我想特别提请您注意：

const_cast<const iter_reference_t<Out>&&>(*o) = std::forward<T>(t);

等等，我们需要const可赋值性？

这个特殊的问题有着悠久的历史。您可以从#573开始，其中用户演示了此问题：

struct C
{
    explicit C(std::string a) : bar(a) {}    
    std::string bar;
};

int main()
{
    std::vector<C> cs = { C("z"), C("d"), C("b"), C("c") };

    ranges::sort(cs | ranges::view::transform([](const C& x) {return x.bar;}));

    for (const auto& c : cs) {
        std::cout << c.bar << std::endl;
    }
}

当然，期望它会按顺序打印 b、c、d、z。但它没有。它打印了 z、d、b、c。顺序没变。这里的原因是因为这是一个prvalues的范围，我们作为排序的一部分交换的元素。嗯，他们是临时工。这对cs任何情况都没有影响。

这显然行不通。用户有一个错误 - 他们打算按Cs 对bars进行排序（即使用投影），但他们只是对bars 进行排序（即使 lambda 返回了一个引用，他们也只会对bars进行排序，而不是对Cs 无论如何 - 在这种情况下，只有一个成员，C但在一般情况下，这显然不是预期的行为）。

但是目标实际上是：我们如何使这个错误无法编译？这就是梦想。问题是C++在C++11中添加了ref-qualifications，但是隐式赋值一直存在。并且隐式operator=没有引用限定符，您可以很好地分配给右值，即使这没有任何意义：

std::string("hello") = "goodbye"; // fine, but pointless, probably indicative of a bug

如果 ravlue 本身正确处理，分配给右值真的没问题。理想情况下，我们可以检查以确保类型具有 rvalue-qualified operator=。代理类型（例如vector<bool>::reference）然后会限定它们的赋值运算符，这就是我们要检查的，每个人都很高兴。

但我们不能这样做——因为基本​​上每种类型都是右值可赋值的，即使很少有类型真正有意义。所以 Eric 和 Casey 提出的在道德上等同于给一个类型添加一个类型特征，该类型说“我是，合法地，真实的，右值可赋值”。不像大多数类型特征，你会做这样的事情：

template <>
inline constexpr bool for_real_rvalue_assignable<T> = true;

这个只是拼写：

T& operator=(Whatever) const;

即使 const 相等运算符实际上不会作为算法的一部分被调用。它必须在那里。

此时您可能会问 - 等等，引用呢？对于“正常”的范围（比如vector<int>，在iter_reference_t<Out>给你int&，而且const iter_reference_t<Out>&&是...仍然只是int&，这就是为什么这只是工作。对于该范围内的产量glvalues，这些常量赋值要求基本上复制了正常的分配要求。该常数转让性问题是 _only_for 纯右值。

这个问题也是为什么views::zip不在 C++20 中的驱动因素。因为zip也会产生一个纯右值范围，而 atuple<T&...>正是我们在这里需要处理的那种代理引用。为了解决这个问题，我们必须进行更改std::tuple以允许这种 const 可分配性。

据我所知，这仍然是它的预期方向（鉴于我们已经将该要求写入了一个概念中，该要求实际上没有标准库代理类型满足）。因此，当views::zip添加时，tuple<T&...>将成为 const-assignable 以及vector<bool>::reference.

这项工作的最终结果是：

std::ranges::sort(std::vector{false, true, true});

实际上会编译并正常工作。

作为更新，当zipC++23 被采用时，该论文的一部分将添加const-assignment 到vector<bool>::reference，这将允许该类型满足indirectly_writable，从而std::ranges::sort能够工作。