Spaceship operator on arrays

Question

The following code is intended to implement comparison on an object that contains an array. Two objects should compare as <,==,> if all array elements compare like that. The following does not compile for a variety of reason:

#include <compare>
class witharray {
private:
  array<int,4> the_array;
public:
  witharray( array<int,4> v )
    : the_array(v) {};
  int size() { return the_array.size(); };
  auto operator<=>( const witharray& other ) const {
    array< std::strong_ordering,4 > cmps;
    for (int id=0; id<4; id++)
      cmps[id] = the_array[id]<=>other.the_array[id];
    return accumulate
      (cmps.begin(),cmps.end(),
       std::equal,
       [] (auto x,auto y) -> std::strong_ordering { return x and y; }
       );
  };
};

First of all, the array of comparisons:

call to implicitly-deleted default constructor of 'array<std::strong_ordering, 4>

Then the attempt to accumulate the comparisons:

no matching function for call to 'accumulate'

Compiler explorer: https://godbolt.org/z/E3ovh5qGa

Or am I completely on the wrong track?

Answer 1

Two objects should compare as <,==,> if all array elements compare like that.

This is a fairly interesting order. One thing to note here is that it's a partial order. That is, given {1, 2} vs {2, 1}, those elements aren't all < or == or >. So you're left with unordered.

C++20's comparisons do have a way to represent that: you have to return a std::partial_ordering.

The way that we can achieve this ordering is that we first compare the first elements, and then we ensure that all the other elements compare the same. If any pair of elements doesn't compare the same, then we know we're unordered:

auto operator<=>( const witharray& other ) const
    -> std::partial_ordering
{
    std::strong_ordering c = the_array[0] <=> other.the_array[0];
    for (int i = 1; i < 4; ++i) {
        if ((the_array[i] <=> other.the_array[i]) != c) {
            return std::partial_ordering::unordered;
        }
    }
    return c;
}

This has the benefit of not having to compare every pair of elements, since we might already know the answer by the time we get to the 2nd element (e.g. {1, 2, x, x} vs {1, 3, x, x} is already unordered, doesn't matter what the other elements are).

This seems like what you were trying to accomplish with your accumulate, except accumulate is the wrong algorithm here since we want to stop early. You'd want all_of in this case:

auto comparisons = views::iota(0, 4)
    | views::transform([&](int i){
        return the_array[i] <=> other.the_array[i];
    });
bool all_match = ranges::all_of(comparisons | drop(1), [&](std::strong_ordering c){
    return c == comparisons[0];
});
return all_match ? comparisons[0] : std::partial_ordering::unordered;

Which is admittedly awkward. In C++23, we can do the comparisons part more directly:

auto comparisons = views::zip_transform(
    compare_three_way{}, the_array, other.the_array);

And then it would read better if you had a predicate like:

bool all_match = ranges::all_of(comparisons | drop(1), equals(comparisons[0]));

or wrote your own algorithm for this specific use-case (which is a pretty easy algorithm to write):

return all_same_value(comparisons)
    ? comparisons[0]
    : std::partial_ordering::unordered;