LessThanComparable.html 5.9 KB

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