std::string_view iterator constructor?

[Olaf van der Spek]

I was updating some code and noticed string_view isn't constructible from (string_view) iterators. What's the reason for this?

IMO it should be constructible from string_view iterators and perhaps even from other contiguous char iterators.

[Marshall Clow]

On Wed, Mar 29, 2017 at 12:26 AM, Olaf van der Spek <olafv...@gmail.com> wrote:

I was updating some code and noticed string_view isn't constructible from (string_view) iterators. What's the reason for this?

IMO it should be constructible from string_view iterators and perhaps even from other contiguous char iterators.

The  "contiguous iterator" property is a run-time property of the iterator pair, and as such not checkable at compile time. 

So string_view would have to have a constructor that took either (a) a pair of string_view iterators, or (b) a pair of iterators.

The first is easy to emulate with the (ptr, len) constructor.

      string_view (&*first, std::distance(first, last));

The second is way too easy to misuse (list::iterator, say?)

-- Marshall

[Nicol Bolas]

On Tuesday, August 8, 2017 at 12:20:07 PM UTC-4, Marshall wrote:

On Wed, Mar 29, 2017 at 12:26 AM, Olaf van der Spek <olafv...@gmail.com> wrote:

I was updating some code and noticed string_view isn't constructible from (string_view) iterators. What's the reason for this?

IMO it should be constructible from string_view iterators and perhaps even from other contiguous char iterators.

The  "contiguous iterator" property is a run-time property of the iterator pair, and as such not checkable at compile time. 

Well maybe that's something we ought to fix.

And no, whether an iterator is contiguous is not a runtime property of the data; it's a compile-time property of the iterator type. It's just not one we have a way to detect.

We have the concept of contiguous iterators, and we have definitions of iterator types that are contiguous. But we do not have a way to actually detect the difference between random access and contiguous iterators in C++.

So string_view would have to have a constructor that took either (a) a pair of string_view iterators, or (b) a pair of iterators.

The first is easy to emulate with the (ptr, len) constructor.

      string_view (&*first, std::distance(first, last));

Because God knows that's something that everyone should learn to write.

[Ville Voutilainen]

On 8 August 2017 at 19:50, Nicol Bolas <jmck...@gmail.com> wrote:
> On Tuesday, August 8, 2017 at 12:20:07 PM UTC-4, Marshall wrote:
>>
>> On Wed, Mar 29, 2017 at 12:26 AM, Olaf van der Spek <olafv...@gmail.com>
>> wrote:
>>>
>>> I was updating some code and noticed string_view isn't constructible from
>>> (string_view) iterators. What's the reason for this?
>>>
>>> IMO it should be constructible from string_view iterators and perhaps
>>> even from other contiguous char iterators.
>>>
>>
>> The "contiguous iterator" property is a run-time property of the iterator
>> pair, and as such not checkable at compile time.
>
>
> Well maybe that's something we ought to fix.
>
> And no, whether an iterator is contiguous is not a runtime property of the
> data; it's a compile-time property of the iterator type. It's just not one
> we have a way to detect.

Yeah, because whether some iterators are contiguous is a run-time
property of those iterators,
and we can't detect the contiguity at compile-time. Like every
iterator of every std::vector.
Or the iterators of std::string. From which iterators did you want to
construct your string_views
again?

[Marshall Clow]

On Tue, Aug 8, 2017 at 9:50 AM, Nicol Bolas <jmck...@gmail.com> wrote:

On Tuesday, August 8, 2017 at 12:20:07 PM UTC-4, Marshall wrote:

On Wed, Mar 29, 2017 at 12:26 AM, Olaf van der Spek <olafv...@gmail.com> wrote:

I was updating some code and noticed string_view isn't constructible from (string_view) iterators. What's the reason for this?

IMO it should be constructible from string_view iterators and perhaps even from other contiguous char iterators.

The  "contiguous iterator" property is a run-time property of the iterator pair, and as such not checkable at compile time. 

Well maybe that's something we ought to fix.

And no, whether an iterator is contiguous is not a runtime property of the data; it's a compile-time property of the iterator type. It's just not one we have a way to detect.

I disagree.

Let's actually read what the standard says, and then look at examples.

[iterator.requirements.general]/5 says: 

Iterators that further satisfy the requirement that, for integral values n and dereferenceable iterator values a and (a + n), *(a + n) is equivalent to *(addressof(*a) + n), are called contiguous iterators.

vector<int>v = {1,2,3,4,5};

basic_string<char>s{"abcde"};

deque<int>d = {1,2,3,4,5};

are v.begin(), v.end()) contiguous iterators?   Yes.

are s.begin(), s.end()) contiguous iterators?   Yes.

are d.begin(), d.end()) contiguous iterators?   On every implementation I know of, yes.

Other pairs of deque::iterators may not be contiguous.

 

We have the concept of contiguous iterators, and we have definitions of iterator types that are contiguous. But we do not have a way to actually detect the difference between random access and contiguous iterators in C++.

Indeed. Certainly not at compile time.

So string_view would have to have a constructor that took either (a) a pair of string_view iterators, or (b) a pair of iterators.

The first is easy to emulate with the (ptr, len) constructor.

      string_view (&*first, std::distance(first, last));

Because God knows that's something that everyone should learn to write.

The reason I like it is not because of the beauty - but because it pushes the responsibility for contiguous-ness (is that even a word?) onto the caller. [ Since the library cannot, in general, check for that ]

[Nevin Liber]

On Tue, Aug 8, 2017 at 11:50 AM, Nicol Bolas <jmck...@gmail.com> wrote:

On Tuesday, August 8, 2017 at 12:20:07 PM UTC-4, Marshall wrote:

On Wed, Mar 29, 2017 at 12:26 AM, Olaf van der Spek <olafv...@gmail.com> wrote:

I was updating some code and noticed string_view isn't constructible from (string_view) iterators. What's the reason for this?

IMO it should be constructible from string_view iterators and perhaps even from other contiguous char iterators.

The  "contiguous iterator" property is a run-time property of the iterator pair, and as such not checkable at compile time. 

Well maybe that's something we ought to fix.

*Nevin hangs head in shame for not yet updating n4183*

--

 Nevin ":-)" Liber  <mailto:ne...@eviloverlord.com>  +1-847-691-1404

[Marshall Clow]

I await this with great interest:

     std::list<int> l = {1,2,3};

     static_assert( std::is_contiguous(l.begin(), l.begin()));

     static_assert( std::is_contiguous(l.begin(), l.begin() + 1 ));

     static_assert(!std::is_contiguous(l.begin(), l.begin() + 2 ));

-- Marshall

[Nicol Bolas]

On Tuesday, August 8, 2017 at 1:10:51 PM UTC-4, Marshall wrote:

On Tue, Aug 8, 2017 at 9:50 AM, Nicol Bolas <jmck...@gmail.com> wrote:

On Tuesday, August 8, 2017 at 12:20:07 PM UTC-4, Marshall wrote:

On Wed, Mar 29, 2017 at 12:26 AM, Olaf van der Spek <olafv...@gmail.com> wrote:

I was updating some code and noticed string_view isn't constructible from (string_view) iterators. What's the reason for this?

IMO it should be constructible from string_view iterators and perhaps even from other contiguous char iterators.

The  "contiguous iterator" property is a run-time property of the iterator pair, and as such not checkable at compile time. 

Well maybe that's something we ought to fix.

And no, whether an iterator is contiguous is not a runtime property of the data; it's a compile-time property of the iterator type. It's just not one we have a way to detect.

I disagree.

Let's actually read what the standard says, and then look at examples.

[iterator.requirements.general]/5 says: 

Iterators that further satisfy the requirement that, for integral values n and dereferenceable iterator values a and (a + n), *(a + n) is equivalent to *(addressof(*a) + n), are called contiguous iterators.

I see nothing here which would permit the contiguous property to be different for some values of `n` and some values of `a`. The only time the value of an iterator is mentioned is that the behavior only counts when `a` is dereferenceable and that `(a + n)` is also dereferenceable. That seems to be to be a property of the type, not a property of the current value of the type. That is, it has to be true for any `n` where `a` and `(a + n)` are dererefenceable.

Note that your interpretation also requires that we read "Iterators that further satisfy..." as "Iterator values that further satisfy..." This is at odds with all of the previous sections, which refer specifically to what Iterator types must satisfy. Consider paragraph 4, which also starts with "Iterators that further satisfy..."; I presume that you're not trying to claim that the mutability of iterators are a runtime quality, are you?

And now, let's pretend that your interpretation is correct. That this definition is in fact a runtime property rather than a compile-time one.

I would therefore say that it is a defect in the standard definition, which should be resolved. Why?

The original paper on this matter, N3884, very clearly intends for contiguousness to be a static, compile-time property. It declared contentiousness to be a new iterator tag, which is of course static. It's revision of 24.2.8, which defines contiguous iterators conceptually, clearly states that it is a property of "A class or pointer type X", not of a particular value.

The refinement that was eventually adopted, N4284, makes it clear that it is doing what N3884 is doing, but without making a new iterator tag for it (due to compatibility issues).

I therefore submit that your interpretation, that contiguousness is a runtime property rather than a static property) is not what the feature was intended to be. And if your interpretation really is what the standard says, then the standard should be corrected.

[Nevin Liber]

So do I, because that isn't what I am doing...

I'm working on a trait to (a) indicate that a particular type represents a contiguous iterator (a refinement of random access iterator) and (b) convert that iterator to a pointer.  I am not checking (and AFAIK, cannot check) that given a pair of iterators, does it represent a contiguous range at run time.

Specifically, for your previous example, the trait would return true for vector<int>::iterator, basic_string<char>::iterator and false for deque<int>::iterator.

[Nevin Liber]

On Tue, Aug 8, 2017 at 1:28 PM, Nicol Bolas <jmck...@gmail.com> wrote:

I therefore submit that your interpretation, that contiguousness is a runtime property rather than a static property) is not what the feature was intended to be. And if your interpretation really is what the standard says, then the standard should be corrected.

Asking if a range is contiguous is a run-time query.  Asking if a given type models a contiguous iterator is a compile-time property.  These are not in conflict with each other.

A raw pointer models a contiguous iterator, yet an arbitrary pair of pointers is not necessarily a contiguous range.

IMO, once we have such a trait, string_view should be extended to construct from a pair of contiguous iterators.

[Nicol Bolas]

On Tuesday, August 8, 2017 at 2:39:50 PM UTC-4, Nevin ":-)" Liber wrote:

On Tue, Aug 8, 2017 at 1:28 PM, Nicol Bolas <jmck...@gmail.com> wrote:

I therefore submit that your interpretation, that contiguousness is a runtime property rather than a static property) is not what the feature was intended to be. And if your interpretation really is what the standard says, then the standard should be corrected.

Asking if a range is contiguous is a run-time query.  Asking if a given type models a contiguous iterator is a compile-time property.  These are not in conflict with each other.

But that also means that when Ranges TS comes along, we wouldn't have a compile-time query for a range which provides contiguous iterators. Or at least, it would have to be called something other than the very natural "contiguous range", since that is taken over by this runtime query.

I just don't see the point in asking the question, "does this pair of iterator values represent a contiguous sequence of value?", rather than "do these iterator types/this range type represent a contiguous sequence of values?"

A raw pointer models a contiguous iterator, yet an arbitrary pair of pointers is not necessarily a contiguous range.

But that's because a pair of pointers is not necessarily a range, not due to whether or not it is a contiguous one. Being a range is a runtime property of the values; being contiguous should be a static property of the iterator type, much like random-access and the like.

IMO, once we have such a trait, string_view should be extended to construct from a pair of contiguous iterators.

Agreed.

[Olaf van der Spek]

2017-08-08 20:39 GMT+02:00 Nevin Liber <ne...@eviloverlord.com>:
> Asking if a range is contiguous is a run-time query.

How so?
A valid range given by two contiguous iterators is a contiguous range.
An invalid range might not be, but then again it's invalid..

> A raw pointer models a contiguous iterator, yet an arbitrary pair of
> pointers is not necessarily a contiguous range.

It's not necessarily a range either.

--
Olaf

[Andrey Semashev]

On 08/08/17 22:37, Olaf van der Spek wrote:
> 2017-08-08 20:39 GMT+02:00 Nevin Liber <ne...@eviloverlord.com>:
>> Asking if a range is contiguous is a run-time query.
>
> How so?
> A valid range given by two contiguous iterators is a contiguous range.
> An invalid range might not be, but then again it's invalid..

I think the case in point is deque. In general, a deque (or a range
adopting deque::iterators) is not contiguous. However, there can be a
pair of iterators that denote a contiguous range within the deque.

IMHO this case probably requires some sort of support from the
container. The user at least needs to be able to discover in runtime if
two iterators denote a contiguous range and then convert the iterators
to local_iterators, which have different type and are statically known
to be contiguous (i.e. are basically guaranteed to refer to the same
segment of the deque).

[Nevin Liber]

On Tue, Aug 8, 2017 at 4:21 PM, Andrey Semashev <andrey....@gmail.com> wrote:

On 08/08/17 22:37, Olaf van derI think the case in point is deque. In general, a deque (or a range adopting deque::iterators) is not contiguous. However, there can be a pair of iterators that denote a contiguous range within the deque.

IMHO this case probably requires some sort of support from the container. The user at least needs to be able to discover in runtime if two iterators denote a contiguous range and then convert the iterators to local_iterators, which have different type and are statically known to be contiguous (i.e. are basically guaranteed to refer to the same segment of the deque).

IMHO this is not a use case I care about.

It is just a artifact for how deque happens to be implemented.  Plus, there is no guarantee that to_pointer(d.begin()) + d.size() == to_pointer(d.end()), even in Marshall's case.

[Nicol Bolas]

On Tuesday, August 8, 2017 at 5:31:49 PM UTC-4, Nevin ":-)" Liber wrote:

On Tue, Aug 8, 2017 at 4:21 PM, Andrey Semashev <andrey....@gmail.com> wrote:

On 08/08/17 22:37, Olaf van derI think the case in point is deque. In general, a deque (or a range adopting deque::iterators) is not contiguous. However, there can be a pair of iterators that denote a contiguous range within the deque.

IMHO this case probably requires some sort of support from the container. The user at least needs to be able to discover in runtime if two iterators denote a contiguous range and then convert the iterators to local_iterators, which have different type and are statically known to be contiguous (i.e. are basically guaranteed to refer to the same segment of the deque).

IMHO this is not a use case I care about.

Absolutely agreed. If the standard can't provide guarantees on it, I'm not sure I want someone writing code that only works if you pass them the right portion of a `deque`.

We need compile-time queries. That there might be some other types which could work at runtime, in some specific implementation-defined instance, is not a query we need. If your iterator cannot guarantee contiguity for any valid range, then I don't really want to support those specific instances where it can guarantee contiguity.

[Olaf van der Spek]

Without support for deque iterators the world would be happy too. ;)

--
Olaf

[Olaf van der Spek]

2017-08-08 18:20 GMT+02:00 Marshall Clow <mclow...@gmail.com>:
> On Wed, Mar 29, 2017 at 12:26 AM, Olaf van der Spek <olafv...@gmail.com>
> wrote:
>>
>> I was updating some code and noticed string_view isn't constructible from
>> (string_view) iterators. What's the reason for this?
>>
>> IMO it should be constructible from string_view iterators and perhaps even
>> from other contiguous char iterators.
>>
>
> The "contiguous iterator" property is a run-time property of the iterator
> pair, and as such not checkable at compile time.
>
> So string_view would have to have a constructor that took either (a) a pair
> of string_view iterators, or (b) a pair of iterators.
>
> The first is easy to emulate with the (ptr, len) constructor.

It might be easy but it's *not* simple.

> string_view (&*first, std::distance(first, last));
>
> The second is way too easy to misuse (list::iterator, say?)

string_view(&*first, last - first)); ?

Isn't &*first undefined behavior for empty ranges though?

--
Olaf