{"id":5931,"date":"2020-06-25T16:42:27","date_gmt":"2020-06-25T16:42:27","guid":{"rendered":"https:\/\/www.modernescpp.com\/index.php\/c-20-fast-comparison-with-the-spaceship-operator\/"},"modified":"2023-12-06T13:36:20","modified_gmt":"2023-12-06T13:36:20","slug":"c-20-fast-comparison-with-the-spaceship-operator","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/c-20-fast-comparison-with-the-spaceship-operator\/","title":{"rendered":"C++20: Optimized Comparison with the Spaceship Operator"},"content":{"rendered":"

In this post, I conclude my miniseries on the three-way comparison operator with a few subtle details. The subtle details include the compiler-generated ==<\/span> and !=<\/span> operators and the interplay of classical comparison operators, and the three-way comparison operator.<\/p>\n

<\/p>\n

\"TimelineCpp20\"<\/p>\n

I finished my last post, “C++20: More Details to the Spaceship Operator<\/a>” with the following class MyInt<\/span>. In this concrete case, I promised to elaborate more on the difference between an explicit and a non-explicit constructor. The rule of thumb is that a constructor taking one argument should be explicit.<\/p>\n

Explicit Constructor<\/h3>\n

Here is essentially the user-defined type MyInt<\/span> from my last post.<\/p>\n

<\/p>\n

\n
\/\/ threeWayComparisonWithInt2.cpp<\/span>\n\n#include <compare><\/span>\n#include <iostream><\/span>\n\nclass<\/span> MyInt<\/span> {\n public:<\/span>\n    constexpr explicit<\/span> MyInt(int<\/span> val):<\/span> value{val} { }    \/\/ (1)<\/span>\n    \n    auto<\/span> operator<\/span><=><\/span>(const<\/span> MyInt&<\/span> rhs) const<\/span> =<\/span> default<\/span>;  \/\/ (2)<\/span>\n    \n    constexpr auto<\/span> operator<\/span><=><\/span>(const<\/span> int<\/span>&<\/span> rhs) const<\/span> {   \/\/ (3)<\/span>\n        return<\/span> value <=><\/span> rhs;\n    }\n    \n private:<\/span> \n    int<\/span> value;\n};\n\n\nint<\/span> main<\/span>() {\n    \n    std::<\/span>cout <<<\/span> std::<\/span>boolalpha <<<\/span> std::<\/span>endl;\n    \n    constexpr MyInt myInt2011(2011<\/span>);\n    constexpr MyInt myInt2014(2014<\/span>);\n    \n    std::<\/span>cout <<<\/span> \"myInt2011 < myInt2014: \"<\/span> <<<\/span> (myInt2011 <<\/span> myInt2014) <<<\/span> std::<\/span>endl; \/\/ (4)<\/span>\n\n    std::<\/span>cout <<<\/span> \"myInt2011 < 2014: \"<\/span> <<<\/span> (myInt2011 <<\/span> 2014<\/span>) <<<\/span> std::<\/span>endl;           \/\/ (5)<\/span>\n    \n    std::<\/span>cout <<<\/span> \"myInt2011 < 2014.5: \"<\/span> <<<\/span> (myInt2011 <<\/span> 2014.5<\/span>) <<<\/span> std::<\/span>endl;       \/\/ (6)<\/span>\n    \n    std::<\/span>cout <<<\/span> \"myInt2011 < true: \"<\/span> <<<\/span> (myInt2011 <<\/span> true<\/span>) <<<\/span> std::<\/span>endl;           \/\/ (7)<\/span>\n              \n    std::<\/span>cout <<<\/span> std::<\/span>endl;\n              \n}\n<\/pre>\n<\/div>\n
Constructors taking one argument such as (1) are often called conversion constructors because they can generate, such as in this case an instance of MyInt<\/span> from an int<\/span>.<\/p>\n
MyInt<\/span> has an explicit constructor (1), a compiler-generated three-way comparison operator (2), and a user-defined comparison operator for int<\/span>(3).\u00a0 (4) uses the compiler-generated comparison operator for MyInt<\/span>, and (5, 6, and 7) the user-defined comparison operator for int. Thanks to implicit narrowing to int<\/span> (6) and the integral promotion (7), instances of MyInt<\/span> can be compared with double<\/span> values and bool<\/span> values.<\/p>\n
\"threeWayComparisonMyInt\"<\/p>\n
When I make MyInt<\/span> more int<\/span>-like, the benefit of the explicit constructor (1) becomes apparent. In the following example, MyInt<\/span> supports basic arithmetic.<\/p>\n
<\/p>\n
\n
\/\/ threeWayComparisonWithInt4.cpp<\/span>\n\n#include <compare><\/span>\n#include <iostream><\/span>\n\nclass<\/span> MyInt<\/span> {\n public:<\/span>\n    constexpr explicit<\/span> MyInt(int<\/span> val):<\/span> value{val} { }               \/\/ (3)<\/span>\n    \n    auto<\/span> operator<\/span><=><\/span>(const<\/span> MyInt&<\/span> rhs) const<\/span> =<\/span> default<\/span>;  \n    \n    constexpr auto<\/span> operator<\/span><=><\/span>(const<\/span> int<\/span>&<\/span> rhs) const<\/span> {\n        return<\/span> value <=><\/span> rhs;\n    }\n    \n    constexpr friend<\/span> MyInt operator<\/span>+<\/span>(const<\/span> MyInt&<\/span> a, const<\/span> MyInt&<\/span> b){\n        return<\/span> MyInt(a.value +<\/span> b.value);\n    }\n    \n    constexpr friend<\/span> MyInt operator<\/span>-<\/span>(const<\/span> MyInt&<\/span> a,const<\/span> MyInt&<\/span> b){\n        return<\/span> MyInt(a.value -<\/span> b.value);\n    }\n    \n    constexpr friend<\/span> MyInt operator<\/span>*<\/span>(const<\/span> MyInt&<\/span> a, const<\/span> MyInt&<\/span> b){\n        return<\/span> MyInt(a.value *<\/span> b.value);\n    }\n    \n    constexpr friend<\/span> MyInt operator<\/span>\/<\/span>(const<\/span> MyInt&<\/span> a, const<\/span> MyInt&<\/span> b){\n        return<\/span> MyInt(a.value \/<\/span> b.value);\n    }\n    \n    friend<\/span> std::<\/span>ostream&<\/span> operator<\/span><<<\/span> (std::<\/span>ostream &<\/span>out, const<\/span> MyInt&<\/span> myInt){\n        out <<<\/span> myInt.value;\n        return<\/span> out;\n    }\n    \n private:<\/span> \n    int<\/span> value;\n};\n\n\nint<\/span> main<\/span>() {\n    \n    std::<\/span>cout <<<\/span> std::<\/span>boolalpha <<<\/span> std::<\/span>endl;\n    \n    constexpr MyInt myInt2011(2011<\/span>);\n    constexpr MyInt myInt2014(2014<\/span>);\n    \n    std::<\/span>cout <<<\/span> \"myInt2011 < myInt2014: \"<\/span> <<<\/span> (myInt2011 <<\/span> myInt2014) <<<\/span> std::<\/span>endl;\n\n    std::<\/span>cout <<<\/span> \"myInt2011 < 2014: \"<\/span> <<<\/span> (myInt2011 <<\/span> 2014<\/span>) <<<\/span> std::<\/span>endl;\n    \n    std::<\/span>cout <<<\/span> \"myInt2011 < 2014.5: \"<\/span> <<<\/span> (myInt2011 <<\/span> 2014.5<\/span>) <<<\/span> std::<\/span>endl;\n    \n    std::<\/span>cout <<<\/span> \"myInt2011 < true: \"<\/span> <<<\/span> (myInt2011 <<\/span> true<\/span>) <<<\/span> std::<\/span>endl;\n    \n    constexpr MyInt res1 =<\/span> (myInt2014 -<\/span> myInt2011) *<\/span> myInt2011;   \/\/ (1)<\/span>\n    std::<\/span>cout <<<\/span> \"res1: \"<\/span> <<<\/span> res1 <<<\/span> std::<\/span>endl;\n    \n    constexpr MyInt res2 =<\/span> (myInt2014 -<\/span> myInt2011) *<\/span> 2011<\/span>;        \/\/ (2)<\/span>\n    std::<\/span>cout <<<\/span> \"res2: \"<\/span> <<<\/span> res2 <<<\/span> std::<\/span>endl;\n    \n    constexpr MyInt res3 =<\/span> (false<\/span> +<\/span> myInt2011 +<\/span> 0.5<\/span>)  \/<\/span> true<\/span>;     \/\/ (3)<\/span>\n    std::<\/span>cout <<<\/span> \"res3: \"<\/span> <<<\/span> res3 <<<\/span> std::<\/span>endl;\n    \n              \n    std::<\/span>cout <<<\/span> std::<\/span>endl;\n              \n}\n<\/pre>\n<\/div>\n
MyInt<\/span> supports basic arithmetic with objects of type MyInt<\/span> (1) but not basic arithmetic with built-in types such as int <\/span>(2), double<\/span>, or bool<\/span> (3). The error message of the compiler gives an unambiguous message:<\/p>\n
\"threeWayComparisonExplicit\"<\/p>\n
The compiler knows in (2) no conversion from int<\/span> to const MyInt<\/span> and in (3) no conversion form from bool<\/span> to const MyInt<\/span>. A viable way to make an int<\/span>, double<\/span>, or bool<\/span> to const MyInt<\/span> is a non-explicit constructor. Consequently, when I remove the explicit<\/span> keyword from the constructor (1), the implicit conversion kicks in, and the program compiles and produces the surprising result.<\/p>\n
\"threeWayComparisonImplicit\"<\/p>\n
The compiler-generated == and != operators are special for performance reasons.<\/p>\n
Optimized == and != operators<\/h2>\n
I wrote in my first post, “C++20: The Three-Way Comparison Operator<\/a>“, that the compiler-generated comparison operators apply lexicographical comparison. Lexicographical comparison means that all base classes are compared left to right and all non-static members in their declaration order.<\/p>\n
Andrew Koenig<\/a> wrote a comment to my post “C++20: More Details to the Spaceship Operator<\/a>” on the Facebook group C++ Enthusiast, which I want to quote here:<\/p>\n
There\u2019s a potential performance problem with <=> that might be worth mentioning: for some types, it is often possible to implement == and != in a way that potentially runs much faster than <=>.
\nFor example, for a vectorlike or stringlike class, == and != can stop after determining that the two values being compared have different lengths, whereas <=> has to examine elements until it finds a difference. If one value is a prefix of the other, that makes the difference between O(1) and O(n).<\/span><\/p><\/blockquote>\n
I have nothing to add to Andrew’s comment but one observation. The standardization committee was aware of this performance issue and fixed it with the paper P1185R2.\u00a0<\/a> Consequently, the compiler-generated == and != operators compare in the case of a string or a vector first their length and then their content if necessary.<\/p>\n
User-defined and auto-generated Comparison Operators<\/h2>\n
When you can define one of the six comparison operators and auto-generate all of them using the spaceship operator, there is one question: Which one has the higher priority? For example, my new implementation MyInt<\/span> has a user-defined smaller and identity operator, and the compiler-generated six comparison operators.<\/p>\n
Let me see what happens:<\/p>\n
<\/p>\n
\n
\/\/ threeWayComparisonWithInt5.cpp<\/span>\n\n#include <compare><\/span>\n#include <iostream><\/span>\n\nclass<\/span> MyInt<\/span> {\n public:<\/span>\n    constexpr explicit<\/span> MyInt(int<\/span> val):<\/span> value{val} { }\n    bool<\/span> operator<\/span> ==<\/span> (const<\/span> MyInt&<\/span> rhs) const<\/span> {                  \n        std::<\/span>cout <<<\/span> \"==  \"<\/span> <<<\/span> std::<\/span>endl;\n        return<\/span> value ==<\/span> rhs.value;\n    }\n    bool<\/span> operator<\/span> <<\/span> (const<\/span> MyInt&<\/span> rhs) const<\/span> {                  \n        std::<\/span>cout <<<\/span> \"<  \"<\/span> <<<\/span> std::<\/span>endl;\n        return<\/span> value <<\/span> rhs.value;\n    }\n    \n    auto<\/span> operator<\/span><=><\/span>(const<\/span> MyInt&<\/span> rhs) const<\/span> =<\/span> default<\/span>;\n    \n private:<\/span>\n     int<\/span> value;\n};\n\nint<\/span> main<\/span>() {\n    \n    MyInt myInt2011(2011<\/span>);\n    MyInt myInt2014(2014<\/span>);\n    \n    myInt2011 ==<\/span> myInt2014;\n    myInt2011 !=<\/span> myInt2014;\n    myInt2011 <<\/span> myInt2014;\n    myInt2011 <=<\/span> myInt2014;\n    myInt2011 ><\/span> myInt2014;\n    myInt2011 >=<\/span> myInt2014;\n    \n}\n<\/pre>\n<\/div>\n
To see the user-defined ==<\/span> and <<\/span> operators in action,\u00a0 I write a corresponding message to std::cout<\/span>. Both operators cannot be constexpr<\/span> because std::cout<\/span> is a run-time operation.<\/p>\n
The compiler uses the user-defined == and < operators in this case. Additionally, the compiler synthesizes the !=<\/span> operator out of the ==<\/span> operator. The compiler does not synthesize the == operator out of the other.<\/p>\n
This behavior does not surprise me because C++ behaves similarly to Python. In Python 3, the compiler generates != out of == if necessary but not the other way around. In Python 2, the so-called rich comparison (the user-defined six comparison operators) has higher priority than Python’s three-way comparison operator __cmp__<\/span>. I have to say Python 2 because the three-way comparison operator is removed in Python 3.<\/p>\n
What’s next?<\/h2>\n
Designated initialization is a particular case of aggregate initialization and empowers you to initialize the members of a class using their names directly. Designed initializers are my next C++20 topic.<\/p>\n","protected":false},"excerpt":{"rendered":"
In this post, I conclude my miniseries on the three-way comparison operator with a few subtle details. The subtle details include the compiler-generated == and != operators and the interplay of classical comparison operators, and the three-way comparison operator.<\/p>\n","protected":false},"author":21,"featured_media":5199,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[375],"tags":[462],"class_list":["post-5931","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-c-20","tag-spaceship"],"_links":{"self":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5931","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/comments?post=5931"}],"version-history":[{"count":2,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5931\/revisions"}],"predecessor-version":[{"id":8756,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5931\/revisions\/8756"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media\/5199"}],"wp:attachment":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media?parent=5931"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=5931"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=5931"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}