In computer science, a three-way comparison takes two values A and B belonging to a type with a total order and determines whether A < B, A = B, or A > B in a single operation, in accordance with the mathematical law of trichotomy.
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, PHP and C++).
Many processors have instruction sets that support such an operation on primitive types. Some machines have signed integers based on a sign-and-magnitude or ones' complement representation (see signed number representations), both of which allow a differentiated positive and negative zero. This does not violate trichotomy as long as a consistent total order is adopted: either −0 = +0 or −0 < +0 is valid. Common floating point types, however, have an exception to trichotomy: there is a special value "NaN" (Not a Number) such that x< NaN, x> NaN, and x = NaN are all false for all floating-point values x (including NaN itself).
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 Perl (for numeric comparisons only, the cmp
operator is used for string lexical comparisons), PHP (since version 7), Ruby, and Apache Groovy, the "spaceship operator" <=>
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]
dataOrdering=LT|EQ|GT
Many object-oriented programming languages have a three-way comparison function, 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. In C++, any class that can be three-way compared can be a parameter to instances of std::compare_three_way
, std::strong_order
, std::weak_order
, or std::partial_order
.
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 arithmetic overflow mentioned below. Many computer languages allow the definition of functions so a compare(A,B) could be devised appropriately, but the question is whether or not its internal definition can employ some sort of three-way syntax or else must fall back on repeated tests.
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 optimization 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 conditional provided by the programming language, Fortran's now-deprecated three-way arithmetic IF statement considers the sign of an arithmetic expression and offers three labels to jump to according to the sign of the result:
IF(expression)negative,zero,positive
The common library function strcmp in C and related languages is a three-way lexicographic comparison of strings; however, these languages lack a general three-way comparison of other data types.
The three-way comparison operator or "spaceship operator" for numbers is denoted as <=>
in Perl, Ruby, Apache Groovy, PHP, Eclipse Ceylon, and C++, and is called the spaceship operator. [2]
In C++, the C++20 revision adds the spaceship operator <=>
, which returns a value that encodes whether the 2 values are equal, less, greater, or unordered and can return different types 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:
echo1<=>1;// 0echo1<=>2;// -1echo2<=>1;// 1
Example in C++:
1<=>1;// evaluates to std::strong_ordering::equal1<=>2;// evaluates to std::strong_ordering::less2<=>1;// evaluates to std::strong_ordering::greater
Three-way comparisons have the property of being easy to compose and build lexicographic comparisons of non-primitive data types, unlike two-way comparisons.
Here is a composition example in Perl.
subcompare($$){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]
In C++:
std::tie(a.unit,a.rank,a.name)<=>std::tie(b.unit,b.rank,b.name)
In computing, NaN, standing for Not a Number, is a particular value of a numeric data type which is undefined as a number, such as the result of 0/0. Systematic use of NaNs was introduced by the IEEE 754 floating-point standard in 1985, along with the representation of other non-finite quantities such as infinities.
A string literal or anonymous string is a literal for a string value in the source code of a computer program. Modern programming languages commonly use a quoted sequence of characters, formally "bracketed delimiters", as in x = "foo"
, where, "foo"
is a string literal with value foo
. Methods such as escape sequences can be used to avoid the problem of delimiter collision and allow the delimiters to be embedded in a string. There are many alternate notations for specifying string literals especially in complicated cases. The exact notation depends on the programming language in question. Nevertheless, there are general guidelines that most modern programming languages follow.
The IEEE Standard for Floating-Point Arithmetic is a technical standard for floating-point arithmetic originally established in 1985 by the Institute of Electrical and Electronics Engineers (IEEE). The standard addressed many problems found in the diverse floating-point implementations that made them difficult to use reliably and portably. Many hardware floating-point units use the IEEE 754 standard.
The syntax of the C programming language is the set of rules governing writing of software in C. It is designed to allow for programs that are extremely terse, have a close relationship with the resulting object code, and yet provide relatively high-level data abstraction. C was the first widely successful high-level language for portable operating-system development.
printf is a C standard library function that formats text and writes it to standard output.
In computer programming, a function object is a construct allowing an object to be invoked or called as if it were an ordinary function, usually with the same syntax. In some languages, particularly C++, function objects are often called functors.
This is a list of operators in the C and C++ programming languages. All the operators listed exist in C++; the column "Included in C", states whether an operator is also present in C. Note that C does not support operator overloading.
In computer programming, the ternary conditional operator is a ternary operator that is part of the syntax for basic conditional expressions in several programming languages. It is commonly referred to as the conditional operator, conditional expression, ternary if, or inline if. An expression if a then b else c
or a ? b : c
evaluates to b
if the value of a
is true, and otherwise to c
. One can read it aloud as "if a then b otherwise c". The form a ? b : c
is the most common, but alternative syntax do exist; for example, Raku uses the syntax a ?? b !! c
to avoid confusion with the infix operators ?
and !
, whereas in Visual Basic .NET, it instead takes the form If(a, b, c)
.
In computer science, the Boolean is a data type that has one of two possible values which is intended to represent the two truth values of logic and Boolean algebra. It is named after George Boole, who first defined an algebraic system of logic in the mid 19th century. The Boolean data type is primarily associated with conditional statements, which allow different actions by changing control flow depending on whether a programmer-specified Boolean condition evaluates to true or false. It is a special case of a more general logical data type—logic does not always need to be Boolean.
In the Perl programming language, autovivification is the automatic creation of new arrays and hashes as required every time an undefined value is dereferenced. Perl autovivification allows a programmer to refer to a structured variable, and arbitrary sub-elements of that structured variable, without expressly declaring the existence of the variable and its complete structure beforehand.
A bit array is an array data structure that compactly stores bits. It can be used to implement a simple set data structure. A bit array is effective at exploiting bit-level parallelism in hardware to perform operations quickly. A typical bit array stores kw bits, where w is the number of bits in the unit of storage, such as a byte or word, and k is some nonnegative integer. If w does not divide the number of bits to be stored, some space is wasted due to internal fragmentation.
In computer science, a relational operator is a programming language construct or operator that tests or defines some kind of relation between two entities. These include numerical equality and inequalities.
In computer programming, the Schwartzian transform is a technique used to improve the efficiency of sorting a list of items. This idiom is appropriate for comparison-based sorting when the ordering is actually based on the ordering of a certain property of the elements, where computing that property is an intensive operation that should be performed a minimal number of times. The Schwartzian transform is notable in that it does not use named temporary arrays.
The computer programming languages C and Pascal have similar times of origin, influences, and purposes. Both were used to design their own compilers early in their lifetimes. The original Pascal definition appeared in 1969 and a first compiler in 1970. The first version of C appeared in 1972.
Signed zero is zero with an associated sign. In ordinary arithmetic, the number 0 does not have a sign, so that −0, +0 and 0 are equivalent. However, in computing, some number representations allow for the existence of two zeros, often denoted by −0 and +0, regarded as equal by the numerical comparison operations but with possible different behaviors in particular operations. This occurs in the sign-magnitude and ones' complement signed number representations for integers, and in most floating-point number representations. The number 0 is usually encoded as +0, but can still be represented by +0, −0, or 0.
String functions are used in computer programming languages to manipulate a string or query information about a string.
The syntax of the Python programming language is the set of rules that defines how a Python program will be written and interpreted. The Python language has many similarities to Perl, C, and Java. However, there are some definite differences between the languages. It supports multiple programming paradigms, including structured, object-oriented programming, and functional programming, and boasts a dynamic type system and automatic memory management.
The null coalescing operator is a binary operator that is part of the syntax for a basic conditional expression in several programming languages, such as : C# since version 2.0, Dart since version 1.12.0, PHP since version 7.0.0, Perl since version 5.10 as logical defined-or, PowerShell since 7.0.0, and Swift as nil-coalescing operator.
This article compares a large number of programming languages by tabulating their data types, their expression, statement, and declaration syntax, and some common operating-system interfaces.
In computer programming, ellipsis notation is used to denote ranges, an unspecified number of arguments, or a parent directory. Most programming languages require the ellipsis to be written as a series of periods; a single (Unicode) ellipsis character cannot be used.
<=>
syntax, in a paper entitled "Consistent Comparison". See "Consistent Comparison" It was successfully merged into the C++20 draft in November 2017.