2017-06-29 2:35 GMT+02:00 Michel Morin via Boost <boost@lists.boost.org>:

...

They are necessary for Boost to be consistent. But I think this means coupling two libraries.

Do you mean coupling of Boost.Iterator and Boost.Range? I think that would be fine, since Boost.Range already couples with Boost.Iterator. Boost.Range's `boost::distance` should call Boost.Iterator's `boost::distance`.

I meant `next()` and `prior()` that are located in Utility: http://www.boost.org/doc/libs/1_64_0/libs/utility/utility.htm Regards, &rzej;

2017-06-29 22:44 GMT+02:00 Ion Gaztañaga via Boost <boost@lists.boost.org>:

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

...

2017-06-28 22:03 GMT+02:00 Michel Morin via Boost <boost@lists.boost.org

...

:

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;

2017-07-03 0:53 GMT+02:00 Ion Gaztañaga via Boost <boost@lists.boost.org>:

On 30/06/2017 9:03, Andrzej Krzemienski via Boost wrote:

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.

AFAIK Boost.Iterator can define iterator_category as something derived from a standard tag, but that "something" could not be any of standard tags, so I think it's non-conformant.

A container could check through SFINAE if the tag of an iterator is exactly one of the standard provided ones. If Boost.Iterator defines iterator_category to anything that is not exactly a standard tag it won't be accepted by the container.

Those Boost iterators provide two distinct tags: 1. STL-conformant *iterator tag* (in the case of zip-iterator it is `std::input_iterator_tag`) 2. Boost-specific *iterator traversal tag*. So, Boost algorithms take advantage of the *iterator traversal tag*, but the iterator is still recognized as an STL container through the *iterator tag*, and still can be used with STL algorithms. The source of the UB is that `std::prev` *requires* that the iterator passed to it is at least a BidirectionalIterator, and zip-iterator is not (it is a legal OutputIterator). And while it is easy to check this with a type trait at compile-time (and Clang and MSVC do check this), technically not meeting these constraints is an UB, and GCC, because it is not required to check it, indeed does not check it. Regards, &rzej;

2017-07-04 0:49 GMT+02:00 Ion Gaztañaga via Boost <boost@lists.boost.org>:

On 03/07/2017 8:41, Andrzej Krzemienski via Boost wrote:

Those Boost iterators provide two distinct tags:

...

1. STL-conformant *iterator tag* (in the case of zip-iterator it is

I don't think so. The following example:

#include <iostream> #include <boost/iterator/zip_iterator.hpp> #include <boost/tuple/tuple.hpp>

template<class Iterator> void print_type(Iterator) { std::cout << typeid(typename Iterator::iterator_category).name() << std::endl; }

int main() { const int N=1; int keys[N]; double values[N]; print_type(boost::make_zip_iterator(boost::make_tuple(&keys[0], &values[0]))); return 0; }

prints in MSVC 2017

"struct boost::iterators::detail::iterator_category_with_traversal<struct std::input_iterator_tag,struct boost::iterators::random_acces s_traversal_tag>"

instead of "std::input_iterator_tag". That type inherits from "std::input_iterator_tag" but it's not an standard tag type, so IMHO, it's a non-conforming iterator.

Not necessarily non-conforming. I guess one could come up with such interpretation, but the Standatd is not really explicit about this. The most relevant sentence, "`iterator_category` shall be defined to be the most specific category tag that describes the iterator’s behavior" -- it could be read as "do not use any tag but these five" or "if you define a tag for RandomAccessIterator don't defien iterator_category as forward_iterator_tag". The example illustrating the intended usage of tags in [std.iterator.tags] also shows that it works fine with tags inherited from the standard ones. This additionally seems to be backed up by MSVC implementation of std::prev: ``` // TEMPLATE FUNCTION prev template<class _BidIt> inline _BidIt prev(_BidIt _First, typename iterator_traits<_BidIt>::difference_type _Off = 1) { // decrement iterator * static_assert(is_base_of<bidirectional_iterator_tag, typename iterator_traits<_BidIt>::iterator_category>::value, "prev requires bidirectional iterator");* _STD advance(_First, -_Off); return (_First); } ``` And by Ranges TS: ``` 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>; }; } ``` Also, the GCC problem is not caused by iterator tags deriving from the standard tags, but because std::prev is instantiated with an InputIterator. Regards, &rzej;

Michel Morin wrote:

Done. https://github.com/boostorg/iterator/pull/24

... and here is a PR for Boost.Range: Make boost::distance traversal-category-aware (and constexpr in C++14) https://github.com/boostorg/range/pull/52 Regards, Michel