ceph/src/boost/libs/icl/doc/html/boost_icl/semantics/maps.html

   1 <html>
   2 <head>
   3 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
   4 <title>Maps</title>
   5 <link rel="stylesheet" href="../../../../../../doc/src/boostbook.css" type="text/css">
   6 <meta name="generator" content="DocBook XSL Stylesheets V1.74.0">
   7 <link rel="home" href="../../index.html" title="Chapter&#160;1.&#160;Boost.Icl">
   8 <link rel="up" href="../semantics.html" title="Semantics">
   9 <link rel="prev" href="sets.html" title="Sets">
  10 <link rel="next" href="collectors__maps_of_sets.html" title="Collectors: Maps of Sets">
  11 </head>
  12 <body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
  13 <table cellpadding="2" width="100%"><tr>
  14 <td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td>
  15 <td align="center"><a href="../../../../../../index.html">Home</a></td>
  16 <td align="center"><a href="../../../../../libraries.htm">Libraries</a></td>
  17 <td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
  18 <td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
  19 <td align="center"><a href="../../../../../../more/index.htm">More</a></td>
  20 </tr></table>
  21 <hr>
  22 <div class="spirit-nav">
  23 <a accesskey="p" href="sets.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="collectors__maps_of_sets.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
  24 </div>
  25 <div class="section boost_icl_semantics_maps" lang="en">
  26 <div class="titlepage"><div><div><h3 class="title">
  27 <a name="boost_icl.semantics.maps"></a><a class="link" href="maps.html" title="Maps">Maps</a>
  28 </h3></div></div></div>
  29 <p>
  30         By definition a map is set of pairs. So we would expect maps to obey the
  31         same laws that are valid for sets. Yet the semantics of the <span class="bold"><strong>icl's</strong></span>
  32         maps may be a different one, because of it's aggregating facilities, where
  33         the aggregating combiner operations are passed to combine the map's associated
  34         values. It turns out, that the aggregation on overlap principle induces semantic
  35         properties to icl maps in such a way, that the set of equations that are
  36         valid will depend on the semantics of the type <code class="computeroutput"><span class="identifier">CodomainT</span></code>
  37         of the map's associated values.
  38       </p>
  39 <p>
  40         This is less magical as it might seem at first glance. If, for instance,
  41         we instantiate an <code class="computeroutput"><a class="link" href="../../boost/icl/interval_map.html" title="Class template interval_map">interval_map</a></code>
  42         to collect and concatenate <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">strings</span></code>
  43         associated to intervals,
  44       </p>
  45 <p>
  46
  47 </p>
  48 <pre class="programlisting"><span class="identifier">interval_map</span><span class="special">&lt;</span><span class="keyword">int</span><span class="special">,</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">&gt;</span> <span class="identifier">cat_map</span><span class="special">;</span>
  49 <span class="identifier">cat_map</span> <span class="special">+=</span> <span class="identifier">make_pair</span><span class="special">(</span><span class="identifier">interval</span><span class="special">&lt;</span><span class="keyword">int</span><span class="special">&gt;::</span><span class="identifier">rightopen</span><span class="special">(</span><span class="number">1</span><span class="special">,</span><span class="number">5</span><span class="special">),</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">(</span><span class="string">"Hello"</span><span class="special">));</span>
  50 <span class="identifier">cat_map</span> <span class="special">+=</span> <span class="identifier">make_pair</span><span class="special">(</span><span class="identifier">interval</span><span class="special">&lt;</span><span class="keyword">int</span><span class="special">&gt;::</span><span class="identifier">rightopen</span><span class="special">(</span><span class="number">3</span><span class="special">,</span><span class="number">7</span><span class="special">),</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">(</span><span class="string">" World"</span><span class="special">));</span>
  51 <span class="identifier">cout</span> <span class="special">&lt;&lt;</span> <span class="string">"cat_map: "</span> <span class="special">&lt;&lt;</span> <span class="identifier">cat_map</span> <span class="special">&lt;&lt;</span> <span class="identifier">endl</span><span class="special">;</span>
  52 </pre>
  53 <p>
  54       </p>
  55 <p>
  56         we won't be able to apply <code class="computeroutput"><span class="keyword">operator</span>
  57         <span class="special">-=</span></code>
  58 </p>
  59 <pre class="programlisting"><span class="comment">// This will not compile because string::operator -= is missing.
  60 </span><span class="identifier">cat_map</span> <span class="special">-=</span> <span class="identifier">make_pair</span><span class="special">(</span><span class="identifier">interval</span><span class="special">&lt;</span><span class="keyword">int</span><span class="special">&gt;::</span><span class="identifier">rightopen</span><span class="special">(</span><span class="number">3</span><span class="special">,</span><span class="number">7</span><span class="special">),</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">(</span><span class="string">" World"</span><span class="special">));</span>
  61 </pre>
  62 <p>
  63         because, as std::sting does not implement <code class="computeroutput"><span class="special">-=</span></code>
  64         itself, this won't compile. So all <span class="bold"><strong>laws</strong></span>,
  65         that rely on <code class="computeroutput"><span class="keyword">operator</span> <span class="special">-=</span></code>
  66         or <code class="computeroutput"><span class="special">-</span></code> not only will not be valid
  67         they can not even be stated. This reduces the set of laws that can be valid
  68         for a richer <code class="computeroutput"><span class="identifier">CodomainT</span></code> type
  69         to a smaller set of laws and thus to a less restricted semantics.
  70       </p>
  71 <p>
  72         Currently we have investigated and validated two major instantiations of
  73         icl::Maps,
  74       </p>
  75 <div class="itemizedlist"><ul type="disc">
  76 <li>
  77 <span class="emphasis"><em><span class="bold"><strong>Maps of Sets</strong></span></em></span> that
  78           will be called <span class="emphasis"><em><span class="bold"><strong>Collectors</strong></span></em></span>
  79           and
  80         </li>
  81 <li>
  82 <span class="emphasis"><em><span class="bold"><strong>Maps of Numbers</strong></span></em></span> which
  83           will be called <span class="emphasis"><em><span class="bold"><strong>Quantifiers</strong></span></em></span>
  84 </li>
  85 </ul></div>
  86 <p>
  87         both of which seem to have many interesting use cases for practical applications.
  88         The semantics associated with the term <span class="emphasis"><em>Numbers</em></span> is a
  89         <a href="http://en.wikipedia.org/wiki/Monoid" target="_top">commutative monoid</a>
  90         for unsigned numbers and a <a href="http://en.wikipedia.org/wiki/Abelian_group" target="_top">commutative
  91         or abelian group</a> for signed numbers. From a practical point of view
  92         we can think of numbers as counting or quantifying the key values of the
  93         map.
  94       </p>
  95 <p>
  96         Icl <span class="emphasis"><em><span class="bold"><strong>Maps of Sets</strong></span></em></span> or
  97         <span class="emphasis"><em><span class="bold"><strong>Collectors</strong></span></em></span> are models
  98         of concept <code class="computeroutput"><span class="identifier">Set</span></code>. This implies
  99         that all laws that have been stated as a semantics for <code class="computeroutput"><span class="identifier">icl</span><span class="special">::</span><span class="identifier">Sets</span></code>
 100         in the previous chapter also hold for <code class="computeroutput"><span class="identifier">Maps</span>
 101         <span class="identifier">of</span> <span class="identifier">Sets</span></code>.
 102         Icl <span class="emphasis"><em><span class="bold"><strong>Maps of Numbers</strong></span></em></span>
 103         or <span class="emphasis"><em><span class="bold"><strong>Quantifiers</strong></span></em></span> on the
 104         contrary are not models of concept <code class="computeroutput"><span class="identifier">Set</span></code>.
 105         But there is a substantial intersection of laws that apply both for <code class="computeroutput"><span class="identifier">Collectors</span></code> and <code class="computeroutput"><span class="identifier">Quantifiers</span></code>.
 106       </p>
 107 <div class="informaltable"><table class="table">
 108 <colgroup>
 109 <col>
 110 <col>
 111 <col>
 112 </colgroup>
 113 <thead><tr>
 114 <th>
 115               <p>
 116                 Kind of Map
 117               </p>
 118               </th>
 119 <th>
 120               <p>
 121                 Alias
 122               </p>
 123               </th>
 124 <th>
 125               <p>
 126                 Behavior
 127               </p>
 128               </th>
 129 </tr></thead>
 130 <tbody>
 131 <tr>
 132 <td>
 133               <p>
 134                 Maps of Sets
 135               </p>
 136               </td>
 137 <td>
 138               <p>
 139                 Collector
 140               </p>
 141               </td>
 142 <td>
 143               <p>
 144                 Collects items <span class="bold"><strong>for</strong></span> key values
 145               </p>
 146               </td>
 147 </tr>
 148 <tr>
 149 <td>
 150               <p>
 151                 Maps of Numbers
 152               </p>
 153               </td>
 154 <td>
 155               <p>
 156                 Quantifier
 157               </p>
 158               </td>
 159 <td>
 160               <p>
 161                 Counts or quantifies <span class="bold"><strong>the</strong></span> key values
 162               </p>
 163               </td>
 164 </tr>
 165 </tbody>
 166 </table></div>
 167 <p>
 168         In the next two sections the law based semantics of <span class="emphasis"><em><span class="bold"><strong>Collectors</strong></span></em></span>
 169         and <span class="emphasis"><em><span class="bold"><strong>Quantifiers</strong></span></em></span> will
 170         be described in more detail.
 171       </p>
 172 </div>
 173 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
 174 <td align="left"></td>
 175 <td align="right"><div class="copyright-footer">Copyright &#169; 2007 -2010 Joachim Faulhaber<br>Copyright &#169; 1999 -2006 Cortex Software GmbH<p>
 176         Distributed under the Boost Software License, Version 1.0. (See accompanying
 177         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>)
 178       </p>
 179 </div></td>
 180 </tr></table>
 181 <hr>
 182 <div class="spirit-nav">
 183 <a accesskey="p" href="sets.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="collectors__maps_of_sets.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
 184 </div>
 185 </body>
 186 </html>