1<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> 2 3<html> 4<!-- 5 == Copyright (c) 1996-1999 6 == Silicon Graphics Computer Systems, Inc. 7 == 8 == Permission to use, copy, modify, distribute and sell this software 9 == and its documentation for any purpose is hereby granted without fee, 10 == provided that the above copyright notice appears in all copies and 11 == that both that copyright notice and this permission notice appear 12 == in supporting documentation. Silicon Graphics makes no 13 == representations about the suitability of this software for any 14 == purpose. It is provided "as is" without express or implied warranty. 15 == 16 == Copyright (c) 1994 17 == Hewlett-Packard Company 18 == 19 == Permission to use, copy, modify, distribute and sell this software 20 == and its documentation for any purpose is hereby granted without fee, 21 == provided that the above copyright notice appears in all copies and 22 == that both that copyright notice and this permission notice appear 23 == in supporting documentation. Hewlett-Packard Company makes no 24 == representations about the suitability of this software for any 25 == purpose. It is provided "as is" without express or implied warranty. 26 == 27 --> 28 29<head> 30 <meta http-equiv="Content-Language" content="en-us"> 31 <meta http-equiv="Content-Type" content="text/html; charset=us-ascii"> 32 33 <title>LessThanComparable</title> 34</head> 35 36<body bgcolor="#FFFFFF" link="#0000EE" text="#000000" vlink="#551A8B" alink= 37"#FF0000"> 38 <img src="../../boost.png" alt="C++ Boost" width="277" height= 39 "86"><br clear="none"> 40 41 <h1>LessThanComparable</h1> 42 43 <h3>Description</h3> 44 45 <p>A type is LessThanComparable if it is ordered: it must be possible to 46 compare two objects of that type using <tt>operator<</tt>, and 47 <tt>operator<</tt> must be a strict weak ordering relation.</p> 48 49 <h3>Refinement of</h3> 50 51 <h3>Associated types</h3> 52 53 <h3>Notation</h3> 54 55 <table summary=""> 56 <tr> 57 <td valign="top"><tt>X</tt></td> 58 59 <td valign="top">A type that is a model of LessThanComparable</td> 60 </tr> 61 62 <tr> 63 <td valign="top"><tt>x</tt>, <tt>y</tt>, <tt>z</tt></td> 64 65 <td valign="top">Object of type <tt>X</tt></td> 66 </tr> 67 </table> 68 69 <h3>Definitions</h3> 70 71 <p>Consider the relation <tt>!(x < y) && !(y < x)</tt>. If 72 this relation is transitive (that is, if <tt>!(x < y) && !(y 73 < x) && !(y < z) && !(z < y)</tt> implies <tt>!(x 74 < z) && !(z < x)</tt>), then it satisfies the mathematical 75 definition of an equivalence relation. In this case, <tt>operator<</tt> 76 is a <i>strict weak ordering</i>.</p> 77 78 <p>If <tt>operator<</tt> is a strict weak ordering, and if each 79 equivalence class has only a single element, then <tt>operator<</tt> is 80 a <i>total ordering</i>.</p> 81 82 <h3>Valid expressions</h3> 83 84 <table border summary=""> 85 <tr> 86 <th>Name</th> 87 88 <th>Expression</th> 89 90 <th>Type requirements</th> 91 92 <th>Return type</th> 93 </tr> 94 95 <tr> 96 <td valign="top">Less</td> 97 98 <td valign="top"><tt>x < y</tt></td> 99 100 <td valign="top"> </td> 101 102 <td valign="top">Convertible to <tt>bool</tt></td> 103 </tr> 104 </table> 105 106 <h3>Expression semantics</h3> 107 108 <table border summary=""> 109 <tr> 110 <th>Name</th> 111 112 <th>Expression</th> 113 114 <th>Precondition</th> 115 116 <th>Semantics</th> 117 118 <th>Postcondition</th> 119 </tr> 120 121 <tr> 122 <td valign="top">Less</td> 123 124 <td valign="top"><tt>x < y</tt></td> 125 126 <td valign="top"><tt>x</tt> and <tt>y</tt> are in the domain of 127 <tt><</tt></td> 128 129 <td valign="top"> </td> 130 </tr> 131 </table> 132 133 <h3>Complexity guarantees</h3> 134 135 <h3>Invariants</h3> 136 137 <table border summary=""> 138 <tr> 139 <td valign="top">Irreflexivity</td> 140 141 <td valign="top"><tt>x < x</tt> must be false.</td> 142 </tr> 143 144 <tr> 145 <td valign="top">Antisymmetry</td> 146 147 <td valign="top"><tt>x < y</tt> implies !(y < x) <a href= 148 "#n2">[2]</a></td> 149 </tr> 150 151 <tr> 152 <td valign="top">Transitivity</td> 153 154 <td valign="top"><tt>x < y</tt> and <tt>y < z</tt> implies <tt>x 155 < z</tt> <a href="#n3">[3]</a></td> 156 </tr> 157 </table> 158 159 <h3>Models</h3> 160 161 <ul> 162 <li>int</li> 163 </ul> 164 165 <h3>Notes</h3> 166 167 <p><a name="n1" id="n1">[1]</a> Only <tt>operator<</tt> is fundamental; 168 the other inequality operators are essentially syntactic sugar.</p> 169 170 <p><a name="n2" id="n2">[2]</a> Antisymmetry is a theorem, not an axiom: it 171 follows from irreflexivity and transitivity.</p> 172 173 <p><a name="n3" id="n3">[3]</a> Because of irreflexivity and transitivity, 174 <tt>operator<</tt> always satisfies the definition of a <i>partial 175 ordering</i>. The definition of a <i>strict weak ordering</i> is stricter, 176 and the definition of a <i>total ordering</i> is stricter still.</p> 177 178 <h3>See also</h3> 179 180 <p><a href= 181 "http://www.sgi.com/tech/stl/EqualityComparable.html">EqualityComparable</a>, 182 <a href= 183 "http://www.sgi.com/tech/stl/StrictWeakOrdering.html">StrictWeakOrdering</a><br> 184 </p> 185 <hr> 186 187 <p><a href="http://validator.w3.org/check?uri=referer"><img border="0" src= 188 "../../doc/images/valid-html401.png" alt="Valid HTML 4.01 Transitional" 189 height="31" width="88"></a></p> 190 191 <p>Revised 192 <!--webbot bot="Timestamp" s-type="EDITED" s-format="%d %B, %Y" startspan -->05 193 December, 2006<!--webbot bot="Timestamp" endspan i-checksum="38516" --></p> 194 195 <table summary=""> 196 <tr valign="top"> 197 <td nowrap><i>Copyright © 2000</i></td> 198 199 <td><i><a href="http://www.lsc.nd.edu/~jsiek">Jeremy Siek</a>, Univ.of 200 Notre Dame (<a href= 201 "mailto:jsiek@lsc.nd.edu">jsiek@lsc.nd.edu</a>)</i></td> 202 </tr> 203 </table> 204 205 <p><i>Distributed under the Boost Software License, Version 1.0. (See 206 accompanying file <a href="../../LICENSE_1_0.txt">LICENSE_1_0.txt</a> or 207 copy at <a href= 208 "http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</a>)</i></p> 209</body> 210</html> 211
