为什么Sortable概念要求完全有序的值类型，而std :: sort仅要求“小于”类型。可比？ [英] Why Sortable concept requires totally ordered value type, while std::sort only requires "less than" comparable?

问题描述

在有关概念N3701的最新文章中，下面是使用 sort 算法的示例：

In the latest paper on concepts N3701, there is the following example with the sort algorithm:

template<typename Cont>
  requires Sortable<Cont>()
void sort(Cont& cont)

其中可稳定概念定义为

template<typename T>
concept bool Sortable()
{
  return Permutable_container<T>() && Totally_ordered<Value_type<T>>();
}

其中 Totally_ordered ，毫不奇怪，定义为

where Totally_ordered, not surprisingly, is defined as

template<typename T>
constexpr bool Totally_ordered()
{
  return Weakly_ordered<T>() && Equality_comparable<T>();
}

，然后 Equality_comparable 定义为

template<typename T>
constexpr bool Equality_comparable()
{
  return requires(T a, T b) {
    {a == b} -> bool;
    {a != b} -> bool;
  };
}

我没有找到 Weakly_ordered ，但我认为它应该看起来像这样（对吗？）

I didn't find the definition of Weakly_ordered, but I believe it should look like this (am I right?)

template<typename T>
constexpr bool Weakly_ordered()
{
  return requires(T a, T b) {
    {a < b} -> bool;
    {a <= b} -> bool;
    {a > b} -> bool;
    {a >= b} -> bool;
  };
}

在此定义中，如果我想对<$ c $进行排序， c> std :: vector< T> ，我需要T提供 all 个比较运算符< ，< = ，> ，> = ， == ，！= 。但是，在C ++的整个生命周期中， std :: sort 仅需要提供运算符< ！这是 cppreference 关于 std :: sort ：

Bottom line, in this definition, if I want to sort std::vector<T>, I need T to provide all comparison operators <, <=, >, >=, ==, !=. However, during the whole life of C++, std::sort only required operator < to be provided! Here is what cppreference says about std::sort:

按升序排列[first，last）范围内的元素。不能保证等值元素的
顺序被保留。第一个
版本使用运算符<为了比较元素，第二个版本
使用给定的比较函数对象comp。

Sorts the elements in the range [first, last) in ascending order. The order of equal elements is not guaranteed to be preserved. The first version uses operator< to compare the elements, the second version uses the given comparison function object comp.

那又怎样，这是否意味着在将来的带有概念的C ++中，对于 std :: vector< T> 类型的 v ，其中 T 仅提供 operator< ， std :: sort（v.begin（），v.end （））会编译，而 std :: sort（v）不会编译？

So what, does that mean that in future C++ with concepts, for v of type std::vector<T> where T provides only operator<, std::sort(v.begin(), v.end()) will compile, while std::sort(v) will not? This sounds crazy.

我在当前的 Eric Niebler的range-v3实现，它的工作方式就像我描述的一样。除非提供所有运算符，否则代码不会编译。

I checked this in the current ranges-v3 implementation by Eric Niebler, and it works just like I described. Code does not compile unless all operators are provided.

另请参见相关讨论： https://github.com/ericniebler/range-v3/issues/271

推荐答案

Concepts TS没有概念化标准库。这仅仅是一个例子。

The Concepts TS does not conceptualize the standard library. It was merely an example; nothing more.

sort 的Ranges TS版本需要 Sortable ，默认将其比较类设置为 std :: less<> 。但是，似乎 std :: less<> :: operator（）对 TotallyOrdered 施加了其参数的类型。这就是它的来历。 P0021R0（PDF）：

The Ranges TS version of sort requires Sortable, which defaults its comparison class to std::less<>. However, it would seem that std::less<>::operator() imposes the TotallyOrdered requirement on the types of its parameters. So that's where it comes from. There's a note about this in P0021R0 (PDF):

[编者注：删除[utility.arg.requirements]中的表[lessthancomparable]。将LessThanComparable的用法替换为TotallyOrdered（确认这是一项重大更改，使类型要求更加严格）。将对[lessthancomparable]的引用替换为对[concepts.lib.compare.totallyordered]的引用]

in [utility.arg.requirements]. Replace uses of LessThanComparable with TotallyOrdered (acknowledging that this is a breaking change that makes type requirements stricter). Replace references to [lessthancomparable] with references to [concepts.lib.compare.totallyordered]]

强调。围绕似乎出现的问题，其他语言功能（例如仅基于 operator< 或类似方式隐式创建所有其他运算符。

Emphasis added. The general issues surrounding this appear to be on-hold, pending other language features (like implicit creation of all other operators based solely on operator< or somesuch).

您可以简单地使用（ ）版本的比较功能。或者，您可以只使用 std :: sort 迭代器版本，该版本将不使用任何类型的概念。

You could simply use a (sane) version of a comparison function. Or you could just use the std::sort iterator version, which won't use concepts of any kind.

还应注意，使用介绍 飞船操作员 在C ++ 20中（我们最早可以将Ranges TS集成到标准中），整个讨论实际上变得毫无意义。一个简单的 auto运算符< =>（const MyType&）= default; 声明在类中，突然您的类型被完全排序。

It should also be noted that, with the introduction of the "spaceship operator" in C++20 (the earliest we could see the Ranges TS integrated into the standard), this whole discussion effectively becomes moot. A simple auto operator<=>(const MyType &) = default; declaration in the class, and suddenly your type is totally ordered.

这篇关于为什么Sortable概念要求完全有序的值类型，而std :: sort仅要求“小于”类型。可比？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！