LessThan Comparable (original) (raw)

SGI

Description

A type is LessThanComparable if it is ordered: it must be possible to compare two objects of that type using operator<, andoperator< must be a partial ordering.

Associated types

Notation

X	A type that is a model of LessThanComparable
x, y, z	Object of type X

Definitions

Consider the relation !(x < y) && !(y < x). If this relation is transitive (that is, if !(x < y) && !(y < x) && !(y < z) && !(z < y)implies !(x < z) && !(z < x)), then it satisfies the mathematical definition of an equivalence relation. In this case, operator<is a strict weak ordering.

If operator< is a strict weak ordering, and if each equivalence class has only a single element, then operator< is a total ordering.

Valid expressions

Name	Expression	Return type
Less	x < y	Convertible to bool
Greater	x > y	Convertible to bool
Less or equal	x <= y	Convertible to bool
Greater or equal	x >= y	Convertible to bool

Expression semantics

Name	Expression	Precondition	Semantics
Less	x < y	x and y are in the domain of <
Greater	x > y	x and y are in the domain of <	Equivalent to y < x [1]
Less or equal	x <= y	x and y are in the domain of <	Equivalent to !(y < x) [1]
Greater or equal	x >= y	x and y are in the domain of <	Equivalent to !(x < y) [1]

Complexity guarantees

Invariants

Irreflexivity	x < x must be false.
Antisymmetry	x < y implies !(y < x) [2]
Transitivity	x < y and y < z implies x < z [3]

Models

Notes

[1]Only operator< is fundamental; the other inequality operators are essentially syntactic sugar.

[2]Antisymmetry is a theorem, not an axiom: it follows from irreflexivity and transitivity.

[3]Because of irreflexivity and transitivity, operator< always satisfies the definition of a partial ordering. The definition of a strict weak ordering is stricter, and the definition of a_total ordering_ is stricter still.