C++20的std::ranges::sort是否不需要支持std::vector<bool>？

Question

C++20的std::ranges::sort是否不需要支持std::vector<bool>？

12

我注意到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::vector<bool> 创建一个 std::ranges::sort 的专门实现吗？有没有委员会关于这个问题的相关信息？

- 康桓瑋

6

C++20 应该移除 std::vector<bool> 的特化，采用 boost 的 boost::dynamic_bitset 代替，并加以改进。 - Cory Kramer

@CoryKramer 我同意std::vector<bool>应该被废弃，但std::bitset不是一个替代品，因为它需要一个编译时常量大小。 - François Andrieux

1

如果您阅读该页面（https://en.cppreference.com/w/cpp/container/vector_bool）中的注释，您会注意到`std::vector<bool>`迭代器是实现定义的，并且某些算法可能无法正常工作...所以我猜测排序支持不是必需的。实际上，对布尔值进行排序也没有太多意义。 - Phil1970

1

@Phil1970 是的，但是std::sort适用于std::vector<bool>，这就是我提出问题的原因。 - 康桓瑋

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Barry · Accepted Answer

作为更新，现在zip已被采用于c++23，该论文的一部分添加了const-assignment到vector<bool>::reference，这使得该类型能够满足indirectly_writable，因此在C++23中可以在vector<bool>上使用std::ranges::sort。

正确。

更普遍地说，std::ranges::sort 无法对代理引用进行排序。直接原因是 sort 需要 sortable（令人惊讶，对吧），如果我们沿着这条链往上走，需要 permutable，需要 indirectly_movable_storable，需要 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没有任何影响。显然，这是行不通的。用户有一个错误——他们打算按bar排序C（即使用投影），但实际上他们只是按bar排序（即使lambda返回一个引用，他们仍然只是排序bar而不是C——在这种情况下，C只有一个成员，但在一般情况下，这显然不是预期的行为）。

但是，我们的目标真正是：如何使这个错误不编译？这就是梦想。问题在于，C++11中添加了ref-qualifications，但隐式赋值一直存在。而且，隐式operator=没有ref-qualifier，你可以轻松地将一个rvalue赋值，即使这完全没有意义：

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

将rvalue分配给一个值仅在rvalue本身正确处理时才是可以的。理想情况下，我们可以检查类型是否具有带有rvalue限定符的operator=。代理类型（例如vector::reference）将会修饰它们的赋值运算符，这就是我们要检查的内容，每个人都很高兴。

但我们无法做到这一点 - 因为基本上每种类型都可以被赋值rvalue，即使实际上能够有意义地进行赋值的类型非常少。所以Eric和Casey提出的方法在道义上相当于向类型添加了一个类型特征，该特征表示“我是真正的rvalue-assignable”。与大多数类型特征不同的是，您需要执行以下操作：

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

这个只是拼写：

T& operator=(Whatever) const;

尽管const等式运算符不会作为算法的一部分实际调用，但它必须存在。

此时你可能会问 - 等等，引用呢？对于“普通”的范围（比如vector），iter_reference_t会给你int&，而const iter_reference_t&&仍然是int&。这就是为什么这个方法能够“正常工作”的原因。对于产生glvalue的范围来说，这些const赋值要求基本上复制了正常的赋值要求。const可赋值性问题只针对prvalue。

这也是为什么views::zip不在C++20中的原因。因为zip也会产生一个prvalue范围，而tuple<T&...>恰好是我们需要处理的代理引用类型。要处理它，我们必须对std::tuple进行更改，以允许这种const可赋值性。

据我所知，这仍然是既定方向（考虑到我们已经将该要求确立为概念，而没有标准库代理类型实际满足此要求）。因此，当添加views::zip时，tuple<T&...>将被设置为const可赋值，以及vector<bool>::reference。

这项工作的最终结果是：

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

实际上将会编译并正确工作。