首頁 探索 說明
註冊 登入
devn00b
/
EQ2EMu
9
3
複刻 0
Files 問題管理 59
目錄樹: d98db1aa33
分支列表 標籤列表
EQ2EMu
/
EQ2
/
source
/
depends
/
boost_1_72_0
/
libs
/
icl
/
doc
/
html
/
boost_icl
/
semantics
/
collectors__maps_of_sets.html

collectors__maps_of_sets.html 32 KB
文件歷史 原始文件

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231 
  1. <html>
    2. 

  2. <head>
    3. 

  3. <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
    4. 

  4. <title>Collectors: Maps of Sets</title>
    5. 

  5. <link rel="stylesheet" href="../../../../../../doc/src/boostbook.css" type="text/css">
    6. 

  6. <meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
    7. 

  7. <link rel="home" href="../../index.html" title="Chapter&#160;1.&#160;Boost.Icl">
    8. 

  8. <link rel="up" href="../semantics.html" title="Semantics">
    9. 

  9. <link rel="prev" href="maps.html" title="Maps">
    10. 

  10. <link rel="next" href="quantifiers__maps_of_numbers.html" title="Quantifiers: Maps of Numbers">
    11. 

  11. </head>
    12. 

  12. <body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
    13. 

  13. <table cellpadding="2" width="100%"><tr>
    14. 

  14. <td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td>
    15. 

  15. <td align="center"><a href="../../../../../../index.html">Home</a></td>
    16. 

  16. <td align="center"><a href="../../../../../libraries.htm">Libraries</a></td>
    17. 

  17. <td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
    18. 

  18. <td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
    19. 

  19. <td align="center"><a href="../../../../../../more/index.htm">More</a></td>
    20. 

  20. </tr></table>
    21. 

  21. <hr>
    22. 

  22. <div class="spirit-nav">
    23. 

  23. <a accesskey="p" href="maps.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../semantics.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="quantifiers__maps_of_numbers.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
    24. 

  24. </div>
    25. 

  25. <div class="section">
    26. 

  26. <div class="titlepage"><div><div><h3 class="title">
    27. 

  27. <a name="boost_icl.semantics.collectors__maps_of_sets"></a><a class="link" href="collectors__maps_of_sets.html" title="Collectors: Maps of Sets">Collectors:
    28. 

  28.       Maps of Sets</a>
    29. 

  29. </h3></div></div></div>
    30. 

  30. <p>
    31. 

  31.         Icl <code class="computeroutput"><span class="identifier">Collectors</span></code>, behave like
    32. 

  32.         <code class="computeroutput"><span class="identifier">Sets</span></code>. This can be understood
    33. 

  33.         easily, if we consider, that every map of sets can be transformed to an equivalent
    34. 

  34.         set of pairs. For instance in the pseudocode below map <code class="computeroutput"><span class="identifier">m</span></code>
    35. 

  35. </p>
    36. 

  36. <pre class="programlisting"><span class="identifier">icl</span><span class="special">::</span><span class="identifier">map</span><span class="special">&lt;</span><span class="keyword">int</span><span class="special">,</span><span class="identifier">set</span><span class="special">&lt;</span><span class="keyword">int</span><span class="special">&gt;</span> <span class="special">&gt;</span>  <span class="identifier">m</span> <span class="special">=</span> <span class="special">{(</span><span class="number">1</span><span class="special">-&gt;{</span><span class="number">1</span><span class="special">,</span><span class="number">2</span><span class="special">}),</span> <span class="special">(</span><span class="number">2</span><span class="special">-&gt;{</span><span class="number">1</span><span class="special">})};</span>
    37. 

  37. </pre>
    38. 

  38. <p>
    39. 

  39.         is equivalent to set <code class="computeroutput"><span class="identifier">s</span></code>
    40. 

  40. </p>
    41. 

  41. <pre class="programlisting"><span class="identifier">icl</span><span class="special">::</span><span class="identifier">set</span><span class="special">&lt;</span><span class="identifier">pair</span><span class="special">&lt;</span><span class="keyword">int</span><span class="special">,</span><span class="keyword">int</span><span class="special">&gt;</span> <span class="special">&gt;</span> <span class="identifier">s</span> <span class="special">=</span> <span class="special">{(</span><span class="number">1</span><span class="special">,</span><span class="number">1</span><span class="special">),(</span><span class="number">1</span><span class="special">,</span><span class="number">2</span><span class="special">),</span>   <span class="comment">//representing 1-&gt;{1,2}</span>
    42. 

  42.                               <span class="special">(</span><span class="number">2</span><span class="special">,</span><span class="number">1</span><span class="special">)</span>       <span class="special">};</span> <span class="comment">//representing 2-&gt;{1}</span>
    43. 

  43. </pre>
    44. 

  44. <p>
    45. 

  45.       </p>
    46. 

  46. <p>
    47. 

  47.         Also the results of add, subtract and other operations on <code class="computeroutput"><span class="identifier">map</span>
    48. 

  48.         <span class="identifier">m</span></code> and <code class="computeroutput"><span class="identifier">set</span>
    49. 

  49.         <span class="identifier">s</span></code> preserves the equivalence of
    50. 

  50.         the containers <span class="emphasis"><em><span class="bold"><strong>almost</strong></span></em></span>
    51. 

  51.         perfectly:
    52. 

  52. </p>
    53. 

  53. <pre class="programlisting"><span class="identifier">m</span> <span class="special">+=</span> <span class="special">(</span><span class="number">1</span><span class="special">,</span><span class="number">3</span><span class="special">);</span>
    54. 

  54. <span class="identifier">m</span> <span class="special">==</span> <span class="special">{(</span><span class="number">1</span><span class="special">-&gt;{</span><span class="number">1</span><span class="special">,</span><span class="number">2</span><span class="special">,</span><span class="number">3</span><span class="special">}),</span> <span class="special">(</span><span class="number">2</span><span class="special">-&gt;{</span><span class="number">1</span><span class="special">})};</span> <span class="comment">//aggregated on collision of key value 1</span>
    55. 

  55. <span class="identifier">s</span> <span class="special">+=</span> <span class="special">(</span><span class="number">1</span><span class="special">,</span><span class="number">3</span><span class="special">);</span>
    56. 

  56. <span class="identifier">s</span> <span class="special">==</span> <span class="special">{(</span><span class="number">1</span><span class="special">,</span><span class="number">1</span><span class="special">),(</span><span class="number">1</span><span class="special">,</span><span class="number">2</span><span class="special">),(</span><span class="number">1</span><span class="special">,</span><span class="number">3</span><span class="special">),</span>   <span class="comment">//representing 1-&gt;{1,2,3}</span>
    57. 

  57.       <span class="special">(</span><span class="number">2</span><span class="special">,</span><span class="number">1</span><span class="special">)</span>             <span class="special">};</span> <span class="comment">//representing 2-&gt;{1}</span>
    58. 

  58. </pre>
    59. 

  59. <p>
    60. 

  60.       </p>
    61. 

  61. <p>
    62. 

  62.         The equivalence of <code class="computeroutput"><span class="identifier">m</span></code> and
    63. 

  63.         <code class="computeroutput"><span class="identifier">s</span></code> is only violated if an
    64. 

  64.         empty set occurres in <code class="computeroutput"><span class="identifier">m</span></code> by
    65. 

  65.         subtraction of a value pair:
    66. 

  66. </p>
    67. 

  67. <pre class="programlisting"><span class="identifier">m</span> <span class="special">-=</span> <span class="special">(</span><span class="number">2</span><span class="special">,</span><span class="number">1</span><span class="special">);</span>
    68. 

  68. <span class="identifier">m</span> <span class="special">==</span> <span class="special">{(</span><span class="number">1</span><span class="special">-&gt;{</span><span class="number">1</span><span class="special">,</span><span class="number">2</span><span class="special">,</span><span class="number">3</span><span class="special">}),</span> <span class="special">(</span><span class="number">2</span><span class="special">-&gt;{})};</span> <span class="comment">//aggregated on collision of key value 2</span>
    69. 

  69. <span class="identifier">s</span> <span class="special">-=</span> <span class="special">(</span><span class="number">2</span><span class="special">,</span><span class="number">1</span><span class="special">);</span>
    70. 

  70. <span class="identifier">s</span> <span class="special">==</span> <span class="special">{(</span><span class="number">1</span><span class="special">,</span><span class="number">1</span><span class="special">),(</span><span class="number">1</span><span class="special">,</span><span class="number">2</span><span class="special">),(</span><span class="number">1</span><span class="special">,</span><span class="number">3</span><span class="special">)</span>   <span class="comment">//representing 1-&gt;{1,2,3}</span>
    71. 

  71.                        <span class="special">};</span> <span class="comment">//2-&gt;{} is not represented in s</span>
    72. 

  72. </pre>
    73. 

  73. <p>
    74. 

  74.       </p>
    75. 

  75. <p>
    76. 

  76.         This problem can be dealt with in two ways.
    77. 

  77.       </p>
    78. 

  78. <div class="orderedlist"><ol class="orderedlist" type="1">
    79. 

  79. <li class="listitem">
    80. 

  80.             Deleting value pairs form the Collector, if it's associated value becomes
    81. 

  81.             a neutral value or <code class="computeroutput"><span class="identifier">identity_element</span></code>.
    82. 

  82.           </li>
    83. 

  83. <li class="listitem">
    84. 

  84.             Using a different equality, called distinct equality in the laws to validate.
    85. 

  85.             Distinct equality only accounts for value pairs that that carry values
    86. 

  86.             unequal to the <code class="computeroutput"><span class="identifier">identity_element</span></code>.
    87. 

  87.           </li>
    88. 

  88. </ol></div>
    89. 

  89. <p>
    90. 

  90.         Solution (1) led to the introduction of map traits, particularly trait <span class="emphasis"><em><span class="bold"><strong>partial_absorber</strong></span></em></span>, which is the default
    91. 

  91.         setting in all icl's map templates.
    92. 

  92.       </p>
    93. 

  93. <p>
    94. 

  94.         Solution (2), is applied to check the semantics of icl::Maps for the partial_enricher
    95. 

  95.         trait that does not delete value pairs that carry identity elements. Distinct
    96. 

  96.         equality is implemented by a non member function called <code class="computeroutput"><span class="identifier">is_distinct_equal</span></code>.
    97. 

  97.         Throughout this chapter distinct equality in pseudocode and law denotations
    98. 

  98.         is denoted as <code class="computeroutput"><span class="special">=</span><span class="identifier">d</span><span class="special">=</span></code> operator.
    99. 

  99.       </p>
    100. 

  100. <p>
    101. 

  101.         The validity of the sets of laws that make up <code class="computeroutput"><span class="identifier">Set</span></code>
    102. 

  102.         semantics should now be quite evident. So the following text shows the laws
    103. 

  103.         that are validated for all <code class="computeroutput"><span class="identifier">Collector</span></code>
    104. 

  104.         types <code class="computeroutput"><span class="identifier">C</span></code>. Which are <code class="computeroutput"><a class="link" href="../../boost/icl/map.html" title="Class template map">icl::map</a></code><code class="computeroutput"><span class="special">&lt;</span><span class="identifier">D</span><span class="special">,</span><span class="identifier">S</span><span class="special">,</span><span class="identifier">T</span><span class="special">&gt;</span></code>,
    105. 

  105.         <code class="computeroutput"><a class="link" href="../../boost/icl/interval_map.html" title="Class template interval_map">interval_map</a></code><code class="computeroutput"><span class="special">&lt;</span><span class="identifier">D</span><span class="special">,</span><span class="identifier">S</span><span class="special">,</span><span class="identifier">T</span><span class="special">&gt;</span></code> and <code class="computeroutput"><a class="link" href="../../boost/icl/split_interval_map.html" title="Class template split_interval_map">split_interval_map</a></code><code class="computeroutput"><span class="special">&lt;</span><span class="identifier">D</span><span class="special">,</span><span class="identifier">S</span><span class="special">,</span><span class="identifier">T</span><span class="special">&gt;</span></code> where <code class="computeroutput"><span class="identifier">CodomainT</span></code>
    106. 

  106.         type <code class="computeroutput"><span class="identifier">S</span></code> is a model of <code class="computeroutput"><span class="identifier">Set</span></code> and <code class="computeroutput"><span class="identifier">Trait</span></code>
    107. 

  107.         type <code class="computeroutput"><span class="identifier">T</span></code> is either <code class="computeroutput"><a class="link" href="../../boost/icl/partial_absorber.html" title="Struct partial_absorber">partial_absorber</a></code> or <code class="computeroutput"><a class="link" href="../../boost/icl/partial_enricher.html" title="Struct partial_enricher">partial_enricher</a></code>.
    108. 

  108.       </p>
    109. 

  109. <h6>
    110. 

  110. <a name="boost_icl.semantics.collectors__maps_of_sets.h0"></a>
    111. 

  111.         <span class="phrase"><a name="boost_icl.semantics.collectors__maps_of_sets.laws_on_set_union__set_intersection_and_set_difference"></a></span><a class="link" href="collectors__maps_of_sets.html#boost_icl.semantics.collectors__maps_of_sets.laws_on_set_union__set_intersection_and_set_difference">Laws
    112. 

  112.         on set union, set intersection and set difference</a>
    113. 

  113.       </h6>
    114. 

  114. <p>
    115. 

  115. </p>
    116. 

  116. <pre class="programlisting"><span class="identifier">Associativity</span><span class="special">&lt;</span><span class="identifier">C</span><span class="special">,+,==</span> <span class="special">&gt;:</span> <span class="identifier">C</span> <span class="identifier">a</span><span class="special">,</span><span class="identifier">b</span><span class="special">,</span><span class="identifier">c</span><span class="special">;</span> <span class="identifier">a</span><span class="special">+(</span><span class="identifier">b</span><span class="special">+</span><span class="identifier">c</span><span class="special">)</span> <span class="special">==</span> <span class="special">(</span><span class="identifier">a</span><span class="special">+</span><span class="identifier">b</span><span class="special">)+</span><span class="identifier">c</span>
    117. 

  117. <span class="identifier">Neutrality</span><span class="special">&lt;</span><span class="identifier">C</span><span class="special">,+,==</span> <span class="special">&gt;</span>   <span class="special">:</span> <span class="identifier">C</span> <span class="identifier">a</span><span class="special">;</span>       <span class="identifier">a</span><span class="special">+</span><span class="identifier">C</span><span class="special">()</span> <span class="special">==</span> <span class="identifier">a</span>
    118. 

  118. <span class="identifier">Commutativity</span><span class="special">&lt;</span><span class="identifier">C</span><span class="special">,+,==</span> <span class="special">&gt;:</span> <span class="identifier">C</span> <span class="identifier">a</span><span class="special">,</span><span class="identifier">b</span><span class="special">;</span>       <span class="identifier">a</span><span class="special">+</span><span class="identifier">b</span> <span class="special">==</span> <span class="identifier">b</span><span class="special">+</span><span class="identifier">a</span>
    119. 

  119. 

  120. <span class="identifier">Associativity</span><span class="special">&lt;</span><span class="identifier">C</span><span class="special">,&amp;,==</span> <span class="special">&gt;:</span> <span class="identifier">C</span> <span class="identifier">a</span><span class="special">,</span><span class="identifier">b</span><span class="special">,</span><span class="identifier">c</span><span class="special">;</span> <span class="identifier">a</span><span class="special">&amp;(</span><span class="identifier">b</span><span class="special">&amp;</span><span class="identifier">c</span><span class="special">)</span> <span class="special">==(</span><span class="identifier">a</span><span class="special">&amp;</span><span class="identifier">b</span><span class="special">)&amp;</span><span class="identifier">c</span>
    121. 

  121. <span class="identifier">Commutativity</span><span class="special">&lt;</span><span class="identifier">C</span><span class="special">,&amp;,==</span> <span class="special">&gt;:</span> <span class="identifier">C</span> <span class="identifier">a</span><span class="special">,</span><span class="identifier">b</span><span class="special">;</span>       <span class="identifier">a</span><span class="special">&amp;</span><span class="identifier">b</span> <span class="special">==</span> <span class="identifier">b</span><span class="special">&amp;</span><span class="identifier">a</span>
    122. 

  122. 

  123. <span class="identifier">RightNeutrality</span><span class="special">&lt;</span><span class="identifier">C</span><span class="special">,-,==</span> <span class="special">&gt;:</span> <span class="identifier">C</span> <span class="identifier">a</span><span class="special">;</span>   <span class="identifier">a</span><span class="special">-</span><span class="identifier">C</span><span class="special">()</span> <span class="special">==</span>  <span class="identifier">a</span>
    124. 

  124. <span class="identifier">Inversion</span><span class="special">&lt;</span><span class="identifier">C</span><span class="special">,-,=</span><span class="identifier">v</span><span class="special">=</span> <span class="special">&gt;</span>     <span class="special">:</span> <span class="identifier">C</span> <span class="identifier">a</span><span class="special">;</span>   <span class="identifier">a</span> <span class="special">-</span> <span class="identifier">a</span> <span class="special">=</span><span class="identifier">v</span><span class="special">=</span> <span class="identifier">C</span><span class="special">()</span>
    125. 

  125. </pre>
    126. 

  126. <p>
    127. 

  127.       </p>
    128. 

  128. <p>
    129. 

  129.         All the fundamental laws could be validated for all icl Maps in their instantiation
    130. 

  130.         as Maps of Sets or Collectors. As expected, Inversion only holds for distinct
    131. 

  131.         equality, if the map is not a <code class="computeroutput"><span class="identifier">partial_absorber</span></code>.
    132. 

  132.       </p>
    133. 

  133. <p>
    134. 

  134. </p>
    135. 

  135. <pre class="programlisting">                             <span class="special">+</span>    <span class="special">&amp;</span>    <span class="special">-</span>
    136. 

  136. <span class="identifier">Associativity</span>                <span class="special">==</span>   <span class="special">==</span>
    137. 

  137. <span class="identifier">Neutrality</span>                   <span class="special">==</span>        <span class="special">==</span>
    138. 

  138. <span class="identifier">Commutativity</span>                <span class="special">==</span>   <span class="special">==</span>
    139. 

  139. <span class="identifier">Inversion</span> <span class="identifier">partial_absorber</span>             <span class="special">==</span>
    140. 

  140.           <span class="identifier">partial_enricher</span>             <span class="special">=</span><span class="identifier">d</span><span class="special">=</span>
    141. 

  141. </pre>
    142. 

  142. <p>
    143. 

  143.       </p>
    144. 

  144. <h6>
    145. 

  145. <a name="boost_icl.semantics.collectors__maps_of_sets.h1"></a>
    146. 

  146.         <span class="phrase"><a name="boost_icl.semantics.collectors__maps_of_sets.distributivity_laws"></a></span><a class="link" href="collectors__maps_of_sets.html#boost_icl.semantics.collectors__maps_of_sets.distributivity_laws">Distributivity
    147. 

  147.         Laws</a>
    148. 

  148.       </h6>
    149. 

  149. <p>
    150. 

  150. </p>
    151. 

  151. <pre class="programlisting">     <span class="identifier">Distributivity</span><span class="special">&lt;</span><span class="identifier">C</span><span class="special">,+,&amp;,=</span><span class="identifier">v</span><span class="special">=</span> <span class="special">&gt;</span> <span class="special">:</span> <span class="identifier">C</span> <span class="identifier">a</span><span class="special">,</span><span class="identifier">b</span><span class="special">,</span><span class="identifier">c</span><span class="special">;</span> <span class="identifier">a</span> <span class="special">+</span> <span class="special">(</span><span class="identifier">b</span> <span class="special">&amp;</span> <span class="identifier">c</span><span class="special">)</span> <span class="special">=</span><span class="identifier">v</span><span class="special">=</span> <span class="special">(</span><span class="identifier">a</span> <span class="special">+</span> <span class="identifier">b</span><span class="special">)</span> <span class="special">&amp;</span> <span class="special">(</span><span class="identifier">a</span> <span class="special">+</span> <span class="identifier">c</span><span class="special">)</span>
    152. 

  152.      <span class="identifier">Distributivity</span><span class="special">&lt;</span><span class="identifier">C</span><span class="special">,&amp;,+,=</span><span class="identifier">v</span><span class="special">=</span> <span class="special">&gt;</span> <span class="special">:</span> <span class="identifier">C</span> <span class="identifier">a</span><span class="special">,</span><span class="identifier">b</span><span class="special">,</span><span class="identifier">c</span><span class="special">;</span> <span class="identifier">a</span> <span class="special">&amp;</span> <span class="special">(</span><span class="identifier">b</span> <span class="special">+</span> <span class="identifier">c</span><span class="special">)</span> <span class="special">=</span><span class="identifier">v</span><span class="special">=</span> <span class="special">(</span><span class="identifier">a</span> <span class="special">&amp;</span> <span class="identifier">b</span><span class="special">)</span> <span class="special">+</span> <span class="special">(</span><span class="identifier">a</span> <span class="special">&amp;</span> <span class="identifier">c</span><span class="special">)</span>
    153. 

  153. <span class="identifier">RightDistributivity</span><span class="special">&lt;</span><span class="identifier">C</span><span class="special">,+,-,=</span><span class="identifier">v</span><span class="special">=</span> <span class="special">&gt;</span> <span class="special">:</span> <span class="identifier">C</span> <span class="identifier">a</span><span class="special">,</span><span class="identifier">b</span><span class="special">,</span><span class="identifier">c</span><span class="special">;</span> <span class="special">(</span><span class="identifier">a</span> <span class="special">+</span> <span class="identifier">b</span><span class="special">)</span> <span class="special">-</span> <span class="identifier">c</span> <span class="special">=</span><span class="identifier">v</span><span class="special">=</span> <span class="special">(</span><span class="identifier">a</span> <span class="special">-</span> <span class="identifier">c</span><span class="special">)</span> <span class="special">+</span> <span class="special">(</span><span class="identifier">b</span> <span class="special">-</span> <span class="identifier">c</span><span class="special">)</span>
    154. 

  154. <span class="identifier">RightDistributivity</span><span class="special">&lt;</span><span class="identifier">C</span><span class="special">,&amp;,-,=</span><span class="identifier">v</span><span class="special">=</span> <span class="special">&gt;</span> <span class="special">:</span> <span class="identifier">C</span> <span class="identifier">a</span><span class="special">,</span><span class="identifier">b</span><span class="special">,</span><span class="identifier">c</span><span class="special">;</span> <span class="special">(</span><span class="identifier">a</span> <span class="special">&amp;</span> <span class="identifier">b</span><span class="special">)</span> <span class="special">-</span> <span class="identifier">c</span> <span class="special">=</span><span class="identifier">v</span><span class="special">=</span> <span class="special">(</span><span class="identifier">a</span> <span class="special">-</span> <span class="identifier">c</span><span class="special">)</span> <span class="special">&amp;</span> <span class="special">(</span><span class="identifier">b</span> <span class="special">-</span> <span class="identifier">c</span><span class="special">)</span>
    155. 

  155. </pre>
    156. 

  156. <p>
    157. 

  157.       </p>
    158. 

  158. <p>
    159. 

  159.         Results for the distributivity laws are almost identical to the validation
    160. 

  160.         of sets except that for a <code class="computeroutput"><span class="identifier">partial_enricher</span>
    161. 

  161.         <span class="identifier">map</span></code> the law <code class="computeroutput"><span class="special">(</span><span class="identifier">a</span> <span class="special">&amp;</span> <span class="identifier">b</span><span class="special">)</span> <span class="special">-</span>
    162. 

  162.         <span class="identifier">c</span> <span class="special">==</span>
    163. 

  163.         <span class="special">(</span><span class="identifier">a</span> <span class="special">-</span> <span class="identifier">c</span><span class="special">)</span>
    164. 

  164.         <span class="special">&amp;</span> <span class="special">(</span><span class="identifier">b</span> <span class="special">-</span> <span class="identifier">c</span><span class="special">)</span></code> holds for lexicographical equality.
    165. 

  165.       </p>
    166. 

  166. <p>
    167. 

  167. </p>
    168. 

  168. <pre class="programlisting">                                                   <span class="special">+,&amp;</span>    <span class="special">&amp;,+</span>
    169. 

  169.      <span class="identifier">Distributivity</span>  <span class="identifier">joining</span>                       <span class="special">==</span>     <span class="special">==</span>
    170. 

  170.                      <span class="identifier">splitting</span>   <span class="identifier">partial_absorber</span>  <span class="special">=</span><span class="identifier">e</span><span class="special">=</span>    <span class="special">=</span><span class="identifier">e</span><span class="special">=</span>
    171. 

  171.                                  <span class="identifier">partial_enricher</span>  <span class="special">=</span><span class="identifier">e</span><span class="special">=</span>    <span class="special">==</span>
    172. 

  172. 

  173.                                                    <span class="special">+,-</span>    <span class="special">&amp;,-</span>
    174. 

  174. <span class="identifier">RightDistributivity</span>  <span class="identifier">joining</span>                       <span class="special">==</span>     <span class="special">==</span>
    175. 

  175.                      <span class="identifier">splitting</span>                     <span class="special">=</span><span class="identifier">e</span><span class="special">=</span>    <span class="special">==</span>
    176. 

  176. </pre>
    177. 

  177. <p>
    178. 

  178.       </p>
    179. 

  179. <h6>
    180. 

  180. <a name="boost_icl.semantics.collectors__maps_of_sets.h2"></a>
    181. 

  181.         <span class="phrase"><a name="boost_icl.semantics.collectors__maps_of_sets.demorgan_s_law_and_symmetric_difference"></a></span><a class="link" href="collectors__maps_of_sets.html#boost_icl.semantics.collectors__maps_of_sets.demorgan_s_law_and_symmetric_difference">DeMorgan's
    182. 

  182.         Law and Symmetric Difference</a>
    183. 

  183.       </h6>
    184. 

  184. <p>
    185. 

  185. </p>
    186. 

  186. <pre class="programlisting"><span class="identifier">DeMorgan</span><span class="special">&lt;</span><span class="identifier">C</span><span class="special">,+,&amp;,=</span><span class="identifier">v</span><span class="special">=</span> <span class="special">&gt;</span> <span class="special">:</span> <span class="identifier">C</span> <span class="identifier">a</span><span class="special">,</span><span class="identifier">b</span><span class="special">,</span><span class="identifier">c</span><span class="special">;</span> <span class="identifier">a</span> <span class="special">-</span> <span class="special">(</span><span class="identifier">b</span> <span class="special">+</span> <span class="identifier">c</span><span class="special">)</span> <span class="special">=</span><span class="identifier">v</span><span class="special">=</span> <span class="special">(</span><span class="identifier">a</span> <span class="special">-</span> <span class="identifier">b</span><span class="special">)</span> <span class="special">&amp;</span> <span class="special">(</span><span class="identifier">a</span> <span class="special">-</span> <span class="identifier">c</span><span class="special">)</span>
    187. 

  187. <span class="identifier">DeMorgan</span><span class="special">&lt;</span><span class="identifier">C</span><span class="special">,&amp;,+,=</span><span class="identifier">v</span><span class="special">=</span> <span class="special">&gt;</span> <span class="special">:</span> <span class="identifier">C</span> <span class="identifier">a</span><span class="special">,</span><span class="identifier">b</span><span class="special">,</span><span class="identifier">c</span><span class="special">;</span> <span class="identifier">a</span> <span class="special">-</span> <span class="special">(</span><span class="identifier">b</span> <span class="special">&amp;</span> <span class="identifier">c</span><span class="special">)</span> <span class="special">=</span><span class="identifier">v</span><span class="special">=</span> <span class="special">(</span><span class="identifier">a</span> <span class="special">-</span> <span class="identifier">b</span><span class="special">)</span> <span class="special">+</span> <span class="special">(</span><span class="identifier">a</span> <span class="special">-</span> <span class="identifier">c</span><span class="special">)</span>
    188. 

  188. </pre>
    189. 

  189. <p>
    190. 

  190.       </p>
    191. 

  191. <p>
    192. 

  192. </p>
    193. 

  193. <pre class="programlisting">                         <span class="special">+,&amp;</span>     <span class="special">&amp;,+</span>
    194. 

  194. <span class="identifier">DeMorgan</span>  <span class="identifier">joining</span>        <span class="special">==</span>      <span class="special">==</span>
    195. 

  195.           <span class="identifier">splitting</span>      <span class="special">==</span>      <span class="special">=</span><span class="identifier">e</span><span class="special">=</span>
    196. 

  196. </pre>
    197. 

  197. <p>
    198. 

  198.       </p>
    199. 

  199. <p>
    200. 

  200. </p>
    201. 

  201. <pre class="programlisting"><span class="identifier">SymmetricDifference</span><span class="special">&lt;</span><span class="identifier">C</span><span class="special">,==</span> <span class="special">&gt;</span> <span class="special">:</span> <span class="identifier">C</span> <span class="identifier">a</span><span class="special">,</span><span class="identifier">b</span><span class="special">,</span><span class="identifier">c</span><span class="special">;</span> <span class="special">(</span><span class="identifier">a</span> <span class="special">+</span> <span class="identifier">b</span><span class="special">)</span> <span class="special">-</span> <span class="special">(</span><span class="identifier">a</span> <span class="special">*</span> <span class="identifier">b</span><span class="special">)</span> <span class="special">==</span> <span class="special">(</span><span class="identifier">a</span> <span class="special">-</span> <span class="identifier">b</span><span class="special">)</span> <span class="special">+</span> <span class="special">(</span><span class="identifier">b</span> <span class="special">-</span> <span class="identifier">a</span><span class="special">)</span>
    202. 

  202. </pre>
    203. 

  203. <p>
    204. 

  204.       </p>
    205. 

  205. <p>
    206. 

  206.         Reviewing the validity tables above shows, that the sets of valid laws for
    207. 

  207.         <code class="computeroutput"><span class="identifier">icl</span> <span class="identifier">Sets</span></code>
    208. 

  208.         and <code class="computeroutput"><span class="identifier">icl</span> <span class="identifier">Maps</span>
    209. 

  209.         <span class="identifier">of</span> <span class="identifier">Sets</span></code>
    210. 

  210.         that are <span class="emphasis"><em>identity absorbing</em></span> are exactly the same. As
    211. 

  211.         expected, only for Maps of Sets that represent empty sets as associated values,
    212. 

  212.         called <span class="emphasis"><em>identity enrichers</em></span>, there are marginal semantic
    213. 

  213.         differences.
    214. 

  214.       </p>
    215. 

  215. </div>
    216. 

  216. <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
    217. 

  217. <td align="left"></td>
    218. 

  218. <td align="right"><div class="copyright-footer">Copyright &#169; 2007-2010 Joachim
    219. 

  219.       Faulhaber<br>Copyright &#169; 1999-2006 Cortex Software
    220. 

  220.       GmbH<p>
    221. 

  221.         Distributed under the Boost Software License, Version 1.0. (See accompanying
    222. 

  222.         file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
    223. 

  223.       </p>
    224. 

  224. </div></td>
    225. 

  225. </tr></table>
    226. 

  226. <hr>
    227. 

  227. <div class="spirit-nav">
    228. 

  228. <a accesskey="p" href="maps.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../semantics.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="quantifiers__maps_of_numbers.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
    229. 

  229. </div>
    230. 

  230. </body>
    231. 

  231. </html>
    232.