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

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

Re: [alg.equal]: really requires a bidirectional iterator

Show key headers only | View raw

on Fri Sep 02 2011, Krzysztof Żelechowski<giecrilj-AT-stegny.2a.pl>  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<char>   (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                      ]

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

Thread

[alg.equal]: really requires a bidirectional iterator Krzysztof Żelechowski<giecrilj@stegny.2a.pl> - 2011-09-02 10:45 -0700
  Re: [alg.equal]: really requires a bidirectional iterator Daniel Krügler<daniel.kruegler@googlemail.com> - 2011-09-03 14:36 -0700
  Re: [alg.equal]: really requires a bidirectional iterator Pete Becker<pete@versatilecoding.com> - 2011-09-03 14:36 -0700
    Re: [alg.equal]: really requires a bidirectional iterator Krzysztof Żelechowski<giecrilj@stegny.2a.pl> - 2011-09-05 15:13 -0700
      Re: [alg.equal]: really requires a bidirectional iterator Daniel Krügler<daniel.kruegler@googlemail.com> - 2011-09-06 11:19 -0700
  Re: [alg.equal]: really requires a bidirectional iterator Dave Abrahams<dave@boostpro.com> - 2011-09-03 14:36 -0700

csiph-web