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                      ]

Am 02.09.2011 19:45, schrieb Krzysztof   elechowski:
>  The expression (*i == *(first2 + (i - first1))) does not have a meaning for
>  input iterators.

I'm not sure, what precisely you mean. In regard to the expression
involving + and -, 25.1 p12 gives a general normative statement:

"they do not have to be defined. In these cases the semantics of a+n is
the same as that of

   X tmp = a;
   advance(tmp, n);
   return tmp;

and that of b-a is the same as of

   return distance(a, b);

One can read that in funny ways, but I think the intention is clear.

In general, the wording state in the whole Clause 25 is very old and not
very good. It was the original hope, that concepts would help to clean
up the language fuzziness here, but they very deferred.

>  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.

Exactly, the requirements are those of i(except for the == operation of
the value type.

>  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.

Yes, the pseudo-code used in Clause 25 is of bad quality. But it would
need a lot of work to clean that up, so *usually* this is done only, if
a clear defect can be isolated.

>  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.

I don't think that the standard has a defect here. I think the effects
of the code make that implicit requirement clear, when it says

"true if for every iterator i in the range [first1,last1) the following
corresponding conditions hold: *i == *(first2 + (i - first1)), pred(*i,
*(first2 + (i - first1))) != false. [..]"

The implication is, that you can increment first2 can be incremented at
least (last1 - first1) in the sense of above quote (i.e.
distance(first1, last1) times) and that the obtained iterator value
after each such incrementation is dereferencable. This requirement does
*not* impose that InputIterator1 must in fact be more than an input
iterator.

Your assertion, "for a general input iterator, there is no way to
predict the length of the sequence starting with first2" is correct, but
that does still not change the requirements on the *algorithm*. It
depends on

>  Example:
>
>  equal (a, a+1, istream_iterator<char>    (cin)); // undefined behavior

I don't see the undefined behavior of this code except that I don't know
what 'a' is, but let's assume, that it is an array, whose element type
is compatible with == between the potentially two different value types.
Here is a full-fledged program:

#include<iostream>
#include<algorithm>
#include<iterator>

int main()
{
   char a[] = {'a'};
   bool res = std::equal(a, a + 1, std::istream_iterator<char>(std::cin));
   std::cout<<  "Result: "<<  res<<  std::endl;
}

The semantics of std::istream_iterator is clearly specified in terms of
extraction operations of the underlying input stream. The *implied*
requirement is, that this input stream *can* read at least one element
successfully, other.

>  The same observations apply, of course, to [alg.mismatch] (which in N3242
>  is, BTW, mis-labelled as [mismatch]).

Sure.

>  Therefore, I would say that std::equal, as it is, really requires a
>  bidirectional iterator.

Why bidirectional?

>  In order to be able to use it with bare input
>  iterators, it would require an overload with last2.
>
>  What do you think?

I disagree with your conclusions and I don't see any reason to increase
the requirements of the here mentioned algorithms. You are describing a
practical problem for *some* input iterator types, but not a fundamental
problem *for the algorithm*. The algorithm clearly implies that number
of valid increments and dereference operations of first2. If the user
cannot guarantee this, this is not the fault of the algorithm
specification. Note, that even in the absence of an explicit
length-awareness via the iterator category, there can still exist
sufficient knowledge via *preconditions* about the capacity of some
specific input iterator. E.g. if I'm using as input iterator a
std::istringstream that reads from string where I know that it's
contents are large enough for the comparison imposed by equal given some
other iterator range, than I'm fine. This example demonstrates that your
example does not proof your hypotheses. It just shows that the algorithm
cannot itself *validate* the input in all cases, but again: This is not
a fundamental defect of the algorithm.

HTH&  Greetings from Bremen,

Daniel Kr  gler




--
[ 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                      ]

On 2011-09-02 17:45:58 +0000, Krzysztof   elechowski said:

>  The expression (*i == *(first2 + (i - first1))) does not have a meaning for
>  input iterators.

See [alg.general]/12:

 In the description of the algorithms operators + and - are used for some
 of the iterator categories for which they do not have to be defined. In these
 cases the semantics of a+n is the same as that of

  X tmp = a;
    advance(tmp, n);
    return tmp;

 and that of b-a is the same as of

  return distance(a, b);

--
  Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)


[ 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                      ]

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                      ]

Pete Becker wrote:

>  On 2011-09-02 17:45:58 +0000, Krzysztof   elechowski said:
>
>>   The expression (*i == *(first2 + (i - first1))) does not have a meaning
>>   for input iterators.
>
>  See [alg.general]/12:
>
>  In the description of the algorithms operators + and - are used for some
>  of the iterator categories for which they do not have to be defined. In
>  these cases the semantics of a+n is the same as that of
>
>  X tmp = a;
>    advance(tmp, n);
>    return tmp;
>
>  and that of b-a is the same as of
>
>  return distance(a, b);
>

Still, what bothers me is that the description of the standard does not
dictate how many times the iterator is advanced.  This is observable when
the advancement has a side effect, like with istreambuf_iterator.

I can imagine an implementation that advances the prescribed number of
times, and then advances the first iterator twice towards the end just for
the fun of it.  I am afraid such an implementation would be conformant.

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                      ]

Am 06.09.2011 00:13, schrieb Krzysztof   elechowski:

[..]

>  Still, what bothers me is that the description of the standard does not
>  dictate how many times the iterator is advanced.  This is observable when
>  the advancement has a side effect, like with istreambuf_iterator.

An implementation has still to satisfy the requirement constraints of
the template arguments. It cannot ignore the "single-pass" constraints
of input iterators, for example.

>  I can imagine an implementation that advances the prescribed number of
>  times, and then advances the first iterator twice towards the end just for
>  the fun of it.  I am afraid such an implementation would be conformant.

Have you found such an implementation in the wild? Even if not, I would
like to see the example code of such a theoretical implementation.

Greetings from Bremen,

Daniel Kr  gler





--
[ 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                      ]