Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!news.albasani.net!.POSTED!not-for-mail From: Dave Abrahams Newsgroups: comp.std.c++ Subject: Re: [alg.equal]: really requires a bidirectional iterator Date: Sat, 3 Sep 2011 14:36:32 -0700 (PDT) Organization: unknown Lines: 62 Sender: std-cpp-request@vandevoorde.com Approved: stephen.clamage@oracle.com Message-ID: References: Content-Type: text/plain; charset=utf-8 X-Trace: news.albasani.net oJ/oV5RRl0+pnQ0K0BqOBgm5XIC7Q/WSuRlfr1nhJpFRANyAp110zYx3dL781WkhR1AWZO2Fk99ikuHqKjaRPg== NNTP-Posting-Date: Sat, 3 Sep 2011 21:36:33 +0000 (UTC) Injection-Info: news.albasani.net; logging-data="juqnIaCZTudd2BJAqRPFdd3Jg6t9oDljT7qTxJ6O5Nw6OvDjBok27iI5FcG1MT38P5wm0D0aAK004qK4S3/xrXpNnQ/lFttNAdzyALQ3o4+GngjOZRrL4ZXHadSS5cAU"; mail-complaints-to="abuse@albasani.net" X-Mailer: Perl5 Mail::Internet v2.05 X-Submission-Address: std-cpp-submit@vandevoorde.com Cancel-Lock: sha1:/WJQx2/r0egI3zFa3IGJm56ZqTc= X-Original-Date: Fri, 02 Sep 2011 11:23:58 -0800 Xref: x330-a1.tempe.blueboxinc.net comp.std.c++:271 on Fri Sep 02 2011, Krzysztof Żelechowski wrote: > The expression (*i == *(first2 + (i - first1))) does not have a meaning for > input iterators. It does. > Moreover, IMHO, the only way of explaining the working of this > algorithm is by providing a reference implementation in the > documentation because it is not possible to talk about "derived input > iterators"; we can only talk about the state of the iterator at a > given execution step. I don't know what derivation has to do with it, but there's a clause in the library standard that lets us describe input- and bidirectional- iterator semantics in terms of math that would normally require random access iterators. Am I missing something? > While the reference implementation need not be in C++ code; any > description that refers values of variables across different stages of > execution (thereby tagging the references to variables with a step > number) is kind of pseudocode. > > What I am more worried about is that the text does not mention that the > sequence starting with first2 is at least as long as the sequence from > first1 to last1; failing to meet this requirement results in undefined > behaviour. That in itself asserts the requirement. > However, for a general input iterator, there is no way to predict the > length of the sequence starting with first2. The answer, if you can't be sure of the length, is "don't use this algorithm." > Example: > > equal (a, a+1, istream_iterator (cin)); // undefined behavior > > The same observations apply, of course, to [alg.mismatch] (which in N3242 > is, BTW, mis-labelled as [mismatch]). > > Therefore, I would say that std::equal, as it is, really requires a > bidirectional iterator. In order to be able to use it with bare input > iterators, it would require an overload with last2. I think having that overload might amount to an improvement, but it's not a defect that we don't have it. -- Dave Abrahams BoostPro Computing http://www.boostpro.com [ 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 ]