Using std::equal with an empty set.

[Vladimir Grigoriev]

What should return the std::equal in case when [first, last) is an empty
set, true or false?

Vladimir Grigoriev

[Igor Tandetnik]

Post by Vladimir Grigoriev
What should return the std::equal in case when [first, last) is an empty
set, true or false?

true

[Vladimir Grigoriev]

From mathematical point of view an empty set is a subset of any set indeed.
However if to follow the Standard description it seems that in this case
std::equal must return false. Because according to the Standard the
following for example condition must hold

pred( *i, *( first2 + ( i - first1 ) ) )

As this condition does not hold for any itearator from [first, last) why
should std::equal return true?

Vladimir Grigoriev

Post by Vladimir Grigoriev
What should return the std::equal in case when [first, last) is an empty
set, true or false?

true

[Ulrich Eckhardt]

Post by Vladimir Grigoriev
From mathematical point of view an empty set is a subset of any set
indeed. However if to follow the Standard description it seems that in
this case std::equal must return false. Because according to the
Standard the following for example condition must hold
pred( *i, *( first2 + ( i - first1 ) ) )
As this condition does not hold for any itearator from [first, last) why
should std::equal return true?

Actually, that condition holds for all elements in that range. Note that
there are effectively no dereferenceable iterators in that range because
first==last, hence also no elements. Note that the STL docs are probably
more explicit there, they are talking about two subsets of equal length
that are compared.

BTW, since you seem to look for thing you can flag as ambiguous (is it a
crusade you're on, btw?), also consider that string("abc").find("") returns
zero. ;)

Good luck!

Uli

[Igor Tandetnik]

Post by Vladimir Grigoriev
From mathematical point of view an empty set is a subset of any set indeed.
However if to follow the Standard description it seems that in this case
std::equal must return false. Because according to the Standard the
following for example condition must hold
pred( *i, *( first2 + ( i - first1 ) ) )

It must hold for every iterator in the range [first, last). If there are no such iterators, then indeed the condition trivially holds for all of them. See also

http://en.wikipedia.org/wiki/Vacuous_truth

This is standard fare in predicate logic.

Post by Vladimir Grigoriev
As this condition does not hold for any itearator from [first, last)

You are committing a logical fallacy. The negation of "for all iterators in the range, the condition holds" is not "for all iterators in the range, the condition doesn't hold". It is "there exists an iterator in the range for which the condition doesn't hold". This last statement is obviously false when the range is empty, so the first statement must be true.

[Vladimir Grigoriev]

Well, I am citing the Standard "Returns true if *for every* iterator i in
the range [first1, last1) the following corresponding conditions ho;d *i ==
*( first2 + ( i - first1 ) )...*Otherwise* returns false."

I believe that when the interval is empty then *otherwise* is true!:)

Vladimir Grigoriev

Post by Vladimir Grigoriev
From mathematical point of view an empty set is a subset of any set indeed.
However if to follow the Standard description it seems that in this case
std::equal must return false. Because according to the Standard the
following for example condition must hold
pred( *i, *( first2 + ( i - first1 ) ) )

It must hold for every iterator in the range [first, last). If there are no
such iterators, then indeed the condition trivially holds for all of them.
See also

http://en.wikipedia.org/wiki/Vacuous_truth

This is standard fare in predicate logic.

Post by Vladimir Grigoriev
As this condition does not hold for any itearator from [first, last)

You are committing a logical fallacy. The negation of "for all iterators in
the range, the condition holds" is not "for all iterators in the range, the
condition doesn't hold". It is "there exists an iterator in the range for
which the condition doesn't hold". This last statement is obviously false
when the range is empty, so the first statement must be true.

[Bo Persson]

Post by Vladimir Grigoriev
Well, I am citing the Standard "Returns true if *for every*
iterator i in the range [first1, last1) the following corresponding
conditions ho;d *i == *( first2 + ( i - first1 ) )...*Otherwise*
returns false."
I believe that when the interval is empty then *otherwise* is
true!:)

Right, so you have found an iterator for which the condition isn't
true? No?


Bo Persson

Post by Vladimir Grigoriev
Vladimir Grigoriev

Post by Vladimir Grigoriev
From mathematical point of view an empty set is a subset of any set indeed.
However if to follow the Standard description it seems that in
this case std::equal must return false. Because according to the
Standard the following for example condition must hold
pred( *i, *( first2 + ( i - first1 ) ) )

It must hold for every iterator in the range [first, last). If
there are no such iterators, then indeed the condition trivially
holds for all of them. See also
http://en.wikipedia.org/wiki/Vacuous_truth
This is standard fare in predicate logic.

Post by Vladimir Grigoriev
As this condition does not hold for any itearator from [first, last)

You are committing a logical fallacy. The negation of "for all
iterators in the range, the condition holds" is not "for all
iterators in the range, the condition doesn't hold". It is "there
exists an iterator in the range for which the condition doesn't
hold". This last statement is obviously false when the range is
empty, so the first statement must be true.

[Vladimir Grigoriev]

No I did not found. So the "otherwise" is true!
I think that the Standard must states explicitly that in case of an empty
set the algorithm must return true. Now reding existent comments in the
Standard it is unclear.

Vladimir Grigoriev

Post by Vladimir Grigoriev
Well, I am citing the Standard "Returns true if *for every*
iterator i in the range [first1, last1) the following corresponding
conditions ho;d *i == *( first2 + ( i - first1 ) )...*Otherwise*
returns false."
I believe that when the interval is empty then *otherwise* is
true!:)

Right, so you have found an iterator for which the condition isn't true?
No?
Bo Persson

Post by Vladimir Grigoriev
Vladimir Grigoriev

Post by Vladimir Grigoriev
From mathematical point of view an empty set is a subset of any set indeed.
However if to follow the Standard description it seems that in
this case std::equal must return false. Because according to the
Standard the following for example condition must hold
pred( *i, *( first2 + ( i - first1 ) ) )

It must hold for every iterator in the range [first, last). If
there are no such iterators, then indeed the condition trivially
holds for all of them. See also
http://en.wikipedia.org/wiki/Vacuous_truth
This is standard fare in predicate logic.

Post by Vladimir Grigoriev
As this condition does not hold for any itearator from [first, last)

You are committing a logical fallacy. The negation of "for all
iterators in the range, the condition holds" is not "for all
iterators in the range, the condition doesn't hold". It is "there
exists an iterator in the range for which the condition doesn't
hold". This last statement is obviously false when the range is
empty, so the first statement must be true.

[Igor Tandetnik]

Post by Vladimir Grigoriev
No I did not found. So the "otherwise" is true!

Pardon? You are saying: "the statement is wrong, but I can't produce any counterexample disproving it - therefore the statement is wrong". How does this make any sense?

Post by Vladimir Grigoriev
I think that the Standard must states explicitly that in case of an
empty set the algorithm must return true. Now reding existent
comments in the Standard it is unclear.

So far, it is clear to every participant in this thread - except you. Perhaps the problem is not with the standard after all?

[Vladimir Grigoriev]

No, you are interpreting me incorrectly. I have pointed out already why the
algorithm must return false. It must return false because the statement
'Otherwise' is true. The true is returned in only one case when "for every
iterator i in the range [first1, last1) the following corresponding
conditions hold.."'. Are you have at least one iterator which satisfies the
conditions? No, you have not. If I cannot even check the conditions why the
algorithm should return true?! For this case there is the phrase "Otherwise
returns false".

Vladimir Grigoriev

Post by Vladimir Grigoriev
No I did not found. So the "otherwise" is true!

Pardon? You are saying: "the statement is wrong, but I can't produce any
counterexample disproving it - therefore the statement is wrong". How does
this make any sense?

Post by Vladimir Grigoriev
I think that the Standard must states explicitly that in case of an
empty set the algorithm must return true. Now reding existent
comments in the Standard it is unclear.

So far, it is clear to every participant in this thread - except you.
Perhaps the problem is not with the standard after all?

[Ulrich Eckhardt]

I have pointed out already why the algorithm must return false. It must
return false because the statement 'Otherwise' is true. The true is
returned in only one case when "for every iterator i in the range
[first1, last1) the following corresponding conditions hold.."'. Are
you have at least one iterator which satisfies the conditions? No,
you have not. If I cannot even check the conditions why the
algorithm should return true?! For this case there is the phrase
"Otherwise returns false".

Please stop. Sorry, but if you knew anything at all about the STL, where
these algorithms come from, you wouldn't be surprised about this. Take a
look at [1], it say there very explicitly, though technically redundantly,
that it compares two ranges.

Now, where is the second range? There is just one iterator after all! Simple
answer, the second range is assumed to have the same length as the first,
even though no past-the-end iterator is supplied. One result of this is
that if the first sequence is empty, the second one is empty, too, and they
are alway equal. Someone posted a link here already which even gives this
principle a name.

BTW: If the range starting at the second iterator is shorter, you get
undefined behaviour. If it is longer, only a subset is compared.

Now, if you want to say that the wording in the standard can be improved,
then say so. Preferably do so to people that care, you were given direction
elsethreads. But, please stop making those nonsense claims that comparison
of two empty sequences should return false and stop wasting everyone's
time.

Seriously, I'm wondering if you're not just an elaborated troll.

Uli

[1] http://www.sgi.com/tech/stl/equal.html

[Vladimir Grigoriev]

Ulrich, It is not so obvious thing as you think. It is obvious for you
because your have much expirience with algorithms. However if to approch
literally to the Standard description questions arise.

Vladimir Grigoriev

[Ulrich Eckhardt]

Post by Vladimir Grigoriev
Ulrich, It is not so obvious thing as you think. It is obvious for you
because your have much expirience with algorithms. However if to approch
literally to the Standard description questions arise.

So you don't have a good foundation of experience but already are wise
enough to detect yet another "foolishness of the C++ Standard"? Sorry, but
that attitude sucks.

Suggestion: Take a look at "Design and Evolution of C++" by Stroustrup
(IIRC), which not only documents how things are (as the standard does) but
also why and how they developed. Then, get familiar with the STL-derived
part of C++, I would even suggest reading the STL documentation instead,
which is a bit more verbose than the standard. Then, when you have an
overview, we can start arguing about whether a definition is good or bad.

Anyway, I'm out of here.

Uli

[Vladimir Grigoriev]

Post by Ulrich Eckhardt

Post by Vladimir Grigoriev
Ulrich, It is not so obvious thing as you think. It is obvious for you
because your have much expirience with algorithms. However if to approch
literally to the Standard description questions arise.

So you don't have a good foundation of experience but already are wise
enough to detect yet another "foolishness of the C++ Standard"? Sorry, but
that attitude sucks.

Yes, I am wise enough to detect yet another foolishness because this
demonstrates that for newcomers the description of the Standard is not clear
enough! For example till now I have not the answer on the question why may
not std::greater_equal be used with the std::min or std::min_element.

Post by Ulrich Eckhardt
Suggestion: Take a look at "Design and Evolution of C++" by Stroustrup
(IIRC), which not only documents how things are (as the standard does) but
also why and how they developed. Then, get familiar with the STL-derived
part of C++, I would even suggest reading the STL documentation instead,
which is a bit more verbose than the standard. Then, when you have an
overview, we can start arguing about whether a definition is good or bad.

Thanks, I am reading. For example I have read in the "C++ in a nutshell" of
Ray Lischner that I may use operator -( 42, 10 ) while here others say that
I may not. This demonstrates one more that the Standard description is not
clear enough even for experienced C++ programmers.

Vladimir Grigoriev

[Igor Tandetnik]

Post by Vladimir Grigoriev
No, you are interpreting me incorrectly. I have pointed out already
why the algorithm must return false.

And you were wrong in this assertion.

Post by Vladimir Grigoriev
It must return false because the
statement 'Otherwise' is true.

No it's not.

Post by Vladimir Grigoriev
The true is returned in only one case
when "for every iterator i in the range [first1, last1) the following
corresponding conditions hold.."'.

Which is true for an empty range.

Post by Vladimir Grigoriev
Are you have at least one iterator
which satisfies the conditions?

For that statement to be true, it is not required that one existed.

Post by Vladimir Grigoriev
No, you have not. If I cannot even
check the conditions why the algorithm should return true?!

You can check the condition. Just iterate over the range and confirm that the condition holds for all its elements.

Post by Vladimir Grigoriev
For this
case there is the phrase "Otherwise returns false".

This phrase covers the case where the previous statement is false. But in the case of an empty range, the statement is true, and thus "otherwise" clause doesn't apply.

[Igor Tandetnik]

Post by Vladimir Grigoriev
Well, I am citing the Standard "Returns true if *for every* iterator
i in the range [first1, last1) the following corresponding conditions
ho;d *i == *( first2 + ( i - first1 ) )...*Otherwise* returns false."
I believe that when the interval is empty then *otherwise* is true!:)

Suppose you are right, and it is false that the condition holds for every iterator in an empty range. Then there must exist an iterator in that range for which the condition doesn't hold. But the range is empty and doesn't contain any iterators at all. We arrived at a contradiction. Therefore, we conclude that your claim is wrong - the condition does hold for every iterator in the range. QED.

Have you read the article I referred you to? It explains the concept of vacuous truth, the concept you seem to be struggling with.

[Vladimir Grigoriev]

Igor, I could say the same! Suppose you are right. Can you point at least
one iterator for which the condition is true?
The problem is that in mathematics it is no more than an agreement . It
should be proclaimed explicitly. However in the Standard this is not
proclaimed.

Vladimir Grigoriev

Post by Vladimir Grigoriev
Well, I am citing the Standard "Returns true if *for every* iterator
i in the range [first1, last1) the following corresponding conditions
ho;d *i == *( first2 + ( i - first1 ) )...*Otherwise* returns false."
I believe that when the interval is empty then *otherwise* is true!:)

Suppose you are right, and it is false that the condition holds for every
iterator in an empty range. Then there must exist an iterator in that range
for which the condition doesn't hold. But the range is empty and doesn't
contain any iterators at all. We arrived at a contradiction. Therefore, we
conclude that your claim is wrong - the condition does hold for every
iterator in the range. QED.

Have you read the article I referred you to? It explains the concept of
vacuous truth, the concept you seem to be struggling with.

[Igor Tandetnik]

Post by Vladimir Grigoriev
Igor, I could say the same! Suppose you are right. Can you point at
least one iterator for which the condition is true?

No. But that doesn't prove your case.

So, it is false that "there exists an element in the set for which the condition is true". Negating this, we can conclude that it is true that "for all elements in the set, the condition is false". However, this doesn't contradict the statement "for all elements in the set, the condition is true" - it only demonstrates that the set in question is empty.

In fact, showing that "for all x in A: P(x)" and "for all x in A: !P(x)" are simultaneously true is a fairly common technique for proving that A is an empty set.

This is Logic 101 stuff. With all due respect, you may want to re-read your favorite textbook on the subect.

Post by Vladimir Grigoriev
The problem is that in mathematics it is no more than an agreement .

Of course. So is human language - are you going to redefine the meaning of words next, Humpty-Dumpty style?

Post by Vladimir Grigoriev
It should be proclaimed explicitly. However in the Standard this is
not proclaimed.

You don't really expect every text to build mathematical foundations from scratch, do you? All scientific and technical literature assumes some shared body of knowledge between authors and readers. Textbooks are there to help one acquire that knowledge.

[Vladimir Grigoriev]

Well, I have been induced.

Vladimir Grigoriev

Post by Vladimir Grigoriev
Igor, I could say the same! Suppose you are right. Can you point at
least one iterator for which the condition is true?

No. But that doesn't prove your case.

So, it is false that "there exists an element in the set for which the
condition is true". Negating this, we can conclude that it is true that "for
all elements in the set, the condition is false". However, this doesn't
contradict the statement "for all elements in the set, the condition is
true" - it only demonstrates that the set in question is empty.

In fact, showing that "for all x in A: P(x)" and "for all x in A: !P(x)" are
simultaneously true is a fairly common technique for proving that A is an
empty set.

This is Logic 101 stuff. With all due respect, you may want to re-read your
favorite textbook on the subect.

Post by Vladimir Grigoriev
The problem is that in mathematics it is no more than an agreement .

Of course. So is human language - are you going to redefine the meaning of
words next, Humpty-Dumpty style?

Post by Vladimir Grigoriev
It should be proclaimed explicitly. However in the Standard this is
not proclaimed.

You don't really expect every text to build mathematical foundations from
scratch, do you? All scientific and technical literature assumes some shared
body of knowledge between authors and readers. Textbooks are there to help
one acquire that knowledge.

[Tim Roberts]

Post by Vladimir Grigoriev
Well, I am citing the Standard "Returns true if *for every* iterator i in
the range [first1, last1) the following corresponding conditions ho;d *i ==
*( first2 + ( i - first1 ) )...*Otherwise* returns false."
I believe that when the interval is empty then *otherwise* is true!:)

Allow me to word that sentence in a slightly different but logically
equivalent way:

"If there is any iterator i in the range [first1,last1) where the condition
does not hold, return false. Otherwise, return true."

What would you return now?

[Vladimir Grigoriev]

Tim, I am dealing with what is written in the Standard but not with how you
interpret it.:)

Vladimir Grigoriev

Post by Tim Roberts

Post by Vladimir Grigoriev
Well, I am citing the Standard "Returns true if *for every* iterator i in
the range [first1, last1) the following corresponding conditions ho;d *i ==
*( first2 + ( i - first1 ) )...*Otherwise* returns false."
I believe that when the interval is empty then *otherwise* is true!:)

Allow me to word that sentence in a slightly different but logically
"If there is any iterator i in the range [first1,last1) where the condition
does not hold, return false. Otherwise, return true."
What would you return now?
--
Providenza & Boekelheide, Inc.