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

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

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

Show all headers | View raw

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                      ]

Back to comp.std.c++ | Previous | Next — Previous 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