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

2017-06-29 22:44 GMT+02:00 Ion Gaztañaga via Boost :

On 28/06/2017 22:14, Andrzej Krzemienski via Boost wrote:

...

2017-06-28 22:03 GMT+02:00 Michel Morin via Boost

...

:

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*() && requires(I i) { { --i } -> Same; { 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;