Three-way comparison
In
It can be implemented in terms of a function (such as strcmp
in C), a method (such as compareTo
in Java), or an operator (such as the spaceship operator <=>
in Perl).
Machine-level computation
Many processors have
High-level languages
Abilities
In C, the functions strcmp
and memcmp
perform a three-way comparison between strings and memory buffers, respectively. They return a negative number when the first argument is lexicographically smaller than the second, zero when the arguments are equal, and a positive number otherwise. This convention of returning the "sign of the difference" is extended to arbitrary comparison functions by the standard sorting function qsort
, which takes a comparison function as an argument and requires it to abide by it.
In
<=>
returns the values −1, 0, or 1 depending on whether A < B, A = B, or A > B, respectively. The Python 2.x cmp
(removed in 3.x), OCaml compare
, and Kotlin compareTo
functions compute the same thing. In the Haskell standard library, the three-way comparison function compare
is defined for all types in the Ord
class; it returns type Ordering
, whose values are LT
(less than), EQ
(equal), and GT
(greater than):[1]data Ordering = LT | EQ | GT
Many object-oriented programming languages have a three-way comparison method, which performs a three-way comparison between the object and another given object. For example, in Java, any class that implements the Comparable
interface has a compareTo
method which either returns a negative integer, zero, or a positive integer, or throws a NullPointerException
(if one or both objects are null
). Similarly, in the .NET framework, any class that implements the IComparable
interface has such a CompareTo
method.
Since Java version 1.5, the same can be computed using the Math.signum
static method if the difference can be known without computational problems such as
When implementing a three-way comparison where a three-way comparison operator or method is not already available, it is common to combine two comparisons, such as A = B and A < B, or A < B and A > B. In principle, a compiler might deduce that these two expressions could be replaced by only one comparison followed by multiple tests of the result, but mention of this optimisation is not to be found in texts on the subject.
In some cases, three-way comparison can be simulated by subtracting A and B and examining the sign of the result, exploiting special instructions for examining the sign of a number. However, this requires the type of A and B to have a well-defined difference. Fixed-width signed integers may overflow when they are subtracted, floating-point numbers have the value NaN with undefined sign, and character strings have no difference function corresponding to their total order. At the machine level, overflow is usually tracked and can be used to determine order after subtraction, but this information is usually unavailable to higher-level languages.
In one case of a three-way
IF (expression) negative,zero,positive
The common library function
Spaceship operator
The three-way comparison operator or "spaceship operator" for numbers is denoted as <=>
in
In C++, the C++20 revision adds the spaceship operator <=>
, which similarly returns the sign of the difference and can also return different types (convertible to signed integers) depending on the strictness of the comparison.[3]
The name's origin is due to it reminding Randal L. Schwartz of the spaceship in an HP BASIC Star Trek game.[4] Another coder has suggested that it was so named because it looked similar to Darth Vader's TIE fighter in the Star Wars saga.[5]
Example in PHP:
echo 1 <=> 1; // 0
echo 1 <=> 2; // -1
echo 2 <=> 1; // 1
Composite data types
Three-way comparisons have the property of being easy to compose and build
Here is a composition example in Perl.
sub compare($$) {
my ($a, $b) = @_;
return $a->{unit} cmp $b->{unit}
|| $a->{rank} <=> $b->{rank}
|| $a->{name} cmp $b->{name};
}
Note that cmp
, in Perl, is for strings, since <=>
is for numbers. Two-way equivalents tend to be less compact but not necessarily less legible. The above takes advantage of short-circuit evaluation of the ||
operator, and the fact that 0 is considered false in Perl. As a result, if the first comparison is equal (thus evaluates to 0), it will "fall through" to the second comparison, and so on, until it finds one that is non-zero, or until it reaches the end.
In some languages, including Python, Ruby, Haskell, etc., comparison of lists is done lexicographically, which means that it is possible to build a chain of comparisons like the above example by putting the values into lists in the order desired; for example, in Ruby:
[a.unit, a.rank, a.name] <=> [b.unit, b.rank, b.name]
See also
- strcmp
References
- ^ Data.Ord
- ^ "Math::Complex". Perl Programming Documentation. Retrieved 26 September 2014.
- ^ Herb Sutter proposed adding a three-way comparison operator to the C++ standard with the
<=>
syntax, in a paper entitled "Consistent Comparison". See "Consistent Comparison" It was successfully merged into the C++20 draft in November 2017. - ^ "Spaceship history (was Re: [dart-misc] DEP meeting notes)".
- ^ "Super Spaceship Operator". 2000-12-08. Retrieved 2014-08-06.