Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_33_1/libs/utility/LessThanComparable.html @ 20

Last change on this file since 20 was 12, checked in by landauf, 18 years ago

added boost
File size: 5.1 KB
Line 
1<HTML>
2<!--
3  -- Copyright (c) Jeremy Siek 2000
4  --
5  -- Permission to use, copy, modify, distribute and sell this software
6  -- and its documentation for any purpose is hereby granted without fee,
7  -- provided that the above copyright notice appears in all copies and
8  -- that both that copyright notice and this permission notice appear
9  -- in supporting documentation.  Silicon Graphics makes no
10  -- representations about the suitability of this software for any
11  -- purpose.  It is provided "as is" without express or implied warranty.
12  -->
13<!--
14  -- Copyright (c) 1996-1999
15  -- Silicon Graphics Computer Systems, Inc.
16  --
17  -- Permission to use, copy, modify, distribute and sell this software
18  -- and its documentation for any purpose is hereby granted without fee,
19  -- provided that the above copyright notice appears in all copies and
20  -- that both that copyright notice and this permission notice appear
21  -- in supporting documentation.  Silicon Graphics makes no
22  -- representations about the suitability of this software for any
23  -- purpose.  It is provided "as is" without express or implied warranty.
24  --
25  -- Copyright (c) 1994
26  -- Hewlett-Packard Company
27  --
28  -- Permission to use, copy, modify, distribute and sell this software
29  -- and its documentation for any purpose is hereby granted without fee,
30  -- provided that the above copyright notice appears in all copies and
31  -- that both that copyright notice and this permission notice appear
32  -- in supporting documentation.  Hewlett-Packard Company makes no
33  -- representations about the suitability of this software for any
34  -- purpose.  It is provided "as is" without express or implied warranty.
35  --
36  -->
37<Head>
38<Title>LessThanComparable</Title>
39</Head>
40<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
41        ALINK="#ff0000"> 
42<IMG SRC="../../boost.png" 
43     ALT="C++ Boost" width="277" height="86"> 
44<!--end header-->
45<BR Clear>
46<H1>LessThanComparable</H1>
47
48<h3>Description</h3>
49A type is LessThanComparable if it is ordered: it must
50be possible to compare two objects of that type using <tt>operator&lt;</tt>, and
51<tt>operator&lt;</tt> must be a strict weak ordering relation.
52
53
54<h3>Refinement of</h3>
55<h3>Associated types</h3>
56<h3>Notation</h3>
57<Table>
58<TR>
59<TD VAlign=top>
60<tt>X</tt>
61</TD>
62<TD VAlign=top>
63A type that is a model of LessThanComparable
64</TD>
65</TR>
66<TR>
67<TD VAlign=top>
68<tt>x</tt>, <tt>y</tt>, <tt>z</tt>
69</TD>
70<TD VAlign=top>
71Object of type <tt>X</tt>
72</TD>
73</tr>
74</table>
75<h3>Definitions</h3>
76Consider the relation <tt>!(x &lt; y) &amp;&amp; !(y &lt; x)</tt>.  If this relation is
77transitive (that is, if <tt>!(x &lt; y) &amp;&amp; !(y &lt; x) &amp;&amp; !(y &lt; z) &amp;&amp; !(z &lt; y)</tt>
78implies <tt>!(x &lt; z) &amp;&amp; !(z &lt; x)</tt>), then it satisfies the mathematical
79definition of an equivalence relation.  In this case, <tt>operator&lt;</tt>
80is a <i>strict weak ordering</i>.
81<P>
82If <tt>operator&lt;</tt> is a strict weak ordering, and if each equivalence class
83has only a single element, then <tt>operator&lt;</tt> is a <i>total ordering</i>.
84<h3>Valid expressions</h3>
85<Table border>
86<TR>
87<TH>
88Name
89</TH>
90<TH>
91Expression
92</TH>
93<TH>
94Type requirements
95</TH>
96<TH>
97Return type
98</TH>
99</TR>
100<TR>
101<TD VAlign=top>
102Less
103</TD>
104<TD VAlign=top>
105<tt>x &lt; y</tt>
106</TD>
107<TD VAlign=top>
108&nbsp;
109</TD>
110<TD VAlign=top>
111Convertible to <tt>bool</tt>
112</TD>
113</TR>
114</table>
115
116
117
118<h3>Expression semantics</h3>
119<Table border>
120<TR>
121<TH>
122Name
123</TH>
124<TH>
125Expression
126</TH>
127<TH>
128Precondition
129</TH>
130<TH>
131Semantics
132</TH>
133<TH>
134Postcondition
135</TH>
136</TR>
137<TR>
138<TD VAlign=top>
139Less
140</TD>
141<TD VAlign=top>
142<tt>x &lt; y</tt>
143</TD>
144<TD VAlign=top>
145<tt>x</tt> and <tt>y</tt> are in the domain of <tt>&lt;</tt>
146</TD>
147<TD VAlign=top>
148&nbsp;
149</TD>
150</table>
151
152
153<h3>Complexity guarantees</h3>
154<h3>Invariants</h3>
155<Table border>
156<TR>
157<TD VAlign=top>
158Irreflexivity
159</TD>
160<TD VAlign=top>
161<tt>x &lt; x</tt> must be false.
162</TD>
163</TR>
164<TR>
165<TD VAlign=top>
166Antisymmetry
167</TD>
168<TD VAlign=top>
169<tt>x &lt; y</tt> implies !(y &lt; x) <A href="#2">[2]</A>
170</TD>
171</TR>
172<TR>
173<TD VAlign=top>
174Transitivity
175</TD>
176<TD VAlign=top>
177<tt>x &lt; y</tt> and <tt>y &lt; z</tt> implies <tt>x &lt; z</tt> <A href="#3">[3]</A>
178</TD>
179</tr>
180</table>
181<h3>Models</h3>
182<UL>
183<LI>
184int
185</UL>
186<h3>Notes</h3>
187<P><A name="1">[1]</A>
188Only <tt>operator&lt;</tt> is fundamental; the other inequality operators
189are essentially syntactic sugar.
190<P><A name="2">[2]</A>
191Antisymmetry is a theorem, not an axiom: it follows from
192irreflexivity and transitivity.
193<P><A name="3">[3]</A>
194Because of irreflexivity and transitivity, <tt>operator&lt;</tt> always
195satisfies the definition of a <i>partial ordering</i>.  The definition of
196a <i>strict weak ordering</i> is stricter, and the definition of a
197<i>total ordering</i> is stricter still.
198<h3>See also</h3>
199<A href="http://www.sgi.com/tech/stl/EqualityComparable.html">EqualityComparable</A>, <A href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">StrictWeakOrdering</A>
200
201
202
203<br>
204<HR>
205<TABLE>
206<TR valign=top>
207<TD nowrap>Copyright &copy 2000</TD><TD>
208<A HREF=http://www.lsc.nd.edu/~jsiek>Jeremy Siek</A>, Univ.of Notre Dame (<A HREF="mailto:jsiek@lsc.nd.edu">jsiek@lsc.nd.edu</A>)
209</TD></TR></TABLE>
210
211</BODY>
212</HTML> 
Note: See TracBrowser for help on using the repository browser.