Beginner's Guide
    First Steps
    Input & Output
    Custom Types – Part 1
    Diagnostics
    Standard Library – Part 1
    Function Objects
    Standard Library – Part 2
    Code Organization
    Custom Types – Part 2
    Generic Programming
    Memory Management
    Software Design Basics

    Comparing Custom Types Custom Comparisons Comparing

    Equality: Does A have the same value as B?
    bool operator == ()  // equal
    bool operator != ()  // not equal
    Ordering: Does A go before/after B?
    bool operator <  ()  // smaller
    bool operator <= ()  // smaller equal
    bool operator >  ()  // greater
    bool operator >= ()  // greater equal
    3-Way Comparison
    auto operator <=> ()  // combines == != < <= > >=

    Comparison functions are not automatically generated by the compiler:
    • C++98-17 : we need to manually implement comparison operators
    • C++20 : we can tell the compiler to generate comparison operators for us

    Principles

    C++: Value-Based Comparisons Value/Identity

    = objects are equal/less/… if their (member) values are equal/less/…

    Reminder: C++ uses Value Semantics
    = variables refer to objects themselves, i.e., they are not just references/pointers

    This is the default behavior for fundamental types (int, double, etc.) in almost all programming languages and also the default for user-defined types in C++:

    • deep copying: produces a new, independent object; object (member) values are copied
    • deep assignment: makes value of target equal to that of source object
    • deep ownership: member variables refer to objects with same lifetime as containing object
    • value-based comparison: variables compare equal/less/… if their values are equal/less/…

    Pairwise Value Relations Relations

    Two objects a and b are

    equal, if == b is true,  (their values are the same)
    equivalent, if !(a < b) && !(b < a) is true  (neither one is ordered before the other)
    incomparable, if a < b, b < a and a == b are all false  (unordered)

    Partial Relation: incomparable values are allowed

    Total Relation: at least one of a < b, b < a and a == b must be true for any pair of values

    Comparison-Salient State Salient State

    = members of a type that form its actual value

    • container items: string characters, vector elements, …
    • day, month & year of a 'Date' type
    • numerator & denominator of a 'Fraction' type
    Non-salient members should not take part in comparisons:
    • memory management details: vector capacity, buffer addresses, …
    • execution details: thread handles, mutexes, …
    • value caches: intermediate results, lookup tables, …

    Substitutability

    a == b implies f(a) == f(b),

    a < b implies f(a) < f(b), etc.

    i.e., if a is equal/equivalent to b, then f(a) is also equal/equivalent to f(b) as long as function f reads only comparison-salient state.

    std::string a = "123";
    std::string b = "123";  // same value as a
    int fa = std::stoi(a);  // string → int
    int fb = std::stoi(b);
    if (a == b) { /* then we expect fa == fb */ }

    Equality Comparisons Equality Equality

    bool operator == (T const& a, T const& b);
    bool operator != (T const& a, T const& b);

    Manual Definition Manual

    class irange {
      int min_; int max_;
    public:   explicit constexpr
      irange(int min, int max) noexcept:     min_{min}, max_{max} {
        if(min_ > max_) std::swap(min_, max_);
      }
      int min() const noexcept { return min_; }
      int max() const noexcept { return max_; }
      friend bool operator ==   (irange const& l, irange const& r) noexcept {   
        return l.min() == r.min() &&            l.max() == r.max();
      }
      friend bool operator !=   (irange const& l, irange const& r) noexcept {   
        return !(l == r);  // reuse operator==
      }
    };
    int main() {
      irange r1 { 0,10};
      irange r2 {20,30};
      if(r1 == r2) {  }  // false
      if(r1 != r2) {  }  // true
    }

    Defaulted Definition Defaulted

    class irange {
      int min_; int max_;
    public:   explicit constexpr
      irange(int min, int max) noexcept:     min_{min}, max_{max} {
        if(min_ > max_) std::swap(min_, max_);
      }
      int min() const noexcept { return min_; }
      int max() const noexcept { return max_; }
      bool operator ==   (irange const&) const  = default;
    };
    • compiler generates recursive comparison of all members
    • no need to define operator!=, compiler will rewrite call a != b as !(a == b) if necessary
    • we can just use a member function declaration that only takes one right hand side parameter
    • requires that every member is == comparable

    Comparing Between Different Types Comparing Different Types Diff.Types

    However, in rare cases it can be justified, e.g., when two different types express values of the same underlying domain, e.g., two different integer types expressing values in the same range.

    A a;
    if(a == a) {  }
    B b;
    if(a == b) {  }
    if(b == a) {  }
    C++98-17  one operator function for each combination needed: C++17
    class B {  };
    class A { public: 
      // symmetric
      friend bool operator ==   (A const& a1, A const& a2) noexcept {  }
      // asymmetric
      friend bool operator ==   (A const& a, B const& b) noexcept {  }
      friend bool operator ==   (B const& a, A const& b) noexcept {  }
      
    };
    C++20  only one operator (member) function per type pair needed: C++20
    class B {  };
    class A { public: 
      // symmetric
      bool operator ==   (A const& a) const noexcept {  }  // or = default;
      // asymmetric - either one member:
      bool operator ==   (B const& b) const noexcept {  }
      // or one free-standing function:
      friend bool operator ==   (A const& a, B const& b) noexcept {  }
      
    };

    compiler rewrites a call a == b as b == a if necessary

    Implementing operator== / != Guidelines

    • Reflexivity: a == a must be true
    • Symmetry: results of a == b and b == a must be the same
    • Transitivity: if a == b and b == c are both true then a == c must be true
    • case-insensitive string comparison (ignores letter case)
    • order of magnitude float comparison (ignores mantissa)
    • punctuation-ignoring text comparison
    • compare_case_insensitive
    • same_order_of_magnitude
    • same_excluding_punctuation
    • container items: string characters, vector elements, …
    • day, month & year of a 'Date' type
    • numerator & denominator of a 'Fraction' type
    • memory management details: vector capacity, buffer addresses, …
    • execution details: thread handles, mutexes, …
    • value caches: intermediate results, lookup tables, …

    std::string a = "xyz";
    std::string b = a;  // copy of a
    if (a == b) { /* then OK */ }

    std::string a = "xyz";
    std::string b = "xyz";  // same value as a
    a[1] = "W";  // <-- 
    if (a != b) { /* then OK */ }

    If a is equal to b, then f(a) should also be equal to f(b) as long as function f reads only comparison-salient state.

    std::string a = "123";
    std::string b = "123";  // same value as a
    int fa = std::stoi(a);  // string → int
    int fb = std::stoi(b);
    if (a == b) { /* then we expect fa == fb */ }
    • compare size (= number of elements) of a container (vector,string,map,set,…) before comparing all individual elements
    • compare house numbers and streets before comparing cities of addresses
    • compare first names of persons before comparing last names
    • could use cheap hash comparison (e.g. using a bloom filter) before comparing all data
    // implement it in terms of operator==
    friend bool operator !=   (A const& l, A const& r) { 
      return !(l == r);
    }

    C++20 only needs operator == because compiler rewrites call a != b as !(a == b)

    • Comparisons must always be read-only operations

      • no out-of-memory errors
      • no file access errors
    • No problem, if (part) of a value is not available (e.g., internal memory buffer not yet allocated, file not opened, …)

      • both values not available ⇒ equal
      • one value available, one not available ⇒ not equal
      • both values available ⇒ compare values

    Ordering Comparisons Ordering Ordering

    bool operator <  (T const& a, T const& b);
    bool operator <= (T const& a, T const& b);
    bool operator >  (T const& a, T const& b);
    bool operator >= (T const& a, T const& b);

    Example: Comparable Date Example: Date Example

    enum class month { jan = 1, feb = 2, , dec = 12 };
    struct date {
      int yyyy;   month mm;   int dd; 
      friend bool operator <   (date const& l, date const& r) noexcept {
        if(l.yyyy < r.yyyy) return true;
        if(l.yyyy > r.yyyy) return false;
        if(l.mm < r.mm) return true;
        if(l.mm > r.mm) return false;
        if(l.dd < r.dd) return true;
        return false;
      }
      // more ordering operators 
      friend bool operator <= (  ) {  }
      friend bool operator >  (  ) {  }
      friend bool operator >= (  ) {  }
      // equality comparison operators 
      friend bool operator == (  ) {  }
      friend bool operator != (  ) {  }
    };
    
    int main() { date earlier {2017, month::dec, 24}; date later {2018, month::may, 12}; if(earlier < later) { }; // true }

    Comparing Between Different Types Comparing Different Types Diff.Types

    However, in rare cases it can be justified, e.g., when two different types express values of the same underlying domain, e.g., two different integer types expressing values in the same range.

    A a;
    if(a < a) {  }
    B b;
    if(a < b) {  }
    if(b < a) {  }
    C++98-17  one operator function for each combination needed: C++17
    class B {  };
    class A { public: 
      // symmetric
      friend bool operator <   (A const& a1, A const& a2) noexcept {  }
      // asymmetric
      friend bool operator <   (A const& a, B const& b) noexcept {  }
      friend bool operator <   (B const& a, A const& b) noexcept {  }
      
    };
    C++20  only one operator (member) function per type pair needed: C++20
    class B {  };
    class A { public: 
      // symmetric
      bool operator <   (A const& a) const noexcept {  }  // or = default;
      // asymmetric - either one member:
      bool operator <   (B const& b) const noexcept {  }
      // or one free-standing function:
      friend bool operator <   (A const& a, B const& b) noexcept {  }
      
    };

    compiler rewrites a call a < b as b < a if necessary

    Prefer to implement just C++20's operator <=> instead of individual ordering operators.

    Implementing Ordering Operators Ordering Operators? Guidelines

    Example: We should not provide an ordering for a type that models an interval (like irange )!

    What could it mean that interval A is less than, i.e., should be ordered before interval B?

    • only the left bound of A could be smaller than the left bound of B,
    • both bounds of A could be smaller than the left bound of B,
    • or A could have a smaller width (max-min) than B.
    • ambiguous interface
    • code that uses such an ordering would be confusing and error-prone
    struct Box {
      int id; 
      double weight;
      Location origin;
      Location target;
    };
    auto heaviest(std::vector<Box> const& v) {
      return max_element(begin(v), end(v), 
        [](Box const& a, Box const& b){         return a.weight < b.weight;     });
    }

    Everyone – including yourself – expects that if a < b compiles, then b > a does also compile.

    Incomplete implementation of ordering operators will almost certainly lead to countless situations where you or users of your type have to waste time on diagnosing compiler errors.

    Providing only strict comparisons < and > but not <= and >= can be justified in very rare situations, but only if you don't provide == and != as well.

    • if a <= b compiles, then a < b || a == b should also compile
    • if a >= b compiles, then a > b || a == b should also compile
    • a <= b and a < b || a == b should give the same answer
    • a >= b and a > b || a == b should give the same answer
    • Comparisons must always be read-only operations

      • no out-of-memory errors
      • no file access errors
    • No problem, if (part) of a value is not available (e.g., internal memory buffer not yet allocated, file not opened, …)

      • both values not available ⇒ equal
      • one value available, one not available ⇒ not equal
      • both values available ⇒ compare values

    3-Way Comparisons  C++20 3-Way  C++20 3-Way C++20

    Spaceship Operator <=> operator<=>

    (a <=> b) < 0 if a < b
    (a <=> b) > 0 if a > b
    (a <=> b) == 0 if a and b are equal/equivalent
    category equivalent values incomparable values
    std::strong_ordering are indistinguishable (truly equal) forbidden
    std::weak_ordering can be distiguished forbidden
    std::partial_ordering can be distiguished allowed
    • 4 <=> 6 →  strong_ordering::less
      5 <=> 5 →  strong_ordering::equal
      8 <=> 1 →  strong_ordering::greater

    • are partially ordered, because of incomparable "Not A Number" values for representing division-by-zero, overflow, etc. (e.g., IEEE 754 silent+signalling NaNs)

      4.1 <=> 6.3 →  partial_ordering::less
      5.2 <=> 5.2 →  partial_ordering::equivalent
      8.3 <=> 1.4 →  partial_ordering::greater

    • "ab"s <=> "bc"s →  strong_ordering::less
      "ab"s <=> "ab"s →  strong_ordering::equal
      "bc"s <=> "ab"s →  strong_ordering::greater

    If one of the boolean comparison operators ==, !=, <, <=, > or >= is not found, the compiler will rewrite the call expression in terms of <=> if necessary:

    • a == b can be rewritten as (a <=> b) == 0
    • a != b can be rewritten as (a <=> b) != 0
    • a < b can be rewritten as (a <=> b) < 0
    • a > b can be rewritten as (a <=> b) > 0
    • a <= b can be rewritten as (a <=> b) <= 0
    • a >= b can be rewritten as (a <=> b) >= 0

    ⇒ in C++20 we only need to provide either only operator== for equality-comparable types without an ordering or only operator<=> for orderable types

    Defaulted Definition Defaulted <=>

    #include <compare>
    enum class month { jan = 1, feb = 2, , dec = 12 };
    struct date {
      int yyyy;   month mm;   int dd; 
      auto operator <=> (date const&) const   = default;
    }

    The default operator <=> recursively compares all data members in order of declaration.

    int main() {
      date earlier {2017, month::dec, 24};
      date later   {2018, month::may, 12};
      if(earlier < later) {  }  // true
      if(earlier > later) {  }  // false
      auto cmp = (earlier <=> later); 
      if(cmp < 0)  {  }  // true
      if(cmp == 0) {  }  // false
      if(cmp > 0)  {  }  // false
    }

    Manual Definition Manual <=>

    #include <compare>
    enum class month { jan = 1, feb = 2, , dec = 12 };
    struct date {
      int yyyy;   month mm;   int dd; 
      auto operator <=> (date const& o)   const noexcept {
        // use built-in <=>; for ints & enums
        if(auto cmp = yyyy <=> o.yyyy;        cmp != 0) { return cmp; }
        if(auto cmp = mm   <=> o.mm;          cmp != 0) { return cmp; }
        return dd <=> o.dd;
      }
    };

    Comparison Categories Comparison Categories Category

    Category Possible Values
    :: less, greater, equivalent, equal
    :: less, greater, equivalent
    :: less, greater, equivalent, unordered

    less a before b
    greater a after b
    equivalent a neither before nor after b
    equal a is the same as b
    unordered a not comparable with b

    std::strong_ordering Strong

    Values: less, greater, equal, equivalent (same as equal)

    • equivalent values are indistinguishable (they are truly equal)
    • all values must be comparable
    class A {
      M m_;
    public: 
      std::strong_ordering
      operator <=> (A const& rhs) const noexcept { 
        if(m_ == rhs.m_)       return strong_ordering::equal;
        if(m_ <  rhs.m_)       return strong_ordering::less;
        return strong_ordering::greater;
      }
    };

    std::weak_ordering Weak

    Values: less, greater, equivalent

    • can distinguish equivalent values
    • all values must be comparable
    • case-insensitive string comparison ('aBc' and 'ABC' are equivalent, but can be distinguished)
    • order of magnitude float comparison (30 and 50 are equivalent, but can be distinguished)
    std::weak_ordering compare_case_insensitive (std::string const&, std::string const&) noexcept {  }
    
    std::weak_ordering compare_order_of_magnitude (float, float) noexcept {  }

    std::partial_ordering Partial

    Values: less, greater, equivalent, unordered

    • can distinguish equivalent values
    • incomparable values are allowed
    • number types with an incomparable "Not A Number" value (for representing division-by-zero, overflow, etc.), e.g., IEEE 754 NaNs (may be used for float, double, long double)
    • tree node adjacency: child less than parent, parent greater than child, equivalent = same node, unordered = nodes not adjacent
    std::partial_ordering compare_adjacency (TreeNode const&, TreeNode const&) noexcept {  }

    Implementing Orderings Guidelines

    Example: We should not provide an ordering for a type that models an interval (like irange )!

    What could it mean that interval A is less than, i.e., should be ordered before interval B?

    • only the left bound of A could be smaller than the left bound of B,
    • both bounds of A could be smaller than the left bound of B,
    • or A could have a smaller width (max-min) than B.
    • ambiguous interface
    • code that uses such an ordering would be confusing and error-prone
    struct Box {
      int id; 
      double weight;
      Location origin;
      Location target;
    };
    auto heaviest(std::vector<Box> const& v) {
      return max_element(begin(v), end(v), 
        [](Box const& a, Box const& b){         return a.weight < b.weight;     });
    }
    std::weak_ordering compare_case_insensitive (std::string const&, std::string const&) noexcept {  }
    
    std::weak_ordering compare_order_of_magnitude (float, float) noexcept {  }
    std::partial_ordering compare_adjacency (TreeNode const&, TreeNode const&) noexcept {  }

    This avoids duplicated code that could diverge when someone forgets to change all operators at the same time.

    Subtle runtime bugs caused by e.g., a forgotten member comparison in only one operator but not in the others will be hard to diagnose!

    • a <= b and a < b || a == b should give the same answer
    • a >= b and a > b || a == b should give the same answer
    • Comparisons must always be read-only operations

      • no out-of-memory errors
      • no file access errors
    • No problem, if (part) of a value is not available (e.g., internal memory buffer not yet allocated, file not opened, …)

      • both values not available ⇒ equal
      • one value available, one not available ⇒ not equal
      • both values available ⇒ compare values