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

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

[alg.equal]: really requires a bidirectional iterator

Followups directed to: comp.std.c++

Show all headers | View raw

The expression (*i == *(first2 + (i - first1))) does not have a meaning for
input iterators.  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.  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.  However, for a general input iterator, there is no way to
predict the length of the sequence starting with first2.

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.

What do you think?

Chris


-- 
[ 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 — Next 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