Hello,
P.J. Plauger wrote:
Quote:
"JDT" <jdt_young@yahoo.comwrote in message
news:jkRZg.16397$e66.7679@newssvr13.news.prodigy.c om...
>
Quote:
>Thanks for the explanation. But an element cannot be deleted even
>after I
>pay attention to your 2nd point. Basically I feed the following
>customized less-than operator into a set. (I hope that the
>fTolerance can
>be as small as possible) One in thousands of elements cannot be
>deleted. I think the operator is only used for sorting/searching, but
>not for the
>final matching. To match an element to be deleted at the end of
>searching, pointers to CSetMember will be used for comparison. Am I
>right? The operator shouldn't cause this type of problem as long as
>it always
>returns a consistent bool value. It really puzzles me ....
>>
>struct lt
>{
> bool operator() (const CSetMember *s1, const CSetMember *s2) const
> {
> float f1 = s1->a * s1->b / s1->c;
> float f2 = s2->a * s2->b / s2->c;
> if (abs(f1-f2) fTolerance)
> return f1 < f2;
> else
> return s1->id < s2->id; // id is a unique integer
> }
>};
>
If this function ever returs true for both lt(s1, s2) and lt(s2, s1)
(and I strongly suspect it does) then it is *not* a strict weak
ordering, and set will not behave properly.
Even worse. It's not symmetry, that is causing the biggest problems with
that functor, but transitivity.
Take 3 objects of type CSetMember c1, c2, c3, where ->a and ->c are 1.0
and c1->b == 0.25*fTolerance c2->b == fTolerance c3->b ==
1.75*fTolerance. Then let c1->id==3, c2->id==2 and c3->id==1.
Then we have lt(c1,c2)==false, lt(c2,c1)== true, lt(c2,c3)==false,
lt(c3,c2)== true, so by transitivity lt(c3,c1) should be true, but
lt(c3,c1) == false and lt(c1,c3)==true. This cannot work in general.
If you want to study the effects of a wrong ordering functor on
std::set, you could for example check the order of the elements after
each insert or erase, but not only the neighbouring elements, try all
kinds of distances between the indexes.
Another problem above is using the absolute error to decide. This made
it really easy to find a counterexample. A better way to compare, if
floating point es involved, is comparing values rounded to the accuracy
the input suggests. Imagine a round(d,n) function rounding d to n
digits after decimal point.
// f1, f2 as above
float c1 = round(f1,4);
float c2 = rounf(f2,4);
if (c1 < c2) return true;
if (c1 == c2) return s1->id < s2->id;
return false;
The OP version cuts the range of numbers into pieces of length
fTolerance, but the points, where the pieces end are different with
every starting point. This must not happen. The discretization should
be uniform over all inputs. If you round your input in a sensible
manner, then you might be able to leave out the rounding inside.
Quite some years ago, I had problems with the qsort function of the
standard C library. It crashed, because it was optimized in a way that
a comparision function, not representing an order as required, would
make it including elements outside the array when sorting. A thrilling
experience.
Bernd Strieder
