Hello,

Cory Nelson wrote:

Andrey Tarasevich wrote:
>Cory Nelson wrote:
Does anyone know how std::set prevents duplicates using only

std::less? ...

And? What exactly is the problem here, in your opinion? If you have a

'less' operation, then equality can be easily defined through it as

follows:

'a equals b' is true if and only if neither 'a less than b' nor 'b

less than

a' is true.

And what? I was just hoping it used some other way than that. That

type of comparison might be rather inefficient if the pred needs to do

a lot of work.

There are 3 different results from the comparision, a<b, a>b, or

neither. You need two comparisions with < to find it out. The

algorithms used for STL need only one comparision for the inner nodes

of the binary search tree used internally, but the left neighbour of

the final position in the tree and the new key will have to be compared

in both ways to avoid duplicates. So there is only one additional

comparision to what the tree traversal already uses.

If an equivalence relation were required additionally to the order

relation, then the interface of the STL classes would be a lot more

difficult, and in general, an equivalence predicate would cost about

the same as the order predicate. To distinguish the three cases we

would need evaluating the order and the equivalence pred each once. So

there is no win to be expected. In more complicated cases the

equivalence predicate cannot be equality, because equality is something

the whole object should be looked at for, where ordering is naturally

done using only a part of the attributes. So the equivalence relation

would have to be something new with no sensible default.

The only chance to really improve something would be some kind of three-

or four-valued logic, i.e. an order function returning

<,>,=,incomparable. But this has the disadvantage, that it would be

overhead for the simple cases, that are to be expected to be the

majority.

Regards,

Bernd Strieder