C++20: Three-way Comparison

C++20: Three-way Comparison

Published
Published July 7, 2021
Tags
C++
C++20

Three-Way Comparison

C++20新增了一个运算符 <=>,称为 three way comparison operator,或三路比较运算符。这个运算符是一个二元运算符,它给出两个操作数的序关系(ordering)。三路比较运算符的优先级是所有二元比较运算符中最高的。
C++20定义了三种序关系,包括 strong ordering,weak ordering 以及 partial ordering。三路比较运算符依照操作数的类型,在大部分情况下将返回这三种序关系中的一种。

Partial Ordering

又称为偏序。在偏序关系中,两个值可能会存在序关系,但并非任意两个值都存在序关系。例如,浮点数类型上存在一个偏序关系。对于两个不为 NaN 的浮点数值,它们之间存在序关系,可以比较大小;但 NaN 与任意浮点数值不存在序关系。偏序关系使用 std::partial_ordering 进行表示。例如:
double a = 1.0; double b = 2.0; double c = std::numeric_limits<double>::quiet_NaN(); std::partial_ordering ordering; ordering = a <=> b; assert(ordering == std::partial_ordering::less); // a < b ordering = b <=> a; assert(ordering == std::partial_ordering::greater); // a > b ordering = a <=> c; assert(ordering == std::partial_ordering::unordered); // NaN does not have partial ordering

Weak Ordering

又称弱序。在弱序关系中,任意的两个值都存在序关系,可以比较大小。但序关系为相等的两个值不一定是不可辨别的。两个值 ab 是不可辨别的,当且仅当可以将包含 a 的表达式中的 a 全部替换为 b 而不影响表达式的值。弱序关系由std::weak_ordering表示。例如有如下的分数类,使用分子和分母表示一个有理数:
struct Fraction { int dividend; int divisor; };
Fraction 应该具有弱序关系。因为分数 10/54/2 应该具有相等关系,但是它们是可以辨别的。因此可以这样定义 Fraction<=> 运算符:
std::weak_ordering operator<=>(const Fraction& lhs, const Fraction& rhs) noexcept { auto lhs_n = lhs.dividend; auto lhs_d = lhs.divisor; auto rhs_n = rhs.dividend; auto rns_d = rhs.divisor; auto d = std::lcm(lhs_d, rhs_d); auto n1 = d / lhs_d * lhs_n; auto n2 = d / rhs_d * rhs_n; return n1 <=> n2; }

Strong Ordering

又称强序。在强序关系中,任意的两个值都存在序关系,可以比较大小。序关系为相等的两个值是不可辨别的。强序关系由 std::strong_ordering 表示。例如,整数类型上存在一个强序关系:
int a = 1; int b = 2; int c = 2; std::strong_ordering ordering; ordering = a <=> b; assert(ordering == std::strong_ordering::less); // a < b ordering = b <=> c; assert(ordering == std::strong_ordering::equivalent); // b = c

序关系类

前文提到,三种不同的序关系分别由STL中实现的三个不同的序关系类所表示。这三个类分别是:
  • std::partial_ordering,表示偏序关系;
  • std::weak_ordering,表示弱序关系;
  • std::strong_ordering,表示强序关系。
这三个序关系类具备一些有趣的属性。
首先,由于偏序、弱序、强序所施加的限制条件逐渐增强,因此表示三种序关系的序关系类有如下的隐式类型转换关系:std::strong_ordering 可隐式转换为 std::weak_orderingstd::weak_ordering 可隐式转换为 std::partial_ordering。但是,std::partial_ordering 不能被隐式或显式地转换为 std::weak_orderingstd::weak_ordering 也不能被隐式或显式地转换为std::strong_ordering
另外,这三个序关系类都可以同字面量 0 比较大小。例如:
int a = 10; int b = 20; int c = 20; std::strong_ordering ab = a <=> b; std::strong_ordering ba = b <=> a; std::strong_ordering bc = b <=> c; assert(ab < 0); // OK: ab is std::strong_ordering::less, which < 0 assert(ba > 0); // OK: ba is std::strong_ordering::greater, which > 0 assert(bc == 0); // OK: bc is std::strong_ordering::equivalent, which == 0
能够同字面量 0 比较大小这一特性可以使代码风格更符合类C语言的习惯(类似于 strcmp 函数的返回值)。
事实上,三路比较运算符并非只能返回STL中预定义的这三个序关系类。三路比较运算符可以返回一个满足下列条件的、任意类型的值:
  • (a <=> b) < 0 当且仅当 a < b
  • (a <=> b) == 0 当且仅当 a = b
  • (a <=> b) > 0 当且仅当 a > b
即只要一个类型定义了与字面量 0 的比较运算,这个类型就可以被三路比较运算符返回。

Default Comparisons

自C++20开始,编译器可以开始为七种比较运算符(即 <=><<===!=>= 以及 >)提供默认实现,示例语法如下:
struct IntPair { int first; int second; // Normal member function declaration bool operator<(const IntPair &) const; // Compiler can generate default implementation for non-member operator functions friend bool operator>(const IntPair &, const IntPair &) = default; }; // Compiler can generate default implementation for member operator functions bool IntPair::operator<(const IntPair &) const = default;
可以看到,对于成员运算符和非成员运算符,编译器均支持自动生成。但需要注意到的是,目前各大主流编译器对自动生成非成员运算符的支持尚不统一。不统一的地方主要在于下面这种写法:
struct IntPair { int first; int second; friend bool operator<(const IntPair &, const IntPair &); }; bool operator<(const IntPair &, const IntPair &) = default;
clang 11.0.1 不能编译上述代码片段,因为 clang 要求只能在 class 内部使用 = default 语法为运算符提供默认实现。但 gcc 可以编译上述代码片段。
与特殊成员函数(构造器、析构器等)类似,C++20也支持使用 = delete 语法来标记某个运算符是deleted function。例如:
struct Point { int x; int y; friend bool operator<(const Point &, const Point &) = delete; }; Point a, b; a < b; // Error: `operator<` is deleted
但是显式地将某个运算符定义为 deleted 的意义不大。如果我们不允许使用某个运算符,直接不声明或定义这个运算符即可。
那么编译器如何为各个运算符提供默认实现呢?
首先来看简单的情况。C++20规定:
  • 对于如下五个运算符:<<=>=>, 如果 <=> 没有被定义,则这五个运算符的默认实现即是将它们声明为 deleted;否则,这五个运算符将通过调用并判断 <=> 的返回值以确定两操作数的大小关系。
  • 对于 != 运算符:如果 == 没有被定义,则 != 的默认实现即是将它声明为 deleted;否则,!= 的默认实现将调用 == 并将其返回值逻辑求反作为 != 的返回值。
例如:
struct IntPair { int first; int second; friend std::strong_ordering operator<=>(const IntPair &, const IntPair &) = default; friend bool operator>(const IntPair &, const IntPair &) = default; }; // Compiler will generate something like: bool operator>(const IntPair& lhs, const IntPair& rhs) { return (lhs <=> rhs) > 0; }
按照惯例,编译器(例如 clang)当发现某个运算符的默认实现是将其声明为 deleted 时,可能会给出一个警告。
然后再来看编译器如何生成 == 运算符的默认实现。C++20规定,编译器为 == 运算符生成的默认实现应满足如下的特性:
  • 两个操作数被认为是相等的,当且仅当它们的所有对应的基类子对象以及对应的数据成员全部相等;
  • == 应有短路特性。在效果上,== 应首先按照声明顺序,依次比较两个操作数的所有对应的基类子对象;然后再按照声明顺序,依次比较两个操作数的所有对应的数据成员。只要上述过程中有一个比较的结果是不相等,则后续的比较均不会进行。另外,如果上述过程中有任何两个对象之间不存在合适的 == 重载,则 == 运算符的默认实现将是将它声明为deleted。
例如:
struct Base1 { /* ... */ }; struct Base2 { /* ... */ }; bool operator==(const Base1 &, const Base1 &); bool operator==(const Base2 &, const Base2 &); struct Derived : public Base1, public Base2 { int x; int y; friend bool operator==(const Derived &, const Derived &) = default; }; // Compiler will generate something like this: bool operator==(const Derived& lhs, const Derived& rhs) { // Compare all base class sub-objects. if (!operator==(static_cast<const Base1 &>(lhs), static_cast<const Base1 &>(rhs))) { return false; } if (!operator==(static_cast<const Base2 &>(lhs), static_cast<const Base2 &>(rhs))) { return false; } // Compare all fields. if (lhs.x != rhs.x) { return false; } if (lhs.y != rhs.y) { return false; } return true; }
最后来看编译器如何为 <=> 运算符生成默认实现。
C++20规定,编译器为 <=> 运算符生成的默认实现应该有如下的特性:
  • <=> 的返回值类型使用 traits std::common_comparison_category 进行计算。这个模板类拥有类型成员 type,它给出由所有的模板类型参数指定的序关系的最强公共序关系。<=> 的返回值类型不能比定义在操作数基类和数据成员类型上的 <=> 运算符的返回值类型蕴含更强的序关系。
  • <=> 应该按照声明顺序,依次调用定义在操作数基类以及操作数数据成员上的 <=> 运算符。只要该过程中有某一个比较关系不是等价关系,则返回该关系。否则,返回等价关系。
例如,对于上述第一点:
struct Foo { double x; int y; // Error: `std::strong_ordering` is too strong since `<=>` on `double` yields `std::partial_ordering` friend std::strong_ordering operator<=>(const Foo &, const Foo &) = default; };
对于上述第二点:
struct Base1 { /* ... */ }; struct Base2 { /* ... */ }; std::weak_ordering operator<=>(const Base1 &, const Base1 &); std::strong_ordering operator<=>(const Base2 &, const Base2 &); struct Derived : public Base1, public Base2 { int x; int y; friend std::partial_ordering operator<=>(const Derived &, const Derived &) = default; }; // Compiler will generate something like this: std::partial_ordering operator<=>(const Derived& lhs, const Derived& rhs) { // Compare all base class sub-objects. if (auto cmp = operator<=>(static_cast<const Base1 &>(lhs), static_cast<const Base1 &>(rhs)); cmp != 0) { return cmp; } if (auto cmp = operator<=>(static_cast<const Base2 &>(lhs), static_cast<const Base2 &>(rhs)); cmp != 0) { return cmp; } // Compare all fields. if (auto cmp = (lhs.x <=> rhs.x); cmp != 0) { return cmp; } if (auto cmp = (lhs.y <=> rhs.y); cmp != 0) { return cmp; } return std::partial_ordering::equivalent; }
对于 <=> 的返回值类型,如果在实际运用中由于类型比较复杂,难以准确判断 <=> 的最强的返回值类型,可以使用 auto 作为 <=> 返回值类型,使编译器自动推导最强的返回值类型。例如:
struct Foo { int x; int y; // Return type will be `std::strong_ordering`. friend auto operator<=>(const Foo &, const Foo &) = default; }; struct Bar { double x; int y; // Return type will be `std::partial_ordering`. friend auto operator<=>(const Bar &, const Bar &) = default; };
这个技巧在定义模板类时非常有用。因为在模板类中,我们可能无法知晓模板实例化后模板的基类类型以及数据成员类型:
template <typename T1, typename T2> struct Pair { T1 first; T2 second; // Return type will be deduced when the template is instantiated friend auto operator<=>(const Pair &, const Pair &) = default; }; Pair<int, int> a, b; Pair<double, int> c, d; a <=> b; // Return type is std::strong_ordering c <=> d; // Return type is std::partial_ordering