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

Question

我注意到 std::ranges::sort cannot 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::vector<bool> 专门化 std::ranges::sort？是否有任何关于委员会如何考虑的信息？

Answer 1

作为更新，既然 zip was adopted for c++23，那篇论文的一部分添加了 const-赋值给 vector<bool>::reference，它允许该类型满足 indirectly_writable，并且因此 std::ranges::sort 在 vector<bool> 上适用于 C++23。

正确。

更一般地说，std::ranges::sort 无法对代理引用进行排序。直接原因是 sort 需要 sortable（令人惊讶，对），如果我们按照链式向上需要 permutable，需要 indirectly_movable_storable，需要 indirectly_movable，需要 indirectly_movable 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 没有任何影响。

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

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

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

仅当 ravlue 本身正确处理时，分配给右值才真正可行。理想情况下，我们可以检查以确保类型具有 rvalue-qualified operator=。代理类型（例如 vector<bool>::reference）将限定它们的赋值运算符，这就是我们要检查的内容，大家都很高兴。

但我们不能那样做 - 因为基本上每种类型都是 rvalue-assignable，即使实际上有意义的类型很少。因此，Eric 和 Casey 的想法在道德上等同于向一个类型添加一个类型特征，该类型表示“我是，合法地，真实的，rvalue-assignable”。不像大多数类型特征，你会做类似的事情：

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&。这就是为什么这个 just works。对于产生 glvalues 的范围，这些 const-assignment 要求基本上重复了正常的赋值要求。const-assignability 问题是 _only_for prvalues。

这个问题也是 views::zip 不在 C++20 中的原因。因为 zip 也产生一个 prvalue 范围，而 tuple<T&...> 正是我们需要在这里处理的那种代理引用。为了解决这个问题，我们必须更改 std::tuple 以允许这种 const-assignability.

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

这项工作的最终结果是：

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

实际上可以正确编译和工作。

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

Should C++20 std::ranges::sort not need to support std::vector<bool>?

c++

stdvector

c++20

std-ranges