span: the best span

This post is a response to RangeOf: A better span, which has many problems worth addressing in detail. While most of this post will deal with specifically std::span<T> (which is indeed the best span), the last section will also discuss a recent addition to the standard library: std::ranges::subrange<T*>.

Non-issues

The original post presents three “issues” with span. One is about naming - but naming is hard and people can disagree as to what the right name for such a thing could be. span seems fine to me. In my code base at work, we call it Slice<T> (named after Rust’s concept of the same name), though this name wouldn’t work so well in C++ since there already is a thing in the standard library called std::slice<T>.

The third is about how span can only be used over contiguous memory. It’s important to note that creating a type erased contiguous view has zero overhead since you can completely represent the state with basically just a pair<T*, size_t> (more on this later). But creating a type erased non-contiguous view can be extremely expensive. span is just for contiguous ranges because it is the precisely the lack of overhead that makes it so useful.

The second listed issue is worth discussing in more detail. It says:

Being non-owning, it’s a view in the Range terminology. Its constness is shallow. that means that you can modify the underlying element of a const span

But far from being an issue, shallow const-ness is the only reasonable implementation choice for this type, and it’s worth understading why. span is a view, or more generally it is a reference-like type. It simply refers to data, it doesn’t own it. Copying a span is cheap - it’s just copying a couple pointers - and each copy also refers to the same underlying data. What this means is that, were span to propagate const, it would be very easy to get around:

std::vector<int> v = {1, 2, 3};

std::span<int> const a = v;
// even if this did not compile...
a[0] = 42;

// ... this surely would
std::span<int> b = a;
b[0] = 42;

Since we can so easily “remove” the const by doing a cheap copy, it doesn’t really make sense to prevent non-const access. This follows the core language rules for reference-like types that we’re more familiar with: pointers do not propagate top-level const - you can modify the element that a T* const points to.

We also see this in the specification for the View concept in Ranges:

template<class T>
  concept View =
    Range<T> && Semiregular<T> && enable_view<T>;

where the default value of enable_view<T> is based in part on the heuristic: “Otherwise, if both T and const T model Range and iter_reference_t<iterator_t<T>> is not the same type as iter_reference_t<iterator_t<const T>>, false. [ Note: Deep const-ness implies element ownership, whereas shallow const-ness implies reference semantics. — end note ]”. In other words, if a Range has deep const-ness, it is not a View (with one exception: single_view<T> is a view with deep constness).

`span<T>` vs `ContiguousRange auto const&`

The bulk of the original post suggests replacing functions taking parameters of type span<T> with function templates taking parameters constrained by ContiguousRange. That is, to replace:

template <typename T>
void f(const std::span<const T> & r);

with

void g(const std::ContiguousRange auto & r);

Let’s start with f. First of all, you basically never want to take a span by reference to const. Types like span are cheap to copy - so you’re not saving anything by taking a reference. You are however introducing another indirection as well as the possibility of aliasing that you don’t need. The only exception is if you really do need the identity of the span in question (e.g. if you’re using one as an out parameter). That’s probably not the case here, so pass by value.

Secondly, it is quite rare to want to deduce the underlying value type of a span, in the same way that it is rare to deduce the underlying signature of a std::function. The advantage of type erasure is the ability to work seamlessly with a wide variety of objects that meet the right set of requirements - if we deduce the value type of span, we can only work with span. You can’t pass in a vector<int> to f - that is, unless you explicitly write f<int>(some_vector), and that’s just unfriendly. You would almost always write a concrete type instead.

There is a similar problem with g in this regard, in that it’s very difficult to actually get the value type from the constrained template argument - there’s just no easy way to do that with Concepts today. I have a whole post about such Concepts declarations issues.

So let’s just pick a value type instead - let’s say, int. That gets us to:

void f(std::span<int const>);
// versus
void g(ContiguousRangeOf<int const> auto const&);

Alright, let’s talk about g now. What actually does that signature mean? Let’s just expand it out to use the most verbose possible syntax for added clarity and see what happens when we call these functions:

void f(std::span<int const>);

template <typename R>
    requires ContiguousRange<R> &&
       Same<iter_value_t<iterator_t<R>>, int const>
void g(R const&);

std::vector<int> v = {1, 2, 3};
std::vector<int> const& cv = v;

f(v);  // ok
f(cv); // ok
g(v);  // error
g(cv); // error

What happened?

A span<int const> is very flexible, it can accept v or cv just fine. But the constraint we’re putting on the range says that iter_value_t must be int const. But the value_type for both vector<int>::iterator and vector<int>::const_iterator is just int (and indeed the value_type should never be cv-qualified). No match.

Can we fix this? We can try to swap from using value_type to using reference, since that would let you distinguish the two different iterator types. If we’re careful enough about references, that gets us a little bit closer:

template <typename R, typename V>
concept ContiguousRangeOf = ContiguousRange<R> &&
    Same<iter_reference_t<iterator_t<R>>, V&>;

void g(ContiguousRangeOf<int const> auto const&);

g(v);  // error: int& isn't int const&
g(cv); // error: same

Oh right, in both cases we’re deducing std::vector<int>, even though cv is a reference to const. We’d need to switch to:

void g(ContiguousRangeOf<int const> auto&&);

g(v);  // error: int& isn't int const&
g(cv); // ok

There’s probably some way of specifying this concept to allow precisely the right things in the const access case… but it escapes me at the moment. At least, I mean some way other than ConvertibleTo<span<int const>>, which seems to defeat the purpose. But let’s just use that for now since it works:

void g(ConvertibleTo<span<int const>> auto&& r) {
    r[0] = 42;
}

g(v); // perfectly okay: assigns v[0] to 42

We want to express that we only want read-only access to the elements - we said int const and not int - but we can’t actually enforce that in the body. I can pass in a non-const vector and then modify its elements just fine. There is nothing stopping me. As a result, there’s very little semantic information that you can deduce from the signature of g compared to the signature of f - f is much more expressive.

One way to solve this particular subproblem is to have a concept that checks the value_type and one that checks the reference. That is, take a ContiguousRangeWithValue<int> auto const& for the const case and a ContiguousRangeWithReference<int> auto&& for the non-const case. This is both quite complex and the difference between these cases is really subtle and beginner-hostile. And it is still insufficient - if the contiguous range in question has shallow const (such as span), this approach still wouldn’t ensure that the function body only has constant access.

Let’s assume that we come up with the correct ContiguousRangeOf concept that checks the right things for us. That still doesn’t mean that this version is easy to use. Consider some simple function that just wants to assign one element:

void f(span<int> s) [[expects: !s.empty()]] {
    s.front() = 42;
}

void g(ContiguousRangeOf<int> auto&& r) [[expects: !r.empty()]]  {
    r.front() = 42;
}

std::vector<int> v = {1, 2, 3};
f(v); // ok
g(v); // ok

int arr[] = {1, 2, 3};
f(arr); // ok
g(arr); // err

Raw arrays don’t have member functions. Our constraint just requires that the range is contiguous - it says nothing at all about whether that range has member functions named empty or front. So even if you can come up with the right way to constrain these functions, you still have to be exceedingly careful about the implementation of them.

On top of all of this, the example in the original post and the one I’ve been using - void f(span<int const>) is just one single function, but whatever the right function template ends up being for this scenario would end up with many, many instantiations - for every kind of range, for every value category and constness. Not only does this bloat compile times, it also just increases the amount of code that needs to be emitted - which would hurt instruction cache.

Typically, when we consider the trade-offs between using type erasure and using templates, we talk about things like convenience, compilation time, and the ability to use heterogeneous types as benefits for type erasure whereas the benefit for using templates is performance. Type erasure typically performs worse because we have to rely on either allocation (to create the type erased object), indirect dispatch via virtual functions or function pointers (to provide a common interface), or both. Indeed, the performance hit on type erasure can be quite large! So, surely, when performance matters, we would want to use ContiguousRangeOf<int> auto&&? Actually, span is special in this regard. There is never any allocation necessary and there is no indirection. The only overhead on using span<int> directly instead of vector<int>& is the overhead of constructing the span<int> itself. And it might even be better than that, due to being able to take the span by value - which means we don’t have to keep going to memory to look up our data. Even on the front that type erasure typically loses, span does just fine.

To summarize:

The solution presented in the original post is not a solution at all. Fixing it is non-trivial, and you have to be careful to ensure that you use forwarding references - otherwise you’re not constraining what you think you’re constraining. It’s not the kind of API approach that lets you fall into the pit of success, as it were.
Once we get the constraint right, we’re severely limited in the functionality we can actually use in the body of the function template, because we only constrained on being a range and not on any actual members. span gives us a common interface that we could use.
There is no way to provide a read-only layer with concepts. If we use a hard constraint on allowing exactly ranges of T const, we prevent users from passing non-const ranges - which would conceptually be safe. But if we allow non-const ranges, we implicitly allow them to be modified in the body of the function. No way to prevent that (or at least, if there is, it’s going to be quite a bit more complicated than taking a span<T const>).
And even if we implement the body correctly, we’re introducing a potentially massive amount of code bloat by way of lots of different instantiations for every container x value category x constness. All of these instantiations give us no benefit whatsoever, since span doesn’t suffer from the typical type erasure performance hit.

There is zero benefit that I can think of to the constrained function template approach over writing a function that takes a span by value, and there are many significant disadvantages.

And it actually gets worse than that, since even if the constrained function template approach had benefits - you would still need span. What if you want to return a span? What if you wanted to pass a subset of a vector into the function, instead of the whole range? You need some lightweight representation to handle both of these situations, and that lightweight representation is span. Concepts don’t help you with other of those problems at all.

`span<T>` vs `subrange<T*>`

As mentioned at the top of this post, there are actually two different contiguous views in the standard library at the moment: span<T> and, new with the addition of Ranges, subrange<T*> (see [range.subrange]). While span is always a contiguous view, subrange is a more general abstraction that can be a view over any kind of iterators. It may be worth asking if we need two contiguous views in the standard library, so let’s go over the differences between these two types. There are a few main ones:

The meaning of the template parameter. span<T> is a contiguous view over a range whose element_type is T. subrange<T*> is a contiguous view using two T*s as iterators. The parameter just means something else. I give the advantage to span here, since it more directly represents what I want to say when I use such a type.
The implicit conversions. span<T> is constructible from any container which has data() and size(). This makes it extremely easy to use, since you can just pass arbitrary containers into it - this conversion is perfectly safe. On the other hand, subrange<T*> is constructible from any range whose iterator and sentinel types model ConvertibleTo<T*>. This includes raw arrays, but may or may not include vector<T>. This is a big advantage for span.
Iterator specification. For span<T>, the iterators are implementation defined. This allows implementations to diagnose bad access, but more importantly allows for stronger type safety. For subrange<T*>, the iterators are precisely T*. The added type safety is important - it can prevent some bad misuses, such as passing in a span<Derived>::iterator into a function expecting a Base* (more on this in a moment). And a non-T* iterator would be very nearly trivial (just a very thin wrapper around T*), so would be unlikely to interfere with the optimizer. Altogether, probably a weak win for span.
Quirks. There are some odd quirks for both types. span<T>::cbegin() gives back an iterator that provides deep constness whereas std::cbegin(span<T>) gives back an iterator that provides shallow constness. That’s… odd. And as described earlier, it’s questionable to provide deep constness for views. As Tim Song pointed out yesterday, subrange<Base*> is currently constructible from subrange<Derived*> - which is actively bad. This is less a quirk than a clear design defect that will probably go away before C++20 ships, so probably not even pointing out. Advantage subrange (hopefully).
Fixed size. While the typical use of span will be to have a runtime-sized view, you can also have a fixed, compile-time-sized view by providing the second template parameter. span<T, 2> is a contiguous view over 2 Ts, and only requires a single T* as its storage. There is no way to express this requirement in subrange. A fixed-size span has the same semantics as a runtime-sized span - so this isn’t really the same kind of specialization difference that we get with vector<bool>.
Generalizing to other iterators. In the same way, there is no way to express a non-contiguous view with span. So if you need a general sub-view, you would need to use subrange. But note that this would not be a type erased view. subrange<list<int>::iterator> and subrange<deque<int>::iterator> are still different types. A subrange<any_iterator<int>> would probably be too expensive to use.

Overall, for the problems that span solves, span is a better solution than subrange. span is, indeed, the best span.

span: the best span

Non-issues

span<T> vs ContiguousRange auto const&

span<T> vs subrange<T*>

`span<T>` vs `ContiguousRange auto const&`

`span<T>` vs `subrange<T*>`