Using std::equal with an empty set.
in [Visual C]
|
Prev: Bounded Buffers
Next: Operator new
From: Vladimir Grigoriev on 25 Jan 2010 09:06 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 "Igor Tandetnik" <itandetnik(a)mvps.org> wrote in message news:ulcd6EcnKHA.1556(a)TK2MSFTNGP05.phx.gbl... Vladimir Grigoriev wrote: > 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. > 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. -- With best wishes, Igor Tandetnik With sufficient thrust, pigs fly just fine. However, this is not necessarily a good idea. It is hard to be sure where they are going to land, and it could be dangerous sitting under them as they fly overhead. -- RFC 1925
From: Bo Persson on 25 Jan 2010 11:31 Vladimir Grigoriev wrote: > 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 > > Vladimir Grigoriev > > "Igor Tandetnik" <itandetnik(a)mvps.org> wrote in message > news:ulcd6EcnKHA.1556(a)TK2MSFTNGP05.phx.gbl... > Vladimir Grigoriev wrote: >> 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. > >> 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.
From: Vladimir Grigoriev on 25 Jan 2010 11:41 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 "Bo Persson" <bop(a)gmb.dk> wrote in message news:7s5vbdF50jU1(a)mid.individual.net... > Vladimir Grigoriev wrote: >> 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 > > >> >> Vladimir Grigoriev >> >> "Igor Tandetnik" <itandetnik(a)mvps.org> wrote in message >> news:ulcd6EcnKHA.1556(a)TK2MSFTNGP05.phx.gbl... >> Vladimir Grigoriev wrote: >>> 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. >> >>> 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. > > >
From: Ulrich Eckhardt on 25 Jan 2010 13:06 Vladimir Grigoriev wrote: > 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 -- C++ FAQ: http://parashift.com/c++-faq-lite Sator Laser GmbH Geschäftsführer: Thorsten Föcking, Amtsgericht Hamburg HR B62 932
From: Vladimir Grigoriev on 25 Jan 2010 14:01
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 |