| [29] | 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 | "http://www.w3.org/Icons/valid-html401" 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> |
|---|
