1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 4<title>Sets and 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="../concepts.html" title="Concepts"> 9<link rel="prev" href="aspects.html" title="Aspects"> 10<link rel="next" href="aggrovering.html" title="Addability, Subtractability and Aggregate on Overlap"> 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="aspects.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="aggrovering.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.sets_and_maps"></a><a class="link" href="sets_and_maps.html" title="Sets and Maps">Sets and Maps</a> 28</h3></div></div></div> 29<h6> 30<a name="boost_icl.concepts.sets_and_maps.h0"></a> 31 <span class="phrase"><a name="boost_icl.concepts.sets_and_maps.a_set_concept"></a></span><a class="link" href="sets_and_maps.html#boost_icl.concepts.sets_and_maps.a_set_concept">A 32 Set Concept</a> 33 </h6> 34<p> 35 On the fundamental aspect all <code class="computeroutput"><a class="link" href="../../boost/icl/interval_base_set.html" title="Class template interval_base_set">interval_sets</a></code> 36 are models of a concept <code class="computeroutput"><span class="identifier">Set</span></code>. 37 The <code class="computeroutput"><span class="identifier">Set</span></code> concept of the Interval 38 Template Library refers to the mathematical notion of a set. 39 </p> 40<div class="informaltable"><table class="table"> 41<colgroup> 42<col> 43<col> 44<col> 45</colgroup> 46<thead><tr> 47<th> 48 <p> 49 Function 50 </p> 51 </th> 52<th> 53 <p> 54 Variant 55 </p> 56 </th> 57<th> 58 <p> 59 implemented as 60 </p> 61 </th> 62</tr></thead> 63<tbody> 64<tr> 65<td> 66 <p> 67 empty set 68 </p> 69 </td> 70<td> 71 </td> 72<td> 73 <p> 74 <code class="computeroutput"><span class="identifier">Set</span><span class="special">::</span><span class="identifier">Set</span><span class="special">()</span></code> 75 </p> 76 </td> 77</tr> 78<tr> 79<td> 80 <p> 81 subset relation 82 </p> 83 </td> 84<td> 85 </td> 86<td> 87 <p> 88 <code class="computeroutput"><span class="keyword">bool</span> <span class="identifier">Set</span><span class="special">::</span><span class="identifier">within</span><span class="special">(</span><span class="keyword">const</span> 89 <span class="identifier">Set</span><span class="special">&</span> 90 <span class="identifier">s1</span><span class="special">,</span> 91 <span class="keyword">const</span> <span class="identifier">Set</span><span class="special">&</span> <span class="identifier">s2</span><span class="special">)</span><span class="keyword">const</span></code> 92 </p> 93 </td> 94</tr> 95<tr> 96<td> 97 <p> 98 equality 99 </p> 100 </td> 101<td> 102 </td> 103<td> 104 <p> 105 <code class="computeroutput"><span class="keyword">bool</span> <span class="identifier">is_element_equal</span><span class="special">(</span><span class="keyword">const</span> 106 <span class="identifier">Set</span><span class="special">&</span> 107 <span class="identifier">s1</span><span class="special">,</span> 108 <span class="keyword">const</span> <span class="identifier">Set</span><span class="special">&</span> <span class="identifier">s2</span><span class="special">)</span></code> 109 </p> 110 </td> 111</tr> 112<tr> 113<td> 114 <p> 115 set union 116 </p> 117 </td> 118<td> 119 <p> 120 inplace 121 </p> 122 </td> 123<td> 124 <p> 125 <code class="computeroutput"><span class="identifier">Set</span><span class="special">&</span> 126 <span class="keyword">operator</span> <span class="special">+=</span> 127 <span class="special">(</span><span class="identifier">Set</span><span class="special">&</span> <span class="identifier">s1</span><span class="special">,</span> <span class="keyword">const</span> 128 <span class="identifier">Set</span><span class="special">&</span> 129 <span class="identifier">s2</span><span class="special">)</span></code> 130 </p> 131 </td> 132</tr> 133<tr> 134<td> 135 </td> 136<td> 137 </td> 138<td> 139 <p> 140 <code class="computeroutput"><span class="identifier">Set</span> <span class="keyword">operator</span> 141 <span class="special">+</span> <span class="special">(</span><span class="keyword">const</span> <span class="identifier">Set</span><span class="special">&</span> <span class="identifier">s1</span><span class="special">,</span> <span class="keyword">const</span> 142 <span class="identifier">Set</span><span class="special">&</span> 143 <span class="identifier">s2</span><span class="special">)</span></code> 144 </p> 145 </td> 146</tr> 147<tr> 148<td> 149 <p> 150 set difference 151 </p> 152 </td> 153<td> 154 <p> 155 inplace 156 </p> 157 </td> 158<td> 159 <p> 160 <code class="computeroutput"><span class="identifier">Set</span><span class="special">&</span> 161 <span class="keyword">operator</span> <span class="special">-=</span> 162 <span class="special">(</span><span class="identifier">Set</span><span class="special">&</span> <span class="identifier">s1</span><span class="special">,</span> <span class="keyword">const</span> 163 <span class="identifier">Set</span><span class="special">&</span> 164 <span class="identifier">s2</span><span class="special">)</span></code> 165 </p> 166 </td> 167</tr> 168<tr> 169<td> 170 </td> 171<td> 172 </td> 173<td> 174 <p> 175 <code class="computeroutput"><span class="identifier">Set</span> <span class="keyword">operator</span> 176 <span class="special">-</span> <span class="special">(</span><span class="keyword">const</span> <span class="identifier">Set</span><span class="special">&</span> <span class="identifier">s1</span><span class="special">,</span> <span class="keyword">const</span> 177 <span class="identifier">Set</span><span class="special">&</span> 178 <span class="identifier">s2</span><span class="special">)</span></code> 179 </p> 180 </td> 181</tr> 182<tr> 183<td> 184 <p> 185 set intersection 186 </p> 187 </td> 188<td> 189 <p> 190 inplace 191 </p> 192 </td> 193<td> 194 <p> 195 <code class="computeroutput"><span class="identifier">Set</span><span class="special">&</span> 196 <span class="keyword">operator</span> <span class="special">&=</span> 197 <span class="special">(</span><span class="identifier">Set</span><span class="special">&</span> <span class="identifier">s1</span><span class="special">,</span> <span class="keyword">const</span> 198 <span class="identifier">Set</span><span class="special">&</span> 199 <span class="identifier">s2</span><span class="special">)</span></code> 200 </p> 201 </td> 202</tr> 203<tr> 204<td> 205 </td> 206<td> 207 </td> 208<td> 209 <p> 210 <code class="computeroutput"><span class="identifier">Set</span> <span class="keyword">operator</span> 211 <span class="special">&</span> <span class="special">(</span><span class="keyword">const</span> <span class="identifier">Set</span><span class="special">&</span> <span class="identifier">s1</span><span class="special">,</span> <span class="keyword">const</span> 212 <span class="identifier">Set</span><span class="special">&</span> 213 <span class="identifier">s2</span><span class="special">)</span></code> 214 </p> 215 </td> 216</tr> 217</tbody> 218</table></div> 219<p> 220 Equality on <code class="computeroutput"><span class="identifier">Sets</span></code> is not implemented 221 as <code class="computeroutput"><span class="keyword">operator</span> <span class="special">==</span></code>, 222 because <code class="computeroutput"><span class="keyword">operator</span> <span class="special">==</span></code> 223 is used for the stronger lexicographical equality on segments, that takes 224 the segmentation of elements into account. 225 </p> 226<p> 227 Being models of concept <code class="computeroutput"><span class="identifier">Set</span></code>, 228 <a href="http://www.cplusplus.com/reference/stl/set/" target="_top"><code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span></code> 229 </a> and all <code class="computeroutput"><a class="link" href="../../boost/icl/interval_base_set.html" title="Class template interval_base_set">interval_sets</a></code> 230 implement these operations and obey the associated laws on <code class="computeroutput"><span class="identifier">Sets</span></code>. See e.g. <a href="http://en.wikipedia.org/wiki/Algebra_of_sets" target="_top">an 231 algebra of sets here</a>. 232 </p> 233<h6> 234<a name="boost_icl.concepts.sets_and_maps.h1"></a> 235 <span class="phrase"><a name="boost_icl.concepts.sets_and_maps.making_intervals_complete"></a></span><a class="link" href="sets_and_maps.html#boost_icl.concepts.sets_and_maps.making_intervals_complete">Making 236 intervals complete</a> 237 </h6> 238<p> 239 An <code class="computeroutput"><a class="link" href="../../boost/icl/interval.html" title="Struct template interval">interval</a></code> is considered 240 to be a set of elements as well. With respect to the <code class="computeroutput"><span class="identifier">Set</span></code> 241 concept presented above <code class="computeroutput"><a class="link" href="../../boost/icl/interval.html" title="Struct template interval">interval</a></code> 242 implements the concept only partially. The reason for that is that addition 243 and subtraction can not be defined on <code class="computeroutput"><a class="link" href="../../boost/icl/interval.html" title="Struct template interval">intervals</a></code>. 244 Two intervals <code class="computeroutput"><span class="special">[</span><span class="number">1</span><span class="special">,</span><span class="number">2</span><span class="special">]</span></code> 245 and <code class="computeroutput"><span class="special">[</span><span class="number">4</span><span class="special">,</span><span class="number">5</span><span class="special">]</span></code> 246 are not addable to a <span class="emphasis"><em><span class="bold"><strong>single</strong></span></em></span> 247 new <code class="computeroutput"><a class="link" href="../../boost/icl/interval.html" title="Struct template interval">interval</a></code>. In other 248 words <code class="computeroutput"><a class="link" href="../../boost/icl/interval.html" title="Struct template interval">intervals</a></code> are incomplete 249 w.r.t. union and difference. <code class="computeroutput"><a class="link" href="../../boost/icl/interval_set.html" title="Class template interval_set">Interval_sets</a></code> 250 can be defined as the <span class="emphasis"><em><span class="bold"><strong>completion</strong></span></em></span> 251 of intervals for the union and difference operations. 252 </p> 253<p> 254 When we claim that addition or subtraction can not be defined on intervals, 255 we are not considering things like e.g. interval arithmetics, where these 256 operations can be defined, but with a different semantics. 257 </p> 258<h6> 259<a name="boost_icl.concepts.sets_and_maps.h2"></a> 260 <span class="phrase"><a name="boost_icl.concepts.sets_and_maps.a_map_concept"></a></span><a class="link" href="sets_and_maps.html#boost_icl.concepts.sets_and_maps.a_map_concept">A 261 Map Concept</a> 262 </h6> 263<p> 264 On the fundamental aspect <code class="computeroutput"><a class="link" href="../../boost/icl/map.html" title="Class template map">icl::map</a></code> 265 and all <code class="computeroutput"><a class="link" href="../../boost/icl/interval_base_map.html" title="Class template interval_base_map">interval_maps</a></code> 266 are models of a concept <code class="computeroutput"><span class="identifier">Map</span></code>. 267 Since a <code class="computeroutput"><span class="identifier">map</span></code> is a <code class="computeroutput"><span class="identifier">set</span> <span class="identifier">of</span> <span class="identifier">pairs</span></code>, we try to design the <code class="computeroutput"><span class="identifier">Map</span></code> concept in accordance to the <code class="computeroutput"><span class="identifier">Set</span></code> concept above. 268 </p> 269<div class="informaltable"><table class="table"> 270<colgroup> 271<col> 272<col> 273<col> 274</colgroup> 275<thead><tr> 276<th> 277 <p> 278 Function 279 </p> 280 </th> 281<th> 282 <p> 283 Variant 284 </p> 285 </th> 286<th> 287 <p> 288 implemented as 289 </p> 290 </th> 291</tr></thead> 292<tbody> 293<tr> 294<td> 295 <p> 296 empty map 297 </p> 298 </td> 299<td> 300 </td> 301<td> 302 <p> 303 <code class="computeroutput"><span class="identifier">Map</span><span class="special">::</span><span class="identifier">Map</span><span class="special">()</span></code> 304 </p> 305 </td> 306</tr> 307<tr> 308<td> 309 <p> 310 subset relation 311 </p> 312 </td> 313<td> 314 </td> 315<td> 316 <p> 317 <code class="computeroutput"><span class="keyword">bool</span> <span class="identifier">within</span><span class="special">(</span><span class="keyword">const</span> 318 <span class="identifier">Map</span><span class="special">&</span> 319 <span class="identifier">s2</span><span class="special">,</span> 320 <span class="keyword">const</span> <span class="identifier">Map</span><span class="special">&</span> <span class="identifier">s2</span><span class="special">)</span><span class="keyword">const</span></code> 321 </p> 322 </td> 323</tr> 324<tr> 325<td> 326 <p> 327 equality 328 </p> 329 </td> 330<td> 331 </td> 332<td> 333 <p> 334 <code class="computeroutput"><span class="keyword">bool</span> <span class="identifier">is_element_equal</span><span class="special">(</span><span class="keyword">const</span> 335 <span class="identifier">Map</span><span class="special">&</span> 336 <span class="identifier">s1</span><span class="special">,</span> 337 <span class="keyword">const</span> <span class="identifier">Map</span><span class="special">&</span> <span class="identifier">s2</span><span class="special">)</span></code> 338 </p> 339 </td> 340</tr> 341<tr> 342<td> 343 <p> 344 map union 345 </p> 346 </td> 347<td> 348 <p> 349 inplace 350 </p> 351 </td> 352<td> 353 <p> 354 <code class="computeroutput"><span class="identifier">Map</span><span class="special">&</span> 355 <span class="keyword">operator</span> <span class="special">+=</span> 356 <span class="special">(</span><span class="identifier">Map</span><span class="special">&</span> <span class="identifier">s1</span><span class="special">,</span> <span class="keyword">const</span> 357 <span class="identifier">Map</span><span class="special">&</span> 358 <span class="identifier">s2</span><span class="special">)</span></code> 359 </p> 360 </td> 361</tr> 362<tr> 363<td> 364 </td> 365<td> 366 </td> 367<td> 368 <p> 369 <code class="computeroutput"><span class="identifier">Map</span> <span class="keyword">operator</span> 370 <span class="special">+</span> <span class="special">(</span><span class="keyword">const</span> <span class="identifier">Map</span><span class="special">&</span> <span class="identifier">s1</span><span class="special">,</span> <span class="keyword">const</span> 371 <span class="identifier">Map</span><span class="special">&</span> 372 <span class="identifier">s2</span><span class="special">)</span></code> 373 </p> 374 </td> 375</tr> 376<tr> 377<td> 378 <p> 379 map difference 380 </p> 381 </td> 382<td> 383 <p> 384 inplace 385 </p> 386 </td> 387<td> 388 <p> 389 <code class="computeroutput"><span class="identifier">Map</span><span class="special">&</span> 390 <span class="keyword">operator</span> <span class="special">-=</span> 391 <span class="special">(</span><span class="identifier">Map</span><span class="special">&</span> <span class="identifier">s1</span><span class="special">,</span> <span class="keyword">const</span> 392 <span class="identifier">Map</span><span class="special">&</span> 393 <span class="identifier">s2</span><span class="special">)</span></code> 394 </p> 395 </td> 396</tr> 397<tr> 398<td> 399 </td> 400<td> 401 </td> 402<td> 403 <p> 404 <code class="computeroutput"><span class="identifier">Map</span> <span class="keyword">operator</span> 405 <span class="special">-</span> <span class="special">(</span><span class="keyword">const</span> <span class="identifier">Map</span><span class="special">&</span> <span class="identifier">s1</span><span class="special">,</span> <span class="keyword">const</span> 406 <span class="identifier">Map</span><span class="special">&</span> 407 <span class="identifier">s2</span><span class="special">)</span></code> 408 </p> 409 </td> 410</tr> 411<tr> 412<td> 413 <p> 414 map intersection 415 </p> 416 </td> 417<td> 418 <p> 419 inplace 420 </p> 421 </td> 422<td> 423 <p> 424 <code class="computeroutput"><span class="identifier">Map</span><span class="special">&</span> 425 <span class="keyword">operator</span> <span class="special">&=</span> 426 <span class="special">(</span><span class="identifier">Map</span><span class="special">&</span> <span class="identifier">s1</span><span class="special">,</span> <span class="keyword">const</span> 427 <span class="identifier">Map</span><span class="special">&</span> 428 <span class="identifier">s2</span><span class="special">)</span></code> 429 </p> 430 </td> 431</tr> 432<tr> 433<td> 434 </td> 435<td> 436 </td> 437<td> 438 <p> 439 <code class="computeroutput"><span class="identifier">Map</span> <span class="keyword">operator</span> 440 <span class="special">&</span> <span class="special">(</span><span class="keyword">const</span> <span class="identifier">Map</span><span class="special">&</span> <span class="identifier">s1</span><span class="special">,</span> <span class="keyword">const</span> 441 <span class="identifier">Map</span><span class="special">&</span> 442 <span class="identifier">s2</span><span class="special">)</span></code> 443 </p> 444 </td> 445</tr> 446</tbody> 447</table></div> 448<p> 449 As one can see, on the abstract kernel the signatures of the icl's <code class="computeroutput"><span class="identifier">Set</span></code> and <code class="computeroutput"><span class="identifier">Map</span></code> 450 concepts are identical, except for the typename. While signatures are identical 451 The sets of valid laws are different, which will be described in more detail 452 in the sections on the <a class="link" href="../semantics/sets.html" title="Sets">semantics 453 of icl Sets</a> and <a class="link" href="../semantics/maps.html" title="Maps">Maps</a>. 454 These semantic differences are mainly based on the implementation of the 455 pivotal member functions <code class="computeroutput"><span class="identifier">add</span></code> 456 and <code class="computeroutput"><span class="identifier">subtract</span></code> for elements 457 and intervals that again serve for implementing <code class="computeroutput"><span class="keyword">operator</span> 458 <span class="special">+=</span></code> and <code class="computeroutput"><span class="keyword">operator</span> 459 <span class="special">-=</span></code>. 460 </p> 461</div> 462<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 463<td align="left"></td> 464<td align="right"><div class="copyright-footer">Copyright © 2007-2010 Joachim 465 Faulhaber<br>Copyright © 1999-2006 Cortex Software 466 GmbH<p> 467 Distributed under the Boost Software License, Version 1.0. (See accompanying 468 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>) 469 </p> 470</div></td> 471</tr></table> 472<hr> 473<div class="spirit-nav"> 474<a accesskey="p" href="aspects.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="aggrovering.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a> 475</div> 476</body> 477</html> 478
