Книга: Standard Template Library Programmer
LessThan Comparable
Разделы на этой странице:
LessThan Comparable
Category: utilities
Component type: concept
Description
A type is LessThanComparable if it is ordered: it must be possible to compare two objects of that type using operator<, and operator< must be a partial ordering.
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] |
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
• int
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.
See also
EqualityComparable, StrictWeakOrdering
Оглавление книги
