Re: [boost] [iterator][range] BoostIteratorTraversalConcepts-aware boost::advance/distance

Subject: Re: [boost] [iterator][range] BoostIteratorTraversalConcepts-aware boost::advance/distance
From: Andrzej Krzemienski (akrzemi1_at_[hidden])
Date: 2017-06-30 07:03:29

2017-06-29 22:44 GMT+02:00 Ion Gaztañaga via Boost <boost_at_[hidden]>:

> On 28/06/2017 22:14, Andrzej Krzemienski via Boost wrote:
>
>> 2017-06-28 22:03 GMT+02:00 Michel Morin via Boost <boost_at_[hidden]
>> >:
>>
>> Hi,
>>>
>>> The Boost iterator traversal concepts have not been adopted by the C++
>>> Standard.
>>> Because of this, some of RandomAccessTraversalIterators (Boost's
>>> concepts)
>>> are
>>> treated as InputIterators (Standard's concepts) by the stdlib.
>>>
>>> IMHO, Boost.Iterator should provide BoostIteratorTraversalConcepts-aware
>>> `boost::advance` and `boost::distance` to avoid the inefficiencies.
>>>
>>
>>
>> Not just inefficiencies. Using `prev()` may simply cause UB. See here:
>> https://akrzemi1.wordpress.com/2017/01/02/not-detecting-bugs/
>>
>
> I would like to confirm something in your post. I think the standard
> requires iterator_category to be one of the standard types, not something
> derived from them:
>
> Draft N4659 (2017/03) 27.4.2 Standard iterator tags
>

Well, yes and no. That is, you are right that if I have implemented
something that is a BidirectionalIterator but is not a
RandomAccessIterator, I should assign it exactly tag
`bidirectional_iterator_tag` and nothing else.

On the other hand, being dead pedantic, the tags inherit from one another,
so I may have an exact standard tag that is at the same time a type derived
from another standard tag.

> For every iterator of type Iterator, iterator_traits<Iterator>::iterator_category
> shall be defined to be the most specific category tag that describes the
> iterator’s behavior
>

Correct.

>
> If this is correct, in your article is_BidirectionalIterator() should be
> defined using is_same instead of is_base_of,

Maybe the choice of the name `is_BidirectionalIterator()` is bad. Wat I
meant was "at least Bidirectional". This function is implemennting a sort
of concept check. If we look at Ranges TS:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/n4671.pdf
Section 9.3.14 describing concept BidirectionalIterator uses DerivedFrom in
the check:

```
template <class I>
concept bool BidirectionalIterator() {
  return ForwardIterator<I>() &&
    *DerivedFrom*<iterator_category_t<I>, bidirectional_iterator_tag>() &&
    requires(I i) {
      { --i } -> Same<I&>;
      { i-- } -> Same<I>;
    };
}
```

and Boost.Iterator's iterator_category definitions might not compatible
> with the standard. Or am I missing something?
>

You are not: Boost.Iterator's category tags are not conformant to STL's
iterator tags. this decision is deliberate, as the definition of STL's
iterator concepts is buggy. For instance a zip iterator composed of
RandomAccessIterators in STL can only be a InputIterator, because it cannot
meet the STL requirement for ForwardIterator:

if *X* is a mutable iterator, *reference *is a reference to *T*; if *X* is
> a constant iterator, *reference *is a reference to *const T*.

A zip iterator has *reference* == *value_type*, as per
http://www.boost.org/doc/libs/1_64_0/libs/iterator/doc/zip_iterator.html.
And this decision makes sense. *reference_type* is not a reference but a
tuple of references.

So according to STL rules zip-iterator can only be an InputIterator, even
though you have random-access capability. And in fact, zip-iterator has
iterator_category tag of `std::input_iterator_tag`, but apart from that it
provides a Boost "traversal category" tag, which just tell how you get to
the next object in the colleciton and not about its reference type.

This STL requirement:

if *X* is a mutable iterator, *reference *is a reference to *T*; if *X* is
> a constant iterator, *reference *is a reference to *const T*.

Is not really necessary. I guess the authors just did not forsee iterator
types like zip-iterator at that point. STL2 does not have this requirement
anymore.

Regards,
&rzej;