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&)withT=intandR=span<int>.operator==(R const&, span<T>)withT=intandR=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&)withT=intandR=span<int const>.operator==(R const&, span<T>)withT=int constandR=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.