C++20: Optimized Comparison with the Spaceship Operator

Contents[Show]

In this post, I conclude my miniseries to the three-way comparison operator with a few subtle details. The subtle details include the compiler-generated the == and != operators and the interplay of classical comparison operators and the three-way comparison operator.

 

TimelineCpp20

I finished my last post "C++20: More Details to the Spaceship Operator" with the following class MyInt. I promised to elaborate more on the difference between an explicit and a non-explicit constructor in this concrete case. The rule of thumb is that a constructor taking one argument should be explicit.

Explicit Constructor

Here is essentially the user-defined type MyInt from my last post.

// threeWayComparisonWithInt2.cpp

#include <compare>
#include <iostream>

class MyInt {
 public:
    constexpr explicit MyInt(int val): value{val} { }    // (1)
    
    auto operator<=>(const MyInt& rhs) const = default;  // (2)
    
    constexpr auto operator<=>(const int& rhs) const {   // (3)
        return value <=> rhs;
    }
    
 private: 
    int value;
};


int main() {
    
    std::cout << std::boolalpha << std::endl;
    
    constexpr MyInt myInt2011(2011);
    constexpr MyInt myInt2014(2014);
    
    std::cout << "myInt2011 < myInt2014: " << (myInt2011 < myInt2014) << std::endl; // (4)

    std::cout << "myInt2011 < 2014: " << (myInt2011 < 2014) << std::endl;           // (5)
    
    std::cout << "myInt2011 < 2014.5: " << (myInt2011 < 2014.5) << std::endl;       // (6)
    
    std::cout << "myInt2011 < true: " << (myInt2011 < true) << std::endl;           // (7)
              
    std::cout << std::endl;
              
}

Constructor taking one argument such as (1) are often called conversion constructor because they can generate such as in this case an instance of MyInt from an int.

MyInt has an explicit constructor (1), a compiler-generated three-way comparison operator (2), and a user-defined comparison operator for int(3).  (4) uses the compiler-generated comparison operator for MyInt, and (5,6, and 7) the user-defined comparison operator for int. Thanks to implicit narrowing to int (6) and the integral promotion (7), instances of MyInt can be compared with double values and bool values.

threeWayComparisonMyInt

When I make MyInt more int-like such, the benefit of the explicit constructor (1) becomes obvious. In the following example, MyInt supports basic arithmetic.

 

// threeWayComparisonWithInt4.cpp

#include <compare>
#include <iostream>

class MyInt {
 public:
    constexpr explicit MyInt(int val): value{val} { }               // (3)
    
    auto operator<=>(const MyInt& rhs) const = default;  
    
    constexpr auto operator<=>(const int& rhs) const {
        return value <=> rhs;
    }
    
    constexpr friend MyInt operator+(const MyInt& a, const MyInt& b){
        return MyInt(a.value + b.value);
    }
    
    constexpr friend MyInt operator-(const MyInt& a,const MyInt& b){
        return MyInt(a.value - b.value);
    }
    
    constexpr friend MyInt operator*(const MyInt& a, const MyInt& b){
        return MyInt(a.value * b.value);
    }
    
    constexpr friend MyInt operator/(const MyInt& a, const MyInt& b){
        return MyInt(a.value / b.value);
    }
    
    friend std::ostream& operator<< (std::ostream &out, const MyInt& myInt){
        out << myInt.value;
        return out;
    }
    
 private: 
    int value;
};


int main() {
    
    std::cout << std::boolalpha << std::endl;
    
    constexpr MyInt myInt2011(2011);
    constexpr MyInt myInt2014(2014);
    
    std::cout << "myInt2011 < myInt2014: " << (myInt2011 < myInt2014) << std::endl;

    std::cout << "myInt2011 < 2014: " << (myInt2011 < 2014) << std::endl;
    
    std::cout << "myInt2011 < 2014.5: " << (myInt2011 < 2014.5) << std::endl;
    
    std::cout << "myInt2011 < true: " << (myInt2011 < true) << std::endl;
    
    constexpr MyInt res1 = (myInt2014 - myInt2011) * myInt2011;   // (1)
    std::cout << "res1: " << res1 << std::endl;
    
    constexpr MyInt res2 = (myInt2014 - myInt2011) * 2011;        // (2)
    std::cout << "res2: " << res2 << std::endl;
    
    constexpr MyInt res3 = (false + myInt2011 + 0.5)  / true;     // (3)
    std::cout << "res3: " << res3 << std::endl;
    
              
    std::cout << std::endl;
              
}

 

MyInt supports basic arithmetic with objects of type MyInt (1), but not basic arithmetic with built-in types such as int (2), double, or bool (3). The error message of the compiler gives an unambiguous message:

threeWayComparisonExplicit

The compiler knows in (2) no conversion from int to const MyInt and in (3) no conversion form from bool to const MyInt. A viable way to make an int, double, or bool to const MyInt is a non-explicit constructor. Consequently, when I remove the explicit keyword from the constructor (1), the implicit conversion kicks in, the program compiles and produces the surprising result.

threeWayComparisonImplicit

The compiler-generated == and != operators are special for performance reasons.

Optimized == and != operators

I wrote in my first post "C++20: The Three-Way Comparison Operator", 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 of the class in their declaration order. 

Andrew Koenig wrote a comment to my post "C++20: More Details to the Spaceship Operator" on the Facebook group C++ Enthusiast, which I want to quote here:

There’s 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 <=>.
For 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).

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.  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.

User-defined and auto-generated Comparison Operators

When you can define one of the six comparison operators and also 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 has a user-defined smaller and identity operator and also the compiler-generated six comparison operators.

Let me see, what happens:

// threeWayComparisonWithInt5.cpp

#include <compare>
#include <iostream>

class MyInt {
 public:
    constexpr explicit MyInt(int val): value{val} { }
    bool operator == (const MyInt& rhs) const {                  
        std::cout << "==  " << std::endl;
        return value == rhs.value;
    }
    bool operator < (const MyInt& rhs) const {                  
        std::cout << "<  " << std::endl;
        return value < rhs.value;
    }
    
    auto operator<=>(const MyInt& rhs) const = default;
    
 private:
     int value;
};

int main() {
    
    MyInt myInt2011(2011);
    MyInt myInt2014(2014);
    
    myInt2011 == myInt2014;
    myInt2011 != myInt2014;
    myInt2011 < myInt2014;
    myInt2011 <= myInt2014;
    myInt2011 > myInt2014;
    myInt2011 >= myInt2014;
    
}

 

To see the user-defined == and < operator in action,  I write a corresponding message to std::cout. Both operators cannot be constexpr because std::cout is a run-time operation.

comparison

In this case, the compiler uses the user-defined == and < operator. Additionally, the compiler synthesizes the != operator out of the == operator. The compiler does not synthesize the == operator out of the != operator.

This behavior does not surprise me, because C++ behaves similar 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__. I have to say Python 2 because the three-way comparison operator is removed in Python 3.

What's next?

Designated initialization is a special case of aggregate initialization and empowers you to directly initialize the members of a class using their names. Designed initializers are my next C++20 topic.

 

Thanks a lot to my Patreon Supporters: Meeting C++, Matt Braun, Roman Postanciuc, Venkata Ramesh Gudpati, Tobias Zindl, Marko, G Prvulovic, Reinhold Dröge, Abernitzke, Frank Grimm, Sakib, Broeserl, António Pina, Darshan Mody, Sergey Agafyin, Андрей Бурмистров, Jake, GS, Lawton Shoemake, Animus24, Jozo Leko, John Breland, espkk, Wolfgang Gärtner, Jon Hess, Christian Wittenhorst, Louis St-Amour, Stephan Roslen, Venkat Nandam, Jose Francisco, Douglas Tinkham, Lakshman, Kuchlong Kuchlong, and Avi Kohn.

 

Thanks in particular to: Bitwyre Technologies

 

Thanks in particular to:   crp4

 

Seminars

I'm happy to give online-seminars or face-to-face seminars world-wide. Please call me if you have any questions.

Bookable Seminars (Online)

Standard Seminars 

Here is a compilation of my standard seminars. These seminars are only meant to give you a first orientation.

Contact Me

Modernes C++,

RainerGrimmSmall

My Newest E-Books

Course: Modern C++ Concurrency in Practice

Course: C++ Standard Library including C++14 & C++17

Course: Embedded Programming with Modern C++

Course: Generic Programming (Templates)

Course: C++ Fundamentals for Professionals

Subscribe to the newsletter (+ pdf bundle)

Blog archive

Source Code

Visitors

Today 9770

Yesterday 13046

Week 30672

Month 170433

All 4620525

Currently are 149 guests and no members online

Kubik-Rubik Joomla! Extensions

Latest comments