1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 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.79.1"> 7<link rel="home" href="../../index.html" title="Chapter 1. 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"> 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</p> 47<pre class="programlisting"><span class="identifier">interval_map</span><span class="special"><</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">></span> <span class="identifier">cat_map</span><span class="special">;</span> 48<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"><</span><span class="keyword">int</span><span class="special">>::</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> 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"><</span><span class="keyword">int</span><span class="special">>::</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> 50<span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"cat_map: "</span> <span class="special"><<</span> <span class="identifier">cat_map</span> <span class="special"><<</span> <span class="identifier">endl</span><span class="special">;</span> 51</pre> 52<p> 53 </p> 54<p> 55 we won't be able to apply <code class="computeroutput"><span class="keyword">operator</span> 56 <span class="special">-=</span></code> 57</p> 58<pre class="programlisting"><span class="comment">// This will not compile because string::operator -= is missing.</span> 59<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"><</span><span class="keyword">int</span><span class="special">>::</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> 60</pre> 61<p> 62 because, as std::sting does not implement <code class="computeroutput"><span class="special">-=</span></code> 63 itself, this won't compile. So all <span class="bold"><strong>laws</strong></span>, 64 that rely on <code class="computeroutput"><span class="keyword">operator</span> <span class="special">-=</span></code> 65 or <code class="computeroutput"><span class="special">-</span></code> not only will not be valid 66 they can not even be stated. This reduces the set of laws that can be valid 67 for a richer <code class="computeroutput"><span class="identifier">CodomainT</span></code> type 68 to a smaller set of laws and thus to a less restricted semantics. 69 </p> 70<p> 71 Currently we have investigated and validated two major instantiations of 72 icl::Maps, 73 </p> 74<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 75<li class="listitem"> 76 <span class="emphasis"><em><span class="bold"><strong>Maps of Sets</strong></span></em></span> that 77 will be called <span class="emphasis"><em><span class="bold"><strong>Collectors</strong></span></em></span> 78 and 79 </li> 80<li class="listitem"> 81 <span class="emphasis"><em><span class="bold"><strong>Maps of Numbers</strong></span></em></span> 82 which will be called <span class="emphasis"><em><span class="bold"><strong>Quantifiers</strong></span></em></span> 83 </li> 84</ul></div> 85<p> 86 both of which seem to have many interesting use cases for practical applications. 87 The semantics associated with the term <span class="emphasis"><em>Numbers</em></span> is a 88 <a href="http://en.wikipedia.org/wiki/Monoid" target="_top">commutative monoid</a> 89 for unsigned numbers and a <a href="http://en.wikipedia.org/wiki/Abelian_group" target="_top">commutative 90 or abelian group</a> for signed numbers. From a practical point of view 91 we can think of numbers as counting or quantifying the key values of the 92 map. 93 </p> 94<p> 95 Icl <span class="emphasis"><em><span class="bold"><strong>Maps of Sets</strong></span></em></span> or 96 <span class="emphasis"><em><span class="bold"><strong>Collectors</strong></span></em></span> are models 97 of concept <code class="computeroutput"><span class="identifier">Set</span></code>. This implies 98 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> 99 in the previous chapter also hold for <code class="computeroutput"><span class="identifier">Maps</span> 100 <span class="identifier">of</span> <span class="identifier">Sets</span></code>. 101 Icl <span class="emphasis"><em><span class="bold"><strong>Maps of Numbers</strong></span></em></span> 102 or <span class="emphasis"><em><span class="bold"><strong>Quantifiers</strong></span></em></span> on the 103 contrary are not models of concept <code class="computeroutput"><span class="identifier">Set</span></code>. 104 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>. 105 </p> 106<div class="informaltable"><table class="table"> 107<colgroup> 108<col> 109<col> 110<col> 111</colgroup> 112<thead><tr> 113<th> 114 <p> 115 Kind of Map 116 </p> 117 </th> 118<th> 119 <p> 120 Alias 121 </p> 122 </th> 123<th> 124 <p> 125 Behavior 126 </p> 127 </th> 128</tr></thead> 129<tbody> 130<tr> 131<td> 132 <p> 133 Maps of Sets 134 </p> 135 </td> 136<td> 137 <p> 138 Collector 139 </p> 140 </td> 141<td> 142 <p> 143 Collects items <span class="bold"><strong>for</strong></span> key values 144 </p> 145 </td> 146</tr> 147<tr> 148<td> 149 <p> 150 Maps of Numbers 151 </p> 152 </td> 153<td> 154 <p> 155 Quantifier 156 </p> 157 </td> 158<td> 159 <p> 160 Counts or quantifies <span class="bold"><strong>the</strong></span> key values 161 </p> 162 </td> 163</tr> 164</tbody> 165</table></div> 166<p> 167 In the next two sections the law based semantics of <span class="emphasis"><em><span class="bold"><strong>Collectors</strong></span></em></span> 168 and <span class="emphasis"><em><span class="bold"><strong>Quantifiers</strong></span></em></span> will 169 be described in more detail. 170 </p> 171</div> 172<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 173<td align="left"></td> 174<td align="right"><div class="copyright-footer">Copyright © 2007-2010 Joachim 175 Faulhaber<br>Copyright © 1999-2006 Cortex Software 176 GmbH<p> 177 Distributed under the Boost Software License, Version 1.0. (See accompanying 178 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>) 179 </p> 180</div></td> 181</tr></table> 182<hr> 183<div class="spirit-nav"> 184<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> 185</div> 186</body> 187</html> 188
