Gitiles
Code Review Sign In
realtimeroboticsgroup.org / RealtimeRoboticsGroup / test / 60e3e2a569af91782db93c94d6a26b82137e1c67 / . / LessThanComparable.html
blob: 15b938fc5d285cb1a1366726394f586ed96b3383 [file] [log] [blame]
Brian Silverman60e3e2a2018-08-04 23:57:12 -0700[diff] [blame^]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&lt;</tt>, and
47 <tt>operator&lt;</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 &lt; y) &amp;&amp; !(y &lt; x)</tt>. If
72 this relation is transitive (that is, if <tt>!(x &lt; y) &amp;&amp; !(y
73 &lt; x) &amp;&amp; !(y &lt; z) &amp;&amp; !(z &lt; y)</tt> implies <tt>!(x
74 &lt; z) &amp;&amp; !(z &lt; x)</tt>), then it satisfies the mathematical
75 definition of an equivalence relation. In this case, <tt>operator&lt;</tt>
76 is a <i>strict weak ordering</i>.</p>
77
78 <p>If <tt>operator&lt;</tt> is a strict weak ordering, and if each
79 equivalence class has only a single element, then <tt>operator&lt;</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 &lt; y</tt></td>
99
100 <td valign="top">&nbsp;</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 &lt; y</tt></td>
125
126 <td valign="top"><tt>x</tt> and <tt>y</tt> are in the domain of
127 <tt>&lt;</tt></td>
128
129 <td valign="top">&nbsp;</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 &lt; x</tt> must be false.</td>
142 </tr>
143
144 <tr>
145 <td valign="top">Antisymmetry</td>
146
147 <td valign="top"><tt>x &lt; y</tt> implies !(y &lt; 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 &lt; y</tt> and <tt>y &lt; z</tt> implies <tt>x
155 &lt; 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&lt;</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&lt;</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 &copy; 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>