1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 4<title>Map Traits</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="../concepts.html" title="Concepts"> 9<link rel="prev" href="aggrovering.html" title="Addability, Subtractability and Aggregate on Overlap"> 10<link rel="next" href="../semantics.html" title="Semantics"> 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="aggrovering.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../concepts.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="../semantics.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.concepts.map_traits"></a><a class="link" href="map_traits.html" title="Map Traits">Map Traits</a> 28</h3></div></div></div> 29<p> 30 Icl maps differ in their behavior dependent on how they handle <a href="http://en.wikipedia.org/wiki/Identity_element" target="_top"><span class="emphasis"><em><span class="bold"><strong>identity elements</strong></span></em></span></a> of the associated 31 type <code class="computeroutput"><span class="identifier">CodomainT</span></code>. 32 </p> 33<h5> 34<a name="boost_icl.concepts.map_traits.h0"></a> 35 <span class="phrase"><a name="boost_icl.concepts.map_traits.remarks_on_identity_elements"></a></span><a class="link" href="map_traits.html#boost_icl.concepts.map_traits.remarks_on_identity_elements">Remarks 36 on Identity Elements</a> 37 </h5> 38<p> 39 In the pseudo code snippets below <code class="computeroutput"><span class="number">0</span></code> 40 will be used to denote <a href="http://en.wikipedia.org/wiki/Identity_element" target="_top"><code class="computeroutput"><span class="identifier">identity</span> <span class="identifier">elements</span></code></a>, 41 which can be different objects like <code class="computeroutput"><span class="keyword">const</span> 42 <span class="keyword">double</span> <span class="number">0.0</span></code>, 43 empty sets, empty strings, null-vectors etc. dependent of the instance type 44 for parameter <code class="computeroutput"><span class="identifier">CodomainT</span></code>. 45 The existence of an <span class="emphasis"><em><span class="bold"><strong>identity element</strong></span></em></span> 46 wrt. an <code class="computeroutput"><span class="keyword">operator</span><span class="special">+=</span></code> 47 is a requirement for template type <code class="computeroutput"><span class="identifier">CodomainT</span></code>. 48 </p> 49<div class="informaltable"><table class="table"> 50<colgroup> 51<col> 52<col> 53<col> 54</colgroup> 55<thead><tr> 56<th> 57 <p> 58 type 59 </p> 60 </th> 61<th> 62 <p> 63 operation 64 </p> 65 </th> 66<th> 67 <p> 68 identity element 69 </p> 70 </th> 71</tr></thead> 72<tbody> 73<tr> 74<td> 75 <p> 76 <code class="computeroutput"><span class="keyword">int</span></code> 77 </p> 78 </td> 79<td> 80 <p> 81 addition 82 </p> 83 </td> 84<td> 85 <p> 86 <code class="computeroutput"><span class="number">0</span></code> 87 </p> 88 </td> 89</tr> 90<tr> 91<td> 92 <p> 93 <code class="computeroutput"><span class="identifier">string</span></code> 94 </p> 95 </td> 96<td> 97 <p> 98 concatenation 99 </p> 100 </td> 101<td> 102 <p> 103 <code class="computeroutput"><span class="string">""</span></code> 104 </p> 105 </td> 106</tr> 107<tr> 108<td> 109 <p> 110 <code class="computeroutput"><span class="identifier">set</span><span class="special"><</span><span class="identifier">T</span><span class="special">></span></code> 111 </p> 112 </td> 113<td> 114 <p> 115 union 116 </p> 117 </td> 118<td> 119 <p> 120 <code class="computeroutput"><span class="special">{}</span></code> 121 </p> 122 </td> 123</tr> 124</tbody> 125</table></div> 126<p> 127 In these cases the <code class="computeroutput"><span class="identifier">identity</span> <span class="identifier">element</span></code> value is delivered by the default 128 constructor of the maps <code class="computeroutput"><span class="identifier">CodomainT</span></code> 129 type. But there are well known exceptions like e.g. numeric multiplication: 130 </p> 131<div class="informaltable"><table class="table"> 132<colgroup> 133<col> 134<col> 135<col> 136</colgroup> 137<thead><tr> 138<th> 139 <p> 140 type 141 </p> 142 </th> 143<th> 144 <p> 145 operation 146 </p> 147 </th> 148<th> 149 <p> 150 identity element 151 </p> 152 </th> 153</tr></thead> 154<tbody><tr> 155<td> 156 <p> 157 <code class="computeroutput"><span class="keyword">int</span></code> 158 </p> 159 </td> 160<td> 161 <p> 162 multiplication 163 </p> 164 </td> 165<td> 166 <p> 167 <code class="computeroutput"><span class="number">1</span></code> 168 </p> 169 </td> 170</tr></tbody> 171</table></div> 172<p> 173 Therefore icl functors, that serve as <code class="computeroutput"><span class="identifier">Combiner</span></code> 174 parameters of icl Maps implement a static function <code class="computeroutput"><span class="identifier">identity_element</span><span class="special">()</span></code> to make sure that the correct <code class="computeroutput"><span class="identifier">identity_element</span><span class="special">()</span></code> 175 is used in the implementation of <span class="emphasis"><em>aggregate on overlap</em></span>. 176</p> 177<pre class="programlisting"><span class="identifier">inplace_times</span><span class="special"><</span><span class="keyword">int</span><span class="special">>::</span><span class="identifier">identity_element</span><span class="special">()</span> <span class="special">==</span> <span class="number">1</span> 178<span class="comment">// or more general</span> 179<span class="identifier">inplace_times</span><span class="special"><</span><span class="identifier">T</span><span class="special">>::</span><span class="identifier">identity_element</span><span class="special">()</span> <span class="special">==</span> <span class="identifier">unit_element</span><span class="special"><</span><span class="identifier">T</span><span class="special">>::</span><span class="identifier">value</span><span class="special">()</span> 180</pre> 181<p> 182 </p> 183<h5> 184<a name="boost_icl.concepts.map_traits.h1"></a> 185 <span class="phrase"><a name="boost_icl.concepts.map_traits.definedness_and_storage_of_identity_elements"></a></span><a class="link" href="map_traits.html#boost_icl.concepts.map_traits.definedness_and_storage_of_identity_elements">Definedness 186 and Storage of Identity Elements</a> 187 </h5> 188<p> 189 There are two <span class="emphasis"><em>properties</em></span> or <span class="emphasis"><em>traits</em></span> 190 of icl maps that can be chosen by a template parameter <code class="computeroutput"><span class="identifier">Traits</span></code>. 191 The <span class="emphasis"><em><span class="bold"><strong>first trait</strong></span></em></span> relates 192 to the <span class="emphasis"><em><span class="bold"><strong>definedness</strong></span></em></span> 193 of the map. Icl maps can be <span class="bold"><strong>partial</strong></span> or 194 <span class="bold"><strong>total</strong></span> on the set of values given by domain 195 type <code class="computeroutput"><span class="identifier">DomainT</span></code>. 196 </p> 197<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 198<li class="listitem"> 199 A <span class="emphasis"><em><span class="bold"><strong>partial</strong></span></em></span> map is 200 only defined on those key elements that have been inserted into the Map. 201 This is usually expected and so <span class="emphasis"><em><span class="bold"><strong>partial 202 definedness</strong></span></em></span> is the default. 203 </li> 204<li class="listitem"> 205 Alternatively an icl Map can be <span class="emphasis"><em><span class="bold"><strong>total</strong></span></em></span>. 206 It is then considered to contain a <span class="emphasis"><em><span class="bold"><strong>neutral 207 value</strong></span></em></span> for all key values that are not stored in 208 the map. 209 </li> 210</ul></div> 211<p> 212 The <span class="emphasis"><em><span class="bold"><strong>second trait</strong></span></em></span> is 213 related to the representation of <code class="computeroutput"><span class="identifier">identity</span> 214 <span class="identifier">elements</span></code> in the map. An icl map 215 can be a <span class="emphasis"><em><span class="bold"><strong>identity absorber</strong></span></em></span> 216 or a <span class="emphasis"><em><span class="bold"><strong>identity enricher</strong></span></em></span>. 217 </p> 218<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 219<li class="listitem"> 220 A <span class="emphasis"><em><span class="bold"><strong>identity absorber</strong></span></em></span> 221 never stores value pairs <code class="computeroutput"><span class="special">(</span><span class="identifier">k</span><span class="special">,</span><span class="number">0</span><span class="special">)</span></code> that 222 carry identity elements. 223 </li> 224<li class="listitem"> 225 A <span class="emphasis"><em><span class="bold"><strong>identity enricher</strong></span></em></span> 226 stores value pairs <code class="computeroutput"><span class="special">(</span><span class="identifier">k</span><span class="special">,</span><span class="number">0</span><span class="special">)</span></code>. 227 </li> 228</ul></div> 229<p> 230 For the template parameter <code class="computeroutput"><span class="identifier">Traits</span></code> 231 of icl Maps we have the following four values. 232 </p> 233<div class="informaltable"><table class="table"> 234<colgroup> 235<col> 236<col> 237<col> 238</colgroup> 239<thead><tr> 240<th> 241 </th> 242<th> 243 <p> 244 identity absorber 245 </p> 246 </th> 247<th> 248 <p> 249 identity enricher 250 </p> 251 </th> 252</tr></thead> 253<tbody> 254<tr> 255<td> 256 <p> 257 partial 258 </p> 259 </td> 260<td> 261 <p> 262 partial_absorber <span class="emphasis"><em>(default)</em></span> 263 </p> 264 </td> 265<td> 266 <p> 267 partial_enricher 268 </p> 269 </td> 270</tr> 271<tr> 272<td> 273 <p> 274 total 275 </p> 276 </td> 277<td> 278 <p> 279 total_absorber 280 </p> 281 </td> 282<td> 283 <p> 284 total_enricher 285 </p> 286 </td> 287</tr> 288</tbody> 289</table></div> 290<h5> 291<a name="boost_icl.concepts.map_traits.h2"></a> 292 <span class="phrase"><a name="boost_icl.concepts.map_traits.map_traits_motivated"></a></span><a class="link" href="map_traits.html#boost_icl.concepts.map_traits.map_traits_motivated">Map 293 Traits motivated</a> 294 </h5> 295<p> 296 Map traits are a late extension to the <span class="bold"><strong>icl</strong></span>. 297 Interval maps have been used for a couple of years in a variety of applications 298 at Cortex Software GmbH with an implementation that resembled the default 299 trait. Only the deeper analysis of the icl's <span class="emphasis"><em><span class="bold"><strong>aggregating 300 Map's concept</strong></span></em></span> in the course of preparation of the library 301 for boost led to the introduction of map Traits. 302 </p> 303<h6> 304<a name="boost_icl.concepts.map_traits.h3"></a> 305 <span class="phrase"><a name="boost_icl.concepts.map_traits.add_subtract_antinomy_in_aggregating_maps"></a></span><a class="link" href="map_traits.html#boost_icl.concepts.map_traits.add_subtract_antinomy_in_aggregating_maps">Add-Subtract 306 Antinomy in Aggregating Maps</a> 307 </h6> 308<p> 309 Constitutional for the absorber/enricher propery is a little antinomy. 310 </p> 311<p> 312 We can insert value pairs to the map by <span class="emphasis"><em><span class="bold"><strong>adding</strong></span></em></span> 313 them to the map via operations <code class="computeroutput"><span class="identifier">add</span><span class="special">,</span> <span class="special">+=</span></code> or <code class="computeroutput"><span class="special">+</span></code>: 314</p> 315<pre class="programlisting"><span class="special">{}</span> <span class="special">+</span> <span class="special">{(</span><span class="identifier">k</span><span class="special">,</span><span class="number">1</span><span class="special">)}</span> <span class="special">==</span> <span class="special">{(</span><span class="identifier">k</span><span class="special">,</span><span class="number">1</span><span class="special">)}</span> <span class="comment">// addition</span></pre> 316<p> 317 </p> 318<p> 319 Further addition on common keys triggers aggregation: 320</p> 321<pre class="programlisting"><span class="special">{(</span><span class="identifier">k</span><span class="special">,</span><span class="number">1</span><span class="special">)}</span> <span class="special">+</span> <span class="special">{(</span><span class="identifier">k</span><span class="special">,</span><span class="number">1</span><span class="special">)}</span> <span class="special">==</span> <span class="special">{(</span><span class="identifier">k</span><span class="special">,</span><span class="number">2</span><span class="special">)}</span> <span class="comment">// aggregation for common key k</span></pre> 322<p> 323 </p> 324<p> 325 A subtraction of existing pairs 326</p> 327<pre class="programlisting"><span class="special">{(</span><span class="identifier">k</span><span class="special">,</span><span class="number">2</span><span class="special">)}</span> <span class="special">-</span> <span class="special">{(</span><span class="identifier">k</span><span class="special">,</span><span class="number">2</span><span class="special">)}</span> <span class="special">==</span> <span class="special">{(</span><span class="identifier">k</span><span class="special">,</span><span class="number">0</span><span class="special">)}</span> <span class="comment">// aggregation for common key k</span></pre> 328<p> 329 yields value pairs that are associated with 0-values or <code class="computeroutput"><span class="identifier">identity</span> 330 <span class="identifier">elements</span></code>. 331 </p> 332<p> 333 So once a value pair is created for a key <code class="computeroutput"><span class="identifier">k</span></code> 334 it can not be removed from the map via subtraction (<code class="computeroutput"><span class="identifier">subtract</span><span class="special">,</span> <span class="special">-=</span></code> or <code class="computeroutput"><span class="special">-</span></code>). 335 </p> 336<p> 337 The very basic fact on sets, that we can remove what we have previously added 338</p> 339<pre class="programlisting"><span class="identifier">x</span> <span class="special">-</span> <span class="identifier">x</span> <span class="special">=</span> <span class="special">{}</span></pre> 340<p> 341 does not apply. 342 </p> 343<p> 344 This is the motivation for the <span class="emphasis"><em><span class="bold"><strong>identity absorber</strong></span></em></span> 345 Trait. A identity absorber map handles value pairs that carry identity elements 346 as <span class="emphasis"><em><span class="bold"><strong>non-existent</strong></span></em></span>, which 347 saves the law: 348</p> 349<pre class="programlisting"><span class="identifier">x</span> <span class="special">-</span> <span class="identifier">x</span> <span class="special">=</span> <span class="special">{}</span></pre> 350<p> 351 </p> 352<p> 353 Yet this introduces a new problem: With such a <span class="emphasis"><em>identity absorber</em></span> 354 we are <span class="emphasis"><em>by definition</em></span> unable to store a value <code class="computeroutput"><span class="special">(</span><span class="identifier">k</span><span class="special">,</span><span class="number">0</span><span class="special">)</span></code> in the map. 355 This may be unfavorable because it is not inline with the behavior of stl::maps 356 and this is not necessarily expected by clients of the library. 357 </p> 358<p> 359 The solution to the problem is the introduction of the identity enricher 360 Trait, so the user can choose a map variant according to her needs. 361 </p> 362<h6> 363<a name="boost_icl.concepts.map_traits.h4"></a> 364 <span class="phrase"><a name="boost_icl.concepts.map_traits.partial_and_total_maps"></a></span><a class="link" href="map_traits.html#boost_icl.concepts.map_traits.partial_and_total_maps">Partial and 365 Total Maps</a> 366 </h6> 367<p> 368 The idea of a identity absorbing map is, that an <span class="emphasis"><em><span class="bold"><strong>associated 369 identity element</strong></span></em></span> value of a pair <code class="computeroutput"><span class="special">(</span><span class="identifier">k</span><span class="special">,</span><span class="number">0</span><span class="special">)</span></code> <span class="emphasis"><em><span class="bold"><strong>codes non-existence</strong></span></em></span> 370 for it's key <code class="computeroutput"><span class="identifier">k</span></code>. So the pair 371 <code class="computeroutput"><span class="special">(</span><span class="identifier">k</span><span class="special">,</span><span class="number">0</span><span class="special">)</span></code> 372 immediately tunnels from a map where it may emerge into the realm of non 373 existence. 374</p> 375<pre class="programlisting"><span class="special">{(</span><span class="identifier">k</span><span class="special">,</span><span class="number">0</span><span class="special">)}</span> <span class="special">==</span> <span class="special">{}</span></pre> 376<p> 377 </p> 378<p> 379 If identity elements do not code <span class="emphasis"><em><span class="bold"><strong>non-existence</strong></span></em></span> 380 but <span class="emphasis"><em><span class="bold"><strong>existence with null quantification</strong></span></em></span>, 381 we can also think of a map that has an associated identity element <span class="emphasis"><em><span class="bold"><strong>for every</strong></span></em></span> key <code class="computeroutput"><span class="identifier">k</span></code> 382 that has no associated value different from 0. So in contrast to modelling 383 <span class="bold"><strong>all</strong></span> neutral value pairs <code class="computeroutput"><span class="special">(</span><span class="identifier">k</span><span class="special">,</span><span class="number">0</span><span class="special">)</span></code> as being <span class="emphasis"><em><span class="bold"><strong>non-existent</strong></span></em></span> 384 we can model <span class="bold"><strong>all</strong></span> neutral value pairs <code class="computeroutput"><span class="special">(</span><span class="identifier">k</span><span class="special">,</span><span class="number">0</span><span class="special">)</span></code> as being 385 <span class="emphasis"><em><span class="bold"><strong>implicitly existent</strong></span></em></span>. 386 </p> 387<p> 388 A map that is modelled in this way, is one large vector with a value <code class="computeroutput"><span class="identifier">v</span></code> for every key <code class="computeroutput"><span class="identifier">k</span></code> 389 of it's domain type <code class="computeroutput"><span class="identifier">DomainT</span></code>. 390 But only non-identity values are actually stored. This is the motivation 391 for the definedness-Trait on <code class="computeroutput"><span class="identifier">icl</span> 392 <span class="identifier">Maps</span></code>. 393 </p> 394<p> 395 A <span class="emphasis"><em><span class="bold"><strong>partial</strong></span></em></span> map models 396 the intuitive view that only value pairs are existent, that are stored in 397 the map. A <span class="emphasis"><em><span class="bold"><strong>total</strong></span></em></span> map 398 exploits the possibility that all value pairs that are not stored can be 399 considered as being existent and <span class="emphasis"><em><span class="bold"><strong>quantified</strong></span></em></span> 400 with the identity element. 401 </p> 402<h5> 403<a name="boost_icl.concepts.map_traits.h5"></a> 404 <span class="phrase"><a name="boost_icl.concepts.map_traits.pragmatical_aspects_of_map_traits"></a></span><a class="link" href="map_traits.html#boost_icl.concepts.map_traits.pragmatical_aspects_of_map_traits">Pragmatical 405 Aspects of Map Traits</a> 406 </h5> 407<p> 408 From a pragmatic perspective value pairs that carry <code class="computeroutput"><span class="identifier">identity</span> 409 <span class="identifier">elements</span></code> as mapped values can often 410 be ignored. If we count, for instance, the number of overlaps of inserted 411 intervals in an <code class="computeroutput"><a class="link" href="../../boost/icl/interval_map.html" title="Class template interval_map">interval_map</a></code> 412 (see example <a class="link" href="../examples/overlap_counter.html" title="Overlap counter">overlap counter</a>), 413 most of the time, we are not interested in whether an overlap has been counted 414 <code class="computeroutput"><span class="number">0</span></code> times or has not been counted 415 at all. A identity enricher map is only needed, if we want to distinct between 416 non-existence and 0-quantification. 417 </p> 418<p> 419 The following distinction can <span class="bold"><strong>not</strong></span> be made 420 for a <code class="computeroutput"><a class="link" href="../../boost/icl/partial_absorber.html" title="Struct partial_absorber">partial_absorber</a></code> 421 map but it can be made for an <code class="computeroutput"><a class="link" href="../../boost/icl/partial_enricher.html" title="Struct partial_enricher">partial_enricher</a></code> 422 map: 423 </p> 424<pre class="programlisting">(k,v) does not exist in the map: Pair (k,v) has NOT been dealt with 425(k,0) key k carries 0 : Pair (k,v) has been dealt with resulting in v=0 426</pre> 427<p> 428 Sometimes this subtle distinction is needed. Then a <code class="computeroutput"><a class="link" href="../../boost/icl/partial_enricher.html" title="Struct partial_enricher">partial_enricher</a></code> 429 is the right choice. Also, If we want to give two <code class="computeroutput"><span class="identifier">icl</span><span class="special">::</span><span class="identifier">Maps</span></code> 430 a common set of keys in order to, say, iterate synchronously over both maps, 431 we need <span class="emphasis"><em>enrichers</em></span>. 432 </p> 433</div> 434<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 435<td align="left"></td> 436<td align="right"><div class="copyright-footer">Copyright © 2007-2010 Joachim 437 Faulhaber<br>Copyright © 1999-2006 Cortex Software 438 GmbH<p> 439 Distributed under the Boost Software License, Version 1.0. (See accompanying 440 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>) 441 </p> 442</div></td> 443</tr></table> 444<hr> 445<div class="spirit-nav"> 446<a accesskey="p" href="aggrovering.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../concepts.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="../semantics.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a> 447</div> 448</body> 449</html> 450
