I think there is an example of a striding iterator adaptor in "C++ Cookbook" (Cogswell, Diggins&  Stephens, 2006, O'Reilly) but the idea is simple enough: I create a striding adaptor with something like:

     striding_iterator<typename decltype(c)::iterator>  every_third(c.begin(), 3);

and then I use it, as indicated, to reference every third element. (Some mechanics are necessary in order to create an end iterator, but it's feasible enough and that's not my question.)

The problem comes when I create another one:

     striding_iterator<typename decltype(c)::iterator>  every_fifth(c.begin(), 6);

Now I advance the first one five times and the second one three times, and compare them for equality. They both reference the same underlying element, so according to 24.2.5 paragraph(6):

>  If a and b are both dereferenceable, then a == b if and only if *a and *b are bound to the same object

So they should compare equal, which is what I did. (The Cookbook implementation asserts, which seems wrong to me.)

However, I just noticed 24.2.5 paragraph(3) which defines the "multi-pass guarantee" which requires that:

>  a == b implies ++a == ++b

However, that's certainly not true of the striding iterators, unless the stride is the same.

And 24.2.5 paragraph(1) insists that X is a forward iterator only if

>  objects of type X offer the multi-pass guarantee,

Now, am I incorrect to tag this adaptor as a forward_iterator (or bidirectional_iterator, if the underlying iterator is bidirectional)? Is that an intentional prohibition?

Clearly I could create a templated collection of striding adaptors with compile-time fixed strides, which would not trigger this problem. However, restricting the strides to compile-time expressions would not fit my use case.


--
[ comp.std.c++ is moderated.  To submit articles, try posting with your ]
[ newsreader.  If that fails, use mailto:std-cpp-submit@vandevoorde.com ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Am 14.12.2012 18:20, schrieb ricilake@googlemail.com:
> I think there is an example of a striding iterator adaptor in "C++ Cookbook" (Cogswell, Diggins&  Stephens, 2006, O'Reilly) but the idea is simple enough: I create a striding adaptor with something like:
>
>       striding_iterator<typename decltype(c)::iterator>  every_third(c.begin(), 3);
>
> and then I use it, as indicated, to reference every third element. (Some mechanics are necessary in order to create an end iterator, but it's feasible enough and that's not my question.)

I assume that typename decltype(c)::iterator is required to be (at
least) a forward iterator for the sake of this discussion.

> The problem comes when I create another one:
>
>       striding_iterator<typename decltype(c)::iterator>  every_fifth(c.begin(), 6);
>
> Now I advance the first one five times and the second one three times, and compare them for equality. They both reference the same underlying element, so according to 24.2.5 paragraph(6):

Your counting scheme is a bit inconsistent, but I'm ignoring this aspect
for the moment.

>>   If a and b are both dereferenceable, then a == b if and only if *a and *b are bound to the same object
>
> So they should compare equal, which is what I did. (The Cookbook implementation asserts, which seems wrong to me.)
>
> However, I just noticed 24.2.5 paragraph(3) which defines the "multi-pass guarantee" which requires that:
>
>>   a == b implies ++a == ++b
>
> However, that's certainly not true of the striding iterators, unless the stride is the same.

I agree.

> And 24.2.5 paragraph(1) insists that X is a forward iterator only if
>
>>   objects of type X offer the multi-pass guarantee,
>
> Now, am I incorrect to tag this adaptor as a forward_iterator (or bidirectional_iterator, if the underlying iterator is bidirectional)? Is that an intentional prohibition?

I wonder why you would consider to allow for mixing iterators with
different strides in general iterator algorithms? I think this would the
definition of a valid range already dubious. For example 24.2.1 says:

"An iterator j is called reachable from an iterator i if and only if
there is a finite sequence of applications of the expression ++i that
makes i == j. If j is reachable from i, they refer to elements of the
same sequence."

If you have i and j stride iterators with different strides and you
would allow for comparing iterator values with different stride values.
In particular I don't think that the constraint

"in general, a range [i,j) refers to the elements in the data structure
starting with the element pointed to by i and up to but not including
the element pointed to by j."

is satisfied. Both iterators traverse over *different* sequences.

> Clearly I could create a templated collection of striding adaptors with compile-time fixed strides, which would not trigger this problem. However, restricting the strides to compile-time expressions would not fit my use case.

I don't see a problem to describe the static property of a striding
iterator as forward iterator, it is just the fact that two iterators
over different strides do not refer to the same sequence and it would be
undefined behaviour to attempt to do so.

HTH & Greetings from Bremen,

Daniel Kr   gler



--
[ comp.std.c++ is moderated.  To submit articles, try posting with your ]
[ newsreader.  If that fails, use mailto:std-cpp-submit@vandevoorde.com ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On 12/14/2012 12:20 PM, ricilake@googlemail.com wrote:
> I think there is an example of a striding iterator adaptor in "C++ Cookbook" (Cogswell, Diggins&  Stephens, 2006, O'Reilly) but the idea is simple enough: I create a striding adaptor with something like:
>
>      striding_iterator<typename decltype(c)::iterator>  every_third(c.begin(), 3);
>
> and then I use it, as indicated, to reference every third element. (Some mechanics are necessary in order to create an end iterator, but it's feasible enough and that's not my question.)
>
> The problem comes when I create another one:
>
>      striding_iterator<typename decltype(c)::iterator>  every_fifth(c.begin(), 6);
>
> Now I advance the first one five times and the second one three times, and compare them for equality. They both reference the same underlying element, so according to 24.2.5 paragraph(6):
>
>>  If a and b are both dereferenceable, then a == b if and only if *a and *b are bound to the same object
>
> So they should compare equal, which is what I did. (The Cookbook implementation asserts, which seems wrong to me.)
>
> However, I just noticed 24.2.5 paragraph(3) which defines the "multi-pass guarantee" which requires that:
>
>>  a == b implies ++a == ++b
>
> However, that's certainly not true of the striding iterators, unless the stride is the same.
>
> And 24.2.5 paragraph(1) insists that X is a forward iterator only if
>
>>  objects of type X offer the multi-pass guarantee,
>
> Now, am I incorrect to tag this adaptor as a forward_iterator (or bidirectional_iterator, if the underlying iterator is bidirectional)? Is that an intentional prohibition?

I believe that it would indeed be incorrect. I can't be sure whether
it's intentional; I would not be surprised to learn that the committee
did not even think of anything similar to your striding iterators when
putting the requirements together. However, if they had thought about
it, I think they would have expected the stride of the iterator to be a
template parameter. I certainly did; I had to start over again and
re-read your message when I realized that you had not in fact defined
them that way. If you had, iterators with different strides would have
had different types. Since the requirements are specific to a single
type of iterator, such a design would have completely avoided the problem.

> Clearly I could create a templated collection of striding adaptors with compile-time fixed strides, which would not trigger this problem. However, restricting the strides to compile-time expressions would not fit my use case.

By making the stride a function parameter of the constructor, rather
than a template parameter, you've put incompatible iterators together
into a single type, making it impossible to meet these requirements.
These requirements are intended to enable developers of algorithms that
are templated by iterator type to know what they can count on being able
to do with these iterators, despite not knowing in advance what type
they will be instantiated with. The features that prevent your iterator
types from qualifying as multi-pass could interfere with algorithms that
rely upon that guarantee. I'll leave it as a exercise for the student to
come up with an algorithm which would break for that reason; it's
relatively straightforward to do, but more work than I have time for
right now.


--
[ comp.std.c++ is moderated.  To submit articles, try posting with your ]
[ newsreader.  If that fails, use mailto:std-cpp-submit@vandevoorde.com ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On Saturday, 15 December 2012 13:53:32 UTC-5, Daniel Kr   gler  wrote:
>  Am 14.12.2012 18:20, schrieb ricilake:
>
>  >        striding_iterator<typename decltype(c)::iterator>   every_third(c.begin(), 3);
>
>  I assume that typename decltype(c)::iterator is required to be (at
>  least) a forward iterator for the sake of this discussion.
>
Yes. If it were an input iterator, so would be the striding iterator and the question wouldn't apply.
>
>  >  The problem comes when I create another one:
>
>  >        striding_iterator<typename decltype(c)::iterator>   every_fifth(c.begin(), 6);
>
>  Your counting scheme is a bit inconsistent, but I'm ignoring this aspect
>  for the moment.

Oops. As one ages, the eyes grow dimmer and the fingers less nimble; not a good combination if one wants to avoid looking like an idiot in public.

>  >  Now I advance the first one five times and the second one three times, and compare them for equality. They both reference the same underlying element, so according to 24.2.5 paragraph(6):
>
>  >  >    If a and b are both dereferenceable, then a == b if and only if *a and *b are bound to the same object
>
>  >  However, I just noticed 24.2.5 paragraph(3) which defines the "multi-pass guarantee" which requires that:
>
>  >>    a == b implies ++a == ++b
>
>  >  However, that's certainly not true of the striding iterators, unless the stride is the same.
>
>  I agree.
>
>  >  Now, am I incorrect to tag this adaptor as a forward_iterator (or bidirectional_iterator, if the underlying iterator is bidirectional)? Is that an intentional prohibition?
>
>  I wonder why you would consider to allow for mixing iterators with
>  different strides in general iterator algorithms?

I didn't really want to. My initial reading of the standard, in particular 24.2.5/6 (quoted above), lead me to believe that I had to permit the comparison of iterators with different strides if they were bound to the same object.

>  I think this would the
>  definition of a valid range already dubious. For example 24.2.1 says:
>
>  "An iterator j is called reachable from an iterator i if and only if
>  there is a finite sequence of applications of the expression ++i that
>  makes i == j. If j is reachable from i, they refer to elements of the
>  same sequence."
>
>  If you have i and j stride iterators with different strides and you
>  would allow for comparing iterator values with different stride values.
>  In particular I don't think that the constraint
>
>  "in general, a range [i,j) refers to the elements in the data structure
>  starting with the element pointed to by i and up to but not including
>  the element pointed to by j."
>
>  is satisfied. Both iterators traverse over *different* sequences.
>

Right. I think that's the crux of the question.

>
>
>  I don't see a problem to describe the static property of a striding
>  iterator as forward iterator, it is just the fact that two iterators
>  over different strides do not refer to the same sequence and it would be
>  undefined behaviour to attempt to do so.
>

That's certainly the conclusion I came to after a private discussion with James Kuyper, during which I convinced myself -- if not him -- that the intent of the wording in the standard was exactly as you've described it and that it was legitimate for me to implement any behaviour (asserting, returning false, etc.) when comparing two deferenceable iterators with different strides. (For ease of implementation, I currently return true when comparing any two non-dereferenceable iterators, but UB permits that as well.)

But I think the standard here is less than clear. 24.2.5/2 says that the domain of == is iterators over the same underlying sequence, but "underlying sequence" isn't well-defined. The attempt to define it in 24.2.1/6 in terms of reachability is circular, because reachability is defined in terms of ==. 24.2.5/6 (a == b iff a and b are bound to the same object) might be an attempt to cut the Gordian knot, but as I think this question illustrates, it's overly demanding in the face of "view" iterators unless you accept a definition of "bound to" which is so idiosyncratic that it at least needs to be spelled out.

A literal interpretation of 24.2.5/6 would also make proxy iterators difficult or impossible. You could, barely, stretch "bound to" to an extra level of indirection, allowing two iterators to each maintain their own value_type&  member and be compared on the basis of the underlying value_type rather than the proxy reference member itself (which is, I think, technically what the iterator is bound to). But how would you extend that to a proxy const_iterator implementing some sort of function transform? Now you have to say that "bound to" is referring to an object whose type is nowhere visible in the public interface of the iterator.

In short, I think that 24.2.5/6 is at best easy to misinterpret, and there should probably be a DR filed. I'd volunteer to do so, but I don't yet think I have a good proposal for fixing it.


--
[ comp.std.c++ is moderated.  To submit articles, try posting with your ]
[ newsreader.  If that fails, use mailto:std-cpp-submit@vandevoorde.com ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]