Add span_iterator overloads for make_span() and subspan()

[aurelienrb]

Hello,

I often need to search for a value in a span and split where it was found. And I can't use the standard algorithms such as std::find() because they return a span_iterator... that I can do nothing with!

Therefore I propose to introduce overloads for make_span() and subspan() that allow to write code like that:

void split(span<T> s, T value)
    const auto it = std::find(s.begin(), s.end(), value);
    
    const span<T> before = make_span(s.begin(), it); // or s.subspan(s.begin(), it);
    const span<T> result = s.subspan(it); // empty if it == s.end()
}

What's your opinion?

Aurelien

[galik]

Maybe a separate library would be more appropriate? (Or at least a separate section in this library) There must be quite a few basic functions that people would use a lot. For example splitting an array into std::vector<gsl::span<T>> based on a predicate or a value?

Your example could return a std::pair for each half?

template<typename T>
std::pair<gsl::span<T>, gsl::span<T>> bisect(gsl::span<T> s, T const& v)
{
	auto found = std::find(s.data(), s.data() + s.size(), v);
	return {{s.data(), found}, {found, s.data() + s.size()}};
}

[aurelienrb]

If we define span::iterator that way:

template <class T>
class span
{
public:
    using iterator = T*;

Then code becomes simpler and more practical.

Therefore what's the point of span_iterator? Because the current design is a bit half baked IMO and it makes me write more complex / risky (ugly) code than if I don't use span.

[maikel]

You could simply use a different span implementation. No-one forces you to use bound-checked iterators. For example: https://github.com/ericniebler/range-v3/blob/master/include/range/v3/span.hpp

[aurelienrb]

Ok so the goal of span_iterator is to provide bounds checking right? I missed it, sorry for that.

My goal is, if possible, help to improve the GSL / span proposal and make it better. And I think there's a hole in the current spec that allows 2 different implementations to be easily incompatible. After a quick read of the pdf, it's not clear to me what the following code should do:

span<int> f(span<int> s)
{
    return make_span(std::next(s.begin()), s.end());
}

Based on how span::iterator is implemented, this code will compile... or not. Don't you think it's an issue (with the spec)?

I think this point should be clarified, and I wished it would require the code to compile because it makes the interface way more useful (IMO) and won't require much work in the current implementation (1 extra overload for make_span() and subspan()).

[MikeGitb]

Doesn't really make a difference, but there have been a few revisins latest paper I could find on this is http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0122r4.pdf.
I don't know, why span's constructors require a pointer instead of an iterator (maybe because we don't have a contiguous_iterator_tag) but I'd also prefer if this got changed - at least for span::iterator.

In my personal opinion, working with gsl::span is anyway much less pleasant than one would expect. So if range checking is not deemed important (although this is actually a core idea behind the span proposal) then the ranges-v3 version is a good alternative - even if it comes with a lot of baggage.

[aurelienrb]

Ok. So I'll create a pull request with my proposed changes and we will see.

Until now in my code I have been using a custom iterator pair class (make_range), a similar idea than what proposed @galik. I saw the limits of that, and I decided to see how span compares to it. I agree it's not as smooth as one would expect. But I like its type erasure approach, it makes my code more elegant and flexible because I don't have to propagate vector::iterator or similar everywhere.

That being said, I identified another caveat with the current implementation of span_iterator:

class X {
public:
    span<int> get() const { return v; }
private:
    std::vector<int> v{1, 2, 3, 4, 5};
};

int main() {
    X x{};
    for (auto it = x.get().begin(), end = x.get().end(); it != end; it++) {
        it = std::find(it, end, 3);
    }
}

It crashes because span_iterator lifetime is bound to the lifetime of the span it originates from. And in the above example it's a temporary.

I think this implementation detail could be challenged and replaced with another one that it not tied to a span instance while still allowing bounds checking. I'll try to propose a pull request for that too.

[maikel]

It crashes because span_iterator lifetime is bound to the lifetime of the span it originates from. And in the above example it's a temporary.

This is a design decision, which was discussed in another issue already.
See here #437

[neilmacintosh]

Hello @aurelienrb and thanks for taking the time to raise an issue. Sorry for the delay in getting back to you. I was off at a C++ standards meeting and then took some vacation.

Now, there's a lot going on in this thread, so let me try to summarize my responses to some of the statements being thrown out:

span currently only has a constructor from a pair of T*, because there is no reliable way to identify a contiguous sequence iterator when we started out (as I believe @MikeGitb correctly observed and I think @maikel has also observed in #361). If there was, we would have a constructor from a pair of iterators.

With that said, I've been doing some work recently to improve the implementation of the existing constructors. I think I could extend that work to allow construction from a pair of iterators where the iterators either originated from a span or from a Container that meets the same concept-requirements as the constructor from Container. It's not quite the from-contiguous-iterator constructor we really want in the design, but it's pretty close and will cover the major use cases (such as the one you have captured here). I will take a look at putting that in now I have some time back to work on the GSL again.

In passing, I'm not sure it's reasonable to describe the span design (or proposal) as "half-baked". Particularly if you have not taken the time to absorb key motivations such as our strong focus on bounds-safety (a sadly common and costly problem in C++ programs).

There are areas with span where we are deliberately pushing the boundaries of what is portable with the current library and language. As an example, look at spans use of std::byte, where technically, the current implementation yields undefined behavior with many compilers. However, now std::byte will be part of the language and library in C++17. So sometimes a little patience is required while we push those boundaries and try to work out what is safe, portable and reasonable in today's C++ without having a design that will be ugly for tomorrow's C++.

[MikeGitb]

A bit off topic, but I'm really glad to hear that std::byte made it into c++17.

[aurelienrb]

Hello Neil,

First of all, thanks for taking time to comment on my usage of "half-baked", which was completely inapropiate and makes me feel ahamed of :/ English is not my native tongue, and I wasn't aware of how rude and agressive this phrase actually is. My intent was to express the idea that only half of the functions related to iterators are available (accessing data) and thus the API is missing the other half (construction from iterators) to "taste really good". I am even more sorry for such rude words since I know who you are and how much work it requires to improve the language. So please "excuse my French" :)

Now regarding the acceptance of iterators in the ctor (or make_span), I had just span_iterator in mind, so if you plan to support them (+ others) that's great news because it means I can patch my local version the time you need to complete the work and continue to use the GSL rather than switching to an alternative library. Moreover, I think it's a good thing in term of consistency regarding the other STL types we are used to.

PS: no worries for the "delay": 2 days is fine... I just hope you had time to see a bit more than the Bongo Ben's of Kona :)

[neilmacintosh]

Thanks for clarifying @aurelienrb, no need for embarrassment. Plus, your English is much better that my French could ever hope to be :-)

Yes, I do plan to support span_iterator, so it sounds like that should meet your needs. Now it's just a matter of me going and doing it!

Yes, I did manage to make it past Bongo Ben's! In fact, I even got a chance to snorkel with some manta rays, which was a mind-blowing experience. Your comment really made me laugh though, as I have spent quite a bit of time at Bongo Ben's on a previous visit ;-)

For everyone looking for the latest span proposal text: I have added it to the CppCoreGuidelines repository here:

https://github.com/isocpp/CppCoreGuidelines/blob/master/docs/P0122R4.pdf

I will keep that updated with future revisions, and it will eventually be referenced in nicer GSL documentation over at that repo.

[neilmacintosh]

Ok...so since this issue was last discussed things have moved on quite a bit. span has made it into the Working Draft for C++20. In that document, and the existing constructor from two pointers remains.

I'm going to close the issue out as - unless the standard library adds a way to identify contiguous iterators - using that constructor is the simplest and best option available for now.