Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.std.c++ > #569

Re: Can a striding iterator adaptor be a forward iterator?

Show all headers | View raw

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                      ]

Back to comp.std.c++ | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Can a striding iterator adaptor be a forward iterator? ricilake@googlemail.com - 2012-12-14 09:20 -0800
  Re: Can a striding iterator adaptor be a forward iterator? Daniel Krügler <daniel.kruegler@googlemail.com> - 2012-12-15 10:53 -0800
    Re: Can a striding iterator adaptor be a forward iterator? ricilake@googlemail.com - 2012-12-17 08:52 -0800
  Re: Can a striding iterator adaptor be a forward iterator? James Kuyper <jameskuyper@verizon.net> - 2012-12-15 10:53 -0800

csiph-web