Path: csiph.com!usenet.pasdenom.info!news.albasani.net!.POSTED!not-for-mail From: James Kuyper Newsgroups: comp.std.c++ Subject: Re: Can a striding iterator adaptor be a forward iterator? Date: Sat, 15 Dec 2012 10:53:57 -0800 (PST) Organization: A noiseless patient Spider Lines: 61 Sender: std-cpp-request@vandevoorde.com Approved: stephen.clamage@oracle.com Message-ID: <50CB7905.90004@verizon.net> References: <7dd38eec-6df6-4415-b900-620a67595ef5@googlegroups.com> NNTP-Posting-Host: To+RUUbpiSZPlf9V9Z0+hhjVJrdYvjEuly6TJTDfw7A= Content-Type: text/plain; charset=ISO-8859-1 X-Trace: news.albasani.net RVIHP3vhkW5+I4dDeMqGVsaHoOSbKixxx8u2K0qBTWEK1ruoHhJSwF36DaJ6BmrTPq6tVYCp2YR8h4NL8fOkww== X-Complaints-To: abuse@albasani.net NNTP-Posting-Date: Sat, 15 Dec 2012 18:53:29 +0000 (UTC) X-Mailer: Perl5 Mail::Internet v2.05 X-Submission-Address: std-cpp-submit@vandevoorde.com Cancel-Lock: sha1:7uwUINXTF04cfAaX5yDjH6wotXA= X-Original-Date: Fri, 14 Dec 2012 14:07:49 -0500 Xref: csiph.com comp.std.c++:570 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 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 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 ]