# Implementing span's comparisons

One of the new types in C++20 is `std::span<T>`

(with its fixed-
size counterpart `std::span<T, N>`

). This is a very useful type,
since it’s a type-erased view onto a contiguous range - but unlike more typical
type erasure (e.g. `std::function`

), there’s no overhead. I’ve
previous written about `span`

here.

In the initial design, `std::span<T>`

had comparison operators
that performed a *deep comparison*. Those operators were subsequently removed.
I think that removal was a mistake, since these operators are very useful (as in,
we have a `span`

-like type in our codebase and we use these operators), but this
blog isn’t going to be about why they were removed or why they should be added
back.

Instead, this blog is about *how* to implement span’s comparison operators, since
I think that is interesting and demonstrates a bunch of C++20 features all in
one go. You can jump straight to the C++20 implementation here or you
can just directly add it to your code base using my `span_ext`

repo
here.

### Design

Let’s start with a quick design. Before we start implementing comparisons, we have
to decide what we’re going to allow comparing to. Here are six types that a
`std::span<int>`

could hypothetically be comparable with:

`std::span<int>`

`std::span<int const>`

`std::span<long>`

`std::vector<int>`

`std::list<int>`

`std::vector<long>`

I started with `span<int>`

as zero because that goes without
saying. `span<int const>`

should also work, since `const`

-ness
should not play in comparisons.

For the rest, I would argue that `std::vector<int>`

should be
comparable but neither `std::list<int>`

nor `std::vector<long>`

nor `std::span<long>`

should be. My position is that span’s comparisons should behave like a glorified
`memcmp`

- and it should only be directly comparable with other contiguous ranges
of the same type.

That is, the nice syntax (`==`

) only is allowed for the direct,
likely-to-be-valid comparisons. For everything else, if you really want to
compare a `std::span<int>`

to a `std::list<long>`

,
you can use `std::ranges::equal`

.

This is actually different from the span paper, where
the defined comparisons where that `std::span<T>`

was only
comparable to `std::span<U>`

. But, in my opinion, it makes a lot
more sense to compare a `std::span<int>`

to a
`std::vector<int>`

than to a `std::span<long>`

.
While mixed-category comparisons can get you in trouble, here they’re not *really* different categories -
and this lets us write `s == v`

instead of
`s == std::span(v)`

(using CTAD, and note that this conversion
is basically free compared to the comparison).

### Implementation in C++17

Given that design, how would we go about implementing it? (If you want, you can skip to the C++20 implementation).

We want to allow cross-type comparisons, and we want to of course allow them
in both directions. We don’t want to be in a position where `s == v`

compiles but `v == s`

does not compile or, worse, compiles
and does something different.

Ignoring constraints for now, that means we’re starting with (also I’m
omiting `constexpr`

for slide-ware):

```
namespace std {
template <typename T, size_t Extent=dynamic_extent>
class span { /* ... */ };
template <typename T, size_t Extent, typename R>
bool operator==(span<T, Extent> lhs,
R const& rhs) {
// we don't have to bring in namespace std here since
// we're already in namespace std. But qualified call
// to std::equal to avoid ADL shenanigans
return std::equal(begin(lhs), end(lhs),
begin(rhs), end(rhs));
}
template <typename T, size_t Extent, typename R>
bool operator==(R const& lhs,
span<T, Extent> rhs) {
return rhs == lhs;
}
// and != overloads that just call ==
template <typename T, size_t Extent, typename R>
bool operator!=(span<T, Extent> lhs, R const& rhs) {
return !(lhs == rhs);
}
template <typename T, size_t Extent, typename R>
bool operator!=(R const& lhs, span<T, Extent> rhs) {
return !(rhs == lhs);
}
// ... and <, <=, >, >=
}
```

The actual implementation for a specific comparison operator is trivial - we
have algorithms for those. Think about how you would implement `operator<`

.

This puts us at 12 operators. Tedious, and we’re missing constraints (that would need to be duplicated everywhere), but are we done? What happens when I just write:

```
std::span<int> x = /* ... */;
std::span<int> y = /* ... */;
bool check = (x == y);
```

This is the simplest case, right? Just same-type comparison. Here’s the error message we get from gcc trunk:

```
<source>:18:17: error: ambiguous overload for 'operator==' (operand types are 'std::span<int>' and 'std::span<int>')
18 | bool check = (x == y);
| ~ ^~ ~
| | |
| | span<[...]>
| span<[...]>
<source>:10:20: note: candidate: 'bool std::operator==(std::span<T, Extent>, const R&) [with T = int; long unsigned int Extent = 18446744073709551615; R = std::span<int>]'
10 | bool operator==(span<T, Extent> lhs, R const& rhs);
| ^~~~~~~~
<source>:13:20: note: candidate: 'bool std::operator==(const R&, std::span<T, Extent>) [with T = int; long unsigned int Extent = 18446744073709551615; R = std::span<int>]'
13 | bool operator==(R const& rhs, span<T, Extent> lhs);
| ^~~~~~~~
```

That is a great error message. The problem is - we have two `operator==`

candidates. One is a template on the left argument and one is a template on the
right argument, both are viable, and neither is any more specialized than the other.

How do we fix this?

One way to fix this is to just… add more overloads! Add a third candidate for
`operator==`

that is just comparison two spans:

```
namespace std {
template <typename T, size_t Extent=dynamic_extent>
class span { /* ... */ };
template <typename T, size_t Extent, typename R>
bool operator==(span<T, Extent> lhs, R const& rhs);
template <typename T, size_t Extent, typename R>
bool operator==(R const& lhs, span<T, Extent> rhs);
template <typename T, size_t E1, size_t E2>
bool operator==(span<T, E1>, span<T, E2>);
}
```

Here, the *extents* can be different but the types must be the same. And this
works. Indeed, by design, since we’re only comparing contiguous things, we can
even funnel both generic range comparison operators to the span specific one,
so that a solution of `operator==`

(with proper constraints)
could be:

```
#define REQUIRES(...) std::enable_if_t<\
(__VA_ARGS__), int> = 0
// check if we can compare two Ts
template <typename T>
inline constexpr bool equality_comparable_v =
std::is_invocable_v<std::equal_to<>,
T const&, T const&> &&
std::is_invocable_v<std::not_equal_to<>,
T const&, T const&>;
namespace std {
template <typename T, size_t Extent=dynamic_extent>
class span { /* ... */ };
template <typename T, size_t E1, size_t E2,
REQUIRES(equality_comparable_v<T>)>
bool operator==(span<T, E1> lhs, span<T, E2> rhs) {
// could even check if E1/E2 are different
// fixed extents, return false
return std::equal(
lhs.begin(), lhs.end(),
rhs.begin(), rhs.end());
}
template <typename T, size_t E, typename R,
REQUIRES(equality_comparable_v<T> &&
std::is_constructible_v<span<T>, R const&>)>
bool operator==(span<T, E> lhs, R const& rhs) {
return lhs == std::span<T>(rhs);
}
template <typename T, size_t E, typename R,
REQUIRES(equality_comparable_v<T> &&
std::is_constructible_v<span<T>, R const&>)>
bool operator==(R const& lhs, span<T, E> rhs) {
return rhs == std::span<T>(lhs);
}
}
```

This solves the comparison problem we had earlier. Now all we need to do is repeat this for every other comparison operator, for a grand total of… 18. 18 comparison operators! Of which, two actually do work and the other 16 just forward onto those two. Cool? Seems unsatisfying.

Also, does this even work?

Actually, no. While this lets me compare a `span<int>`

to a
`span<int>`

, which would be the bare minimum requirement anyway,
it doesn’t even let me compare a `span<int>`

to a
`span<int const>`

. Nor actually, with the constraints I added
above, does it let me compare a `span<int>`

to a `vector<int>`

because `span<int>`

is not constructible from a
`vector<int> const&`

!

Both of those are fixable by introducing the new constraint `sameish`

: two types
are the *sameish* if they’re the same after removing `const`

-ness
(`int`

and `int const`

aren’t the same - but they’re
the same…ish).

```
#define REQUIRES(...) std::enable_if_t<\
(__VA_ARGS__), int> = 0
// check if we can compare two Ts
template <typename T>
inline constexpr bool equality_comparable_v =
std::is_invocable_v<std::equal_to<>,
T const&, T const&> &&
std::is_invocable_v<std::not_equal_to<>,
T const&, T const&>;
template <typename T, typename U>
inline constexpr bool sameish =
std::is_same_v<std::remove_cv_t<T>,
std::remove_cv_t<U>>;
namespace std {
template <typename T, size_t Extent=dynamic_extent>
class span { /* ... */ };
template <typename T, size_t E1, typename U, size_t E2,
REQUIRES(sameish<T, U> && equality_comparable_v<T>)>
bool operator==(span<T, E1> lhs, span<U, E2> rhs) {
return std::equal(
lhs.begin(), lhs.end(),
rhs.begin(), rhs.end());
}
template <typename T, size_t E, typename R,
REQUIRES(equality_comparable_v<T> &&
std::is_constructible_v<span<T const>,
R const&>)>
bool operator==(span<T, E> lhs, R const& rhs) {
return lhs == std::span<T const>(rhs);
}
template <typename T, size_t E, typename R,
REQUIRES(equality_comparable_v<T> &&
std::is_constructible_v<span<T const>,
R const&>)>
bool operator==(R const& lhs, span<T, E> rhs) {
return rhs == std::span<T const>(lhs);
}
}
```

This, finally, is a complete solution. Well, it would be nice if we checked
not only that `T == T`

is a valid expression but also that it
was convertible to `bool`

, so it’s *nearly* complete. But it
does satisfy the rest of the requirements I set out earlier… at the cost of
having to write 18 operators and some very careful constraints.

Moreover, you really have to test those 18 operators carefully - while writing this blog I made numerous typos in these implementations (and no promises that I fixed all of them either), which would only be caught in testing…

### Implementation in C++17 with hidden friends

But wait, there’s this technique that people like to use to implement comparison
operators called *hidden friends*. Does that help us here?

```
namespace std {
template <typename T, size_t Extent=dynamic_extent>
class span {
// ...
template <typename U=T,
REQUIRES(equality_comparable_v<U>)>
friend bool operator==(span lhs, span rhs);
};
```

And the answer is… not really, no. If I have a `vector<int> const`

,
I’m simply not going to be able to compare it to a `span<int>`

in this way.

If I make the hidden friend take two `span<T const>`

objects
instead, then I have to deal with redefinition issues with `span<T>`

and `span<T const>`

competing to define the same operators.

I don’t think there’s a solution here. At least, I can’t think of one.

### Implementation in C++20

Thankfully, C++20 is here and we can do… so much better. With the combination of three large features:

- Concepts
- Ranges
`operator<=>`

(or generally, C++20 comparisons)

Our initial design was that `span<T>`

should be comparable to
any contiguous range of the *sameish* type, as long a that type is appropriately
comparable.

Since we’re going to need that particular constraint in multiple places, let’s turn it into a proper concept:

```
// a contiguous range whose value type and T
// are the sameish type
// (range_value_t shouldn't be cv-qualified)
template <typename R, typename T>
concept const_contiguous_range_of =
contiguous_range<R const> &&
std::same_as<
std::remove_cvref_t<T>,
std::ranges::range_value_t<R const>>;
```

And now we can directly translate our requirements into code:

```
namespace std {
template <typename T, size_t Extent=dynamic_extent>
class span { /* ... */ };
template <equality_comparable T, size_t E,
const_contiguous_range_of<T> R>
bool operator==(span<T, E> lhs, R const& rhs)
{
return ranges::equal(lhs, rhs);
}
template <three_way_comparable T, size_t E,
const_contiguous_range_of<T> R>
auto operator<=>(span<T, E> lhs, R const& rhs)
{
return std::lexicographical_compare_three_way(
lhs.begin(), lhs.end(),
ranges::begin(rhs), ranges::end(rhs));
}
}
```

That’s it. That’s… the complete solution. Just two operators, with constraints
that are quite straightforward to write, both of whose implementations are roughly
trivial (now, if you want to support types that do not provide `<=>`

,
you’ll have to use * synth-three-way* in [expos.only.func] and constrain based on that). Moreover,
unlike before, these can (and probably should) be member function templates. The
only reason I’m making them non-member function templates is that it’s the only
way I can add them outside of the standard library.

Why do we only need 2 operators where previously we needed 18? Because C++20’s comparison operators allow reversed and synthesized comparisons. Let’s go through a few examples to see what the candidate sets are and how overload resolution actually works. See also Comparisons in C++20 for a more thorough treatment.

#### Comparing `span<int>`

to `span<int>`

with `==`

We’ll have two candidates (I’m going to ignore extents for simplicity):

`operator==(span<T>, R const&)`

with`T=int`

and`R=span<int>`

.`operator==(R const&, span<T>)`

with`T=int`

and`R=span<int>`

. This is the reversed candidate.

Both are exact matches (no conversions in either argument), neither function template is more specialized than the other, neither is more constrained than the other. But we prefer the non-reversed candidate to the reversed one, so this works and is unambiguous (and the implementation is hopefully obviously correct).

#### Comparing `span<int>`

to `span<int const>`

with `==`

We again have two candidates, though they of course deduce differently:

`operator==(span<T>, R const&)`

with`T=int`

and`R=span<int const>`

.`operator==(R const&, span<T>)`

with`T=int const`

and`R=span<int>`

The difference in deduction doesn’t really matter though - both candidates are exact matches, with neither function template more specialized or more constrained than the other, so we prefer the non-reversed candidate. This works and is unambiguous.

#### Comparing `span<int>`

to `span<int>`

with `!=`

Since there is no `operator!=`

candidate, this works exactly the
same way as `==`

does, except in the end
instead of evaluating `x == y`

we evaluate
`!(x == y)`

.

Since `x != y`

nearly always means `!(x == y)`

,
we get it for free alongside `x == y`

.

#### Comparing `vector<int>`

to `span<int>`

with `==`

This time, the normal operator isn’t a candidate (since `vector<int>`

is not any kind of `span<T>`

) but the reversed operator is: we
still deduce `R=vector<int>`

and `T=int`

. That’s
our only candidate, it’s viable, and it works.

#### Comparing `span<int>`

to `list<int>`

with `==`

Similar to the above, only the normal candidate would be potentially viable -
but after we deduce `R=list<int>`

, we see that `R`

fails to
satisfy the constraint that it is a contiguous range. The normal candidate is
removed from consideration, and we end up with no viable candidates.

#### Comparing `span<int>`

to `vector<long>`

with `==`

As above, only the normal candidate would be potentially viable, and here
`R=vector<long>`

is actually a contiguous range. But that’s not
our only constraint, we also require the *sameish* value type - and `int`

and `long`

are not sameish. Hence, we again end up with no
viable candidates.

#### Comparing `vector<int>`

to `span<int>`

with `<`

Enough about `==`

, here’s an example with `<`

.

We don’t have any `operator<`

candidates, but we do
have an `operator<=>`

candidate with its parameters reversed.
This deduces `R=vector<int>`

and `T=int`

, all
the constraints are satisfied. It’s the only candidate, and it’s viable.

This gets applied to our code that did `v < s`

and rewrites it
to evaluate as `0 < operator<=>(s, v)`

(note the reversal of
arguments into the function). Had we compared in the other direction,
`s < v`

would rewrite to `operator<=>(s, v) < 0`

.

### Try It Out

As you can see, implementing `span`

’s comparison operators in C++20 is remarkably
easy comparing to what this was like in C++17. I wouldn’t call the implementation
*trivial* - it still took thought to come up with the correct constraints - though
it does seem trivial in comparison.

Even though `std`

won’t provide these comparison operators, and it’s somewhat
naughty to do so externally, I created a repo that does exactly this:
span_ext. It’s a single header that
implements all of the comparison operators for `std::span`

in
C++20. It’s built on top of concepts, ranges, and `<=>`

like
I showed in this blog. I’m not the best at CMake, patches welcome!

But libc++ does not have the C++20 library functionality yet, so it instead can use range-v3 for all the relevant pieces. That’s why the header is, at the time of this writing anyway, 162 lines of code instead of like 20 - because most of it implementing other C++20 library things that may not necessarily exist yet.

C++20 may lack comparisons for `std::span`

, but it’s still going
to be great.

Let me know what you think of this article on twitter @BarryRevzin!