From -8428388595986639381 X-Google-Thread: f78e5,e1cf64e55daed60f X-Google-NewGroupId: yes X-Google-Attributes: gid7894ca11fe,domainid0,public,usenet X-Google-Language: ENGLISH,ASCII Received: by 10.180.87.165 with SMTP id az5mr3273343wib.1.1355763142386; Mon, 17 Dec 2012 08:52:22 -0800 (PST) MIME-Version: 1.0 Path: i11ni202803wiw.0!nntp.google.com!proxad.net!feeder1-2.proxad.net!feeder.erje.net!eu.feeder.erje.net!news.albasani.net!.POSTED!not-for-mail From: ricilake@googlemail.com Newsgroups: comp.std.c++ Subject: Re: Can a striding iterator adaptor be a forward iterator? Date: Mon, 17 Dec 2012 08:52:59 -0800 (PST) Organization: unknown Lines: 81 Sender: std-cpp-request@vandevoorde.com Approved: stephen.clamage@oracle.com Message-ID: <163e7bd3-c549-4462-b3b4-135fb4fc3038@googlegroups.com> References: <7dd38eec-6df6-4415-b900-620a67595ef5@googlegroups.com> NNTP-Posting-Host: OSLLVZ8gzIxnaxnHmejn/flJ06ozu8eG6B1bS3uHn40= X-Trace: news.albasani.net QurbJW/emLad39T9QsyBJ1jNIOtr9rHiizpz9hg2sN7OUjuXxJtwO2MLiLm6YBkcvkuu12lPJYGq0LDOYjbu4g== X-Complaints-To: abuse@albasani.net NNTP-Posting-Date: Mon, 17 Dec 2012 16:52:22 +0000 (UTC) X-Mailer: Perl5 Mail::Internet v2.05 X-Submission-Address: std-cpp-submit@vandevoorde.com Cancel-Lock: sha1:crSL4F1teNS9qCD4WiWs35tT5jI= X-Original-Date: Sat, 15 Dec 2012 14:38:35 -0800 (PST) Content-Type: text/plain; charset=ISO-8859-1 On Saturday, 15 December 2012 13:53:32 UTC-5, Daniel Kr�gler wrote: > Am 14.12.2012 18:20, schrieb ricilake: > > > striding_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 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 ]