Find if two variables are equal only with less than operator

Question

I am trying to implement a binary search tree and I need a function which tells me if an element already exists in the tree or not! However the only operator I can use is < . Is this even possible?

I have already tried (a<b) || (b<a) and !(a<b) && !(b<a)

Note: I am only allowed to use < to compare my elements in the binary tree.

Answer 1

You can write in C++

not ( a < b or b < a )

that is equivalent to

not ( a < b ) and not ( b < a )

Though for the binary search tree that expression is not required because usually it is enough to use if_else statements like

if ( a < b )
{
    // ...
}
else if ( b < a )
{
    //...
}
else /* a == b */
{
    //...
}

Answer 2

You cannot guarantee, given only an implementation of operator<, that a == b.

This is because there exists a concept called "Partial Ordering", which may, under unusual circumstances, permit a scenario where two objects can be conditionally ordered against each other.

Consider, as an example, a graph describing class inheritance. We could define the following rules:

• Class A is equal to Class B if A and B describe the same class.
• Class A is greater than Class B if A is a superclass of B or is a superclass of a superclass of B or so on (B inherits from A, or B inherits from C which inherits from A, etc.)
• Class A is less than Class B if A is a subclass of B (A inherits from B, or A inherits from C which inherits from B, etc.)
• Class A is not ordered with respect to Class B if they have no relation to each other (A does not inherit from B, and B does not inherit from A)
• Class A is not ordered with respect to Class B if they both inherit from the same superclass, but otherwise have no relation (A inherits from C, B inherits from C)
• Class A is not ordered with respect to Class B if they are mutually inherited from the same subclass, but otherwise have no relation (C inherits from both A and B)

This makes it fully plausible that, given the following function:

std::string compare(T const& a, T const& b) {
    if(a == b) 
        return "Equal to";
    else if(a < b) 
        return "Less than";
    else if(a <= b) 
        return "Less than or Equal to";
    else if(a > b) 
        return "Greater than";
    else if(a >= b) 
        return "Greater than or Equal to";
    else 
        return "Unordered to";
}

The output could be "Unordered to", given some inputs.

The only way to guarantee that two generic arguments are equal to each other is to have an overload for operator==.

Now, the good news for you is that if you're constructing a Binary Search Tree, there's an unwritten convention that the types being used to compare against should be, at the very least, weakly ordered (which means a==b will return the same as !(a < b || b < a)). So in your specific circumstances, so long as the provided key value is weakly ordered, !(a < b || b < a) will always return true when the objects are equal.

But you do need some mechanism to ensure the user doesn't try to pass a partially ordered key to your comparison function. Otherwise, you're stuck requiring a full operator== implementation.

P.S: Before someone jumps in and says "What about arithmetic types?", I would remind you that NaN exists for IEEE-compliant Floating point values, where a < b and b < a can both return false. a == b can also return false if both a and b are NaN, even if both NaN values have the same payload! Additionally, this relationship is only guaranteed for integers in a twos-compliment representation, which the C++ standard does not require.