ceph/src/boost/libs/icl/doc/html/boost_icl/concepts/sets_and_maps.html

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