ceph/src/boost/libs/icl/doc/html/boost_icl/function_reference/erasure.html

   1 <html>
   2 <head>
   3 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
   4 <title>Erasure</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="../function_reference.html" title="Function Reference">
   9 <link rel="prev" href="insertion.html" title="Insertion">
  10 <link rel="next" href="intersection.html" title="Intersection">
  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="insertion.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../function_reference.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="intersection.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
  24 </div>
  25 <div class="section boost_icl_function_reference_erasure" lang="en">
  26 <div class="titlepage"><div><div><h3 class="title">
  27 <a name="boost_icl.function_reference.erasure"></a><a class="link" href="erasure.html" title="Erasure">Erasure</a>
  28 </h3></div></div></div>
  29 <div class="toc"><dl>
  30 <dt><span class="section"><a href="erasure.html#boost_icl.function_reference.erasure.synopsis">Synopsis</a></span></dt>
  31 <dt><span class="section"><a href="erasure.html#boost_icl.function_reference.erasure.erasure_of_objects">Erasure
  32         of Objects</a></span></dt>
  33 <dt><span class="section"><a href="erasure.html#boost_icl.function_reference.erasure.erasure_by_iterators">Erasure
  34         by Iterators</a></span></dt>
  35 </dl></div>
  36 <div class="section boost_icl_function_reference_erasure_synopsis" lang="en">
  37 <div class="titlepage"><div><div><h4 class="title">
  38 <a name="boost_icl.function_reference.erasure.synopsis"></a><a class="link" href="erasure.html#boost_icl.function_reference.erasure.synopsis" title="Synopsis">Synopsis</a>
  39 </h4></div></div></div>
  40 <div class="informaltable"><table class="table">
  41 <colgroup>
  42 <col>
  43 <col>
  44 <col>
  45 <col>
  46 <col>
  47 </colgroup>
  48 <thead><tr>
  49 <th>
  50                 <p>
  51                   <span class="emphasis"><em><span class="bold"><strong>Erasure</strong></span></em></span>
  52                 </p>
  53                 </th>
  54 <th>
  55                 <p>
  56                   interval<br> sets
  57                 </p>
  58                 </th>
  59 <th>
  60                 <p>
  61                   interval<br> maps
  62                 </p>
  63                 </th>
  64 <th>
  65                 <p>
  66                   element<br> sets
  67                 </p>
  68                 </th>
  69 <th>
  70                 <p>
  71                   element<br> maps
  72                 </p>
  73                 </th>
  74 </tr></thead>
  75 <tbody>
  76 <tr>
  77 <td>
  78                 <p>
  79                   <code class="computeroutput"><span class="identifier">T</span><span class="special">&amp;</span>
  80                   <span class="identifier">T</span><span class="special">::</span><span class="identifier">erase</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span></code>
  81                 </p>
  82                 </td>
  83 <td>
  84                 <p>
  85                   <a class="link" href="../interface/function_synopsis.html#element_type"><span class="bold"><strong>e</strong></span></a>
  86                   <a class="link" href="../interface/function_synopsis.html#interval_type"><span class="bold"><strong>i</strong></span></a>
  87                 </p>
  88                 </td>
  89 <td>
  90                 <p>
  91                   <a class="link" href="../interface/function_synopsis.html#element_type"><span class="bold"><strong>e</strong></span></a>
  92                   <a class="link" href="../interface/function_synopsis.html#interval_type"><span class="bold"><strong>i</strong></span></a>
  93                   <a class="link" href="../interface/function_synopsis.html#element_mapping_type"><span class="bold"><strong>b</strong></span></a>
  94                   <a class="link" href="../interface/function_synopsis.html#interval_mapping_type"><span class="bold"><strong>p</strong></span></a>
  95                 </p>
  96                 </td>
  97 <td>
  98                 <p>
  99                   <a class="link" href="../interface/function_synopsis.html#element_type"><span class="bold"><strong>e</strong></span></a>
 100                 </p>
 101                 </td>
 102 <td>
 103                 <p>
 104                   <a class="link" href="../interface/function_synopsis.html#element_mapping_type"><span class="bold"><strong>b</strong></span></a>
 105                   <a class="link" href="../interface/function_synopsis.html#interval_mapping_type"><span class="bold"><strong>p</strong></span></a>
 106                 </p>
 107                 </td>
 108 </tr>
 109 <tr>
 110 <td>
 111                 <p>
 112                   <code class="computeroutput"><span class="identifier">T</span><span class="special">&amp;</span>
 113                   <span class="identifier">erase</span><span class="special">(</span><span class="identifier">T</span><span class="special">&amp;,</span>
 114                   <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span></code>
 115                 </p>
 116                 </td>
 117 <td>
 118                 <p>
 119                   <a class="link" href="../interface/function_synopsis.html#element_type"><span class="bold"><strong>e</strong></span></a>
 120                   <a class="link" href="../interface/function_synopsis.html#interval_type"><span class="bold"><strong>i</strong></span></a>
 121                   <a class="link" href="../interface/function_synopsis.html#interval_set_types"><span class="bold"><strong>S</strong></span></a>
 122                 </p>
 123                 </td>
 124 <td>
 125                 <p>
 126                   <a class="link" href="../interface/function_synopsis.html#element_type"><span class="bold"><strong>e</strong></span></a>
 127                   <a class="link" href="../interface/function_synopsis.html#interval_type"><span class="bold"><strong>i</strong></span></a>
 128                   <a class="link" href="../interface/function_synopsis.html#interval_set_types"><span class="bold"><strong>S</strong></span></a>
 129                   <a class="link" href="../interface/function_synopsis.html#element_mapping_type"><span class="bold"><strong>b</strong></span></a>
 130                   <a class="link" href="../interface/function_synopsis.html#interval_mapping_type"><span class="bold"><strong>p</strong></span></a>
 131                   <a class="link" href="../interface/function_synopsis.html#interval_map_types"><span class="bold"><strong>M</strong></span></a>
 132                 </p>
 133                 </td>
 134 <td>
 135                 <p>
 136                   <a class="link" href="../interface/function_synopsis.html#element_type"><span class="bold"><strong>e</strong></span></a>
 137                   <a class="link" href="../interface/function_synopsis.html#itl_set_type"><span class="bold"><strong>s</strong></span></a>
 138                 </p>
 139                 </td>
 140 <td>
 141                 <p>
 142                   <a class="link" href="../interface/function_synopsis.html#element_mapping_type"><span class="bold"><strong>b</strong></span></a>
 143                   <a class="link" href="../interface/function_synopsis.html#itl_map_type"><span class="bold"><strong>m</strong></span></a>
 144                 </p>
 145                 </td>
 146 </tr>
 147 <tr>
 148 <td>
 149                 <p>
 150                   <code class="computeroutput"><span class="keyword">void</span> <span class="identifier">T</span><span class="special">::</span><span class="identifier">erase</span><span class="special">(</span><span class="identifier">iterator</span><span class="special">)</span></code>
 151                 </p>
 152                 </td>
 153 <td>
 154                 <p>
 155                   1
 156                 </p>
 157                 </td>
 158 <td>
 159                 <p>
 160                   1
 161                 </p>
 162                 </td>
 163 <td>
 164                 <p>
 165                   1
 166                 </p>
 167                 </td>
 168 <td>
 169                 <p>
 170                   1
 171                 </p>
 172                 </td>
 173 </tr>
 174 <tr>
 175 <td>
 176                 <p>
 177                   <code class="computeroutput"><span class="keyword">void</span> <span class="identifier">T</span><span class="special">::</span><span class="identifier">erase</span><span class="special">(</span><span class="identifier">iterator</span><span class="special">,</span><span class="identifier">iterator</span><span class="special">)</span></code>
 178                 </p>
 179                 </td>
 180 <td>
 181                 <p>
 182                   1
 183                 </p>
 184                 </td>
 185 <td>
 186                 <p>
 187                   1
 188                 </p>
 189                 </td>
 190 <td>
 191                 <p>
 192                   1
 193                 </p>
 194                 </td>
 195 <td>
 196                 <p>
 197                   1
 198                 </p>
 199                 </td>
 200 </tr>
 201 </tbody>
 202 </table></div>
 203 <a name="boost_icl.function_reference.erasure.synopsis.erasure"></a><h6>
 204 <a name="id1167178"></a>
 205           <a class="link" href="erasure.html#boost_icl.function_reference.erasure.synopsis.erasure">Erasure</a>
 206         </h6>
 207 <p>
 208           The effects of <span class="emphasis"><em><span class="bold"><strong>erasure</strong></span></em></span>
 209           implemented by <code class="computeroutput"><span class="identifier">erase</span></code> and
 210           <span class="emphasis"><em><span class="bold"><strong>subtraction</strong></span></em></span> implemented
 211           by <code class="computeroutput"><span class="identifier">subtract</span></code> and <code class="computeroutput"><span class="keyword">operator</span> <span class="special">-=</span></code>
 212           are identical for all Set-types of the <span class="bold"><strong>icl</strong></span>.
 213         </p>
 214 <p>
 215           For Map-types, <code class="computeroutput"><span class="identifier">erase</span></code> provides
 216           the <span class="bold"><strong>stl</strong></span> semantics of erasure in contrast
 217           to <code class="computeroutput"><span class="identifier">subtract</span></code> and <code class="computeroutput"><span class="keyword">operator</span> <span class="special">-=</span></code>,
 218           that implement a generalized subtraction, that performs inverse aggregations
 219           if key values collide or key intervals overlap.
 220         </p>
 221 <p>
 222           Using iterators it is possible to erase objects or ranges of objects the
 223           iterator is pointing at from icl Sets and Maps.
 224         </p>
 225 </div>
 226 <div class="section boost_icl_function_reference_erasure_erasure_of_objects" lang="en">
 227 <div class="titlepage"><div><div><h4 class="title">
 228 <a name="boost_icl.function_reference.erasure.erasure_of_objects"></a><a class="link" href="erasure.html#boost_icl.function_reference.erasure.erasure_of_objects" title="Erasure of Objects">Erasure
 229         of Objects</a>
 230 </h4></div></div></div>
 231 <p>
 232
 233 </p>
 234 <pre class="programlisting"><span class="comment">/* overload table for */</span>       <span class="identifier">T</span><span class="special">\</span><span class="identifier">P</span><span class="special">|</span> <span class="identifier">e</span> <span class="identifier">i</span> <span class="identifier">b</span> <span class="identifier">p</span>
 235 <span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">T</span><span class="special">::</span><span class="identifier">erase</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span>          <span class="special">---+--------</span>
 236 <span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">erase</span><span class="special">(</span><span class="identifier">T</span><span class="special">&amp;,</span> <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span>          <span class="identifier">s</span> <span class="special">|</span> <span class="identifier">s</span>
 237                                 <span class="identifier">m</span> <span class="special">|</span>     <span class="identifier">m</span>
 238                                 <span class="identifier">S</span> <span class="special">|</span> <span class="identifier">S</span> <span class="identifier">S</span>
 239                                 <span class="identifier">M</span> <span class="special">|</span>     <span class="identifier">M</span> <span class="identifier">M</span>
 240 </pre>
 241 <p>
 242         </p>
 243 <p>
 244           The next table contains complexity characteristics for the <code class="computeroutput"><span class="identifier">erase</span></code> function on elements and segments.
 245         </p>
 246 <div class="table">
 247 <a name="id1168579"></a><p class="title"><b>Table&#160;1.31.&#160;Time Complexity for erasure of elements and segments
 248         on icl containers</b></p>
 249 <div class="table-contents"><table class="table" summary="Time Complexity for erasure of elements and segments
 250         on icl containers">
 251 <colgroup>
 252 <col>
 253 <col>
 254 <col>
 255 <col>
 256 <col>
 257 </colgroup>
 258 <thead><tr>
 259 <th>
 260               <p>
 261                 <code class="computeroutput"><span class="identifier">T</span><span class="special">&amp;</span>
 262                 <span class="identifier">T</span><span class="special">::</span><span class="identifier">erase</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span></code><br> <code class="computeroutput"><span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">erase</span><span class="special">(</span><span class="identifier">T</span><span class="special">&amp;,</span> <span class="keyword">const</span>
 263                 <span class="identifier">P</span><span class="special">&amp;)</span></code>
 264               </p>
 265               </th>
 266 <th>
 267               <p>
 268                 domain<br> type
 269               </p>
 270               </th>
 271 <th>
 272               <p>
 273                 interval<br> type
 274               </p>
 275               </th>
 276 <th>
 277               <p>
 278                 domain<br> mapping<br> type
 279               </p>
 280               </th>
 281 <th>
 282               <p>
 283                 interval<br> mapping<br> type
 284               </p>
 285               </th>
 286 </tr></thead>
 287 <tbody>
 288 <tr>
 289 <td>
 290               <p>
 291                 <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> </a>
 292               </p>
 293               </td>
 294 <td>
 295               <p>
 296                 <span class="emphasis"><em>O(log n)</em></span>
 297               </p>
 298               </td>
 299 <td>
 300               <p>
 301               </p>
 302               </td>
 303 <td>
 304               <p>
 305               </p>
 306               </td>
 307 <td>
 308               <p>
 309               </p>
 310               </td>
 311 </tr>
 312 <tr>
 313 <td>
 314               <p>
 315                 <code class="computeroutput"><a class="link" href="../../boost/icl/map.html" title="Class template map">icl::map</a></code>
 316               </p>
 317               </td>
 318 <td>
 319               <p>
 320                 <span class="emphasis"><em>O(log n)</em></span>
 321               </p>
 322               </td>
 323 <td>
 324               <p>
 325               </p>
 326               </td>
 327 <td>
 328               <p>
 329                 <span class="emphasis"><em>O(log n)</em></span>
 330               </p>
 331               </td>
 332 <td>
 333               <p>
 334               </p>
 335               </td>
 336 </tr>
 337 <tr>
 338 <td>
 339               <p>
 340                 <code class="computeroutput"><a class="link" href="../../boost/icl/interval_set.html" title="Class template interval_set">interval_sets</a></code>
 341               </p>
 342               </td>
 343 <td>
 344               <p>
 345                 <span class="emphasis"><em>O(log n)</em></span>
 346               </p>
 347               </td>
 348 <td>
 349               <p>
 350                 <span class="emphasis"><em>amortized<br> O(log n)</em></span>
 351               </p>
 352               </td>
 353 <td>
 354               <p>
 355               </p>
 356               </td>
 357 <td>
 358               <p>
 359               </p>
 360               </td>
 361 </tr>
 362 <tr>
 363 <td>
 364               <p>
 365                 <code class="computeroutput"><a class="link" href="../../boost/icl/interval_map.html" title="Class template interval_map">interval_maps</a></code>
 366               </p>
 367               </td>
 368 <td>
 369               <p>
 370                 <span class="emphasis"><em>O(log n)</em></span>
 371               </p>
 372               </td>
 373 <td>
 374               <p>
 375                 <span class="emphasis"><em>O(n)</em></span>
 376               </p>
 377               </td>
 378 <td>
 379               <p>
 380                 <span class="emphasis"><em>O(log n)</em></span>
 381               </p>
 382               </td>
 383 <td>
 384               <p>
 385                 <span class="emphasis"><em>O(n)</em></span>
 386               </p>
 387               </td>
 388 </tr>
 389 </tbody>
 390 </table></div>
 391 </div>
 392 <br class="table-break"><p>
 393           As presented in the overload tables for inplace function <code class="computeroutput"><span class="identifier">erase</span></code> below, more type combinations are
 394           available for <span class="emphasis"><em>erasure</em></span> than for <span class="emphasis"><em>insertion</em></span>.
 395         </p>
 396 <p>
 397
 398 </p>
 399 <pre class="programlisting"><span class="comment">// overload tables for function    element containers:     interval containers:
 400 </span><span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">erase</span><span class="special">(</span><span class="identifier">T</span><span class="special">&amp;,</span> <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span>             <span class="identifier">T</span><span class="special">\</span><span class="identifier">P</span><span class="special">|</span> <span class="identifier">e</span> <span class="identifier">b</span> <span class="identifier">s</span> <span class="identifier">m</span>            <span class="identifier">T</span><span class="special">\</span><span class="identifier">P</span><span class="special">|</span> <span class="identifier">e</span> <span class="identifier">i</span> <span class="identifier">b</span> <span class="identifier">p</span> <span class="identifier">S</span> <span class="identifier">M</span>
 401                                    <span class="special">---+--------</span>            <span class="special">---+------------</span>
 402                                     <span class="identifier">s</span> <span class="special">|</span> <span class="identifier">s</span>   <span class="identifier">s</span>               <span class="identifier">S</span> <span class="special">|</span> <span class="identifier">S</span> <span class="identifier">S</span>     <span class="identifier">S</span>
 403                                     <span class="identifier">m</span> <span class="special">|</span> <span class="identifier">m</span> <span class="identifier">m</span> <span class="identifier">m</span> <span class="identifier">m</span>             <span class="identifier">M</span> <span class="special">|</span> <span class="identifier">M</span> <span class="identifier">M</span> <span class="identifier">M</span> <span class="identifier">M</span> <span class="identifier">M</span> <span class="identifier">M</span>
 404 </pre>
 405 <p>
 406           We can split up these overloads in two groups. The first group can be called
 407           <span class="emphasis"><em>reverse insertion</em></span>.
 408 </p>
 409 <pre class="programlisting"><span class="comment">/* (1) Reverse insertion */</span>        <span class="identifier">T</span><span class="special">\</span><span class="identifier">P</span><span class="special">|</span> <span class="identifier">e</span> <span class="identifier">b</span> <span class="identifier">s</span> <span class="identifier">m</span>            <span class="identifier">T</span><span class="special">\</span><span class="identifier">P</span><span class="special">|</span> <span class="identifier">e</span> <span class="identifier">i</span> <span class="identifier">b</span> <span class="identifier">p</span> <span class="identifier">S</span> <span class="identifier">M</span>
 410                                    <span class="special">---+--------</span>            <span class="special">---+------------</span>
 411                                     <span class="identifier">s</span> <span class="special">|</span> <span class="identifier">s</span>   <span class="identifier">s</span>               <span class="identifier">S</span> <span class="special">|</span> <span class="identifier">S</span> <span class="identifier">S</span>     <span class="identifier">S</span>
 412                                     <span class="identifier">m</span> <span class="special">|</span>   <span class="identifier">m</span>   <span class="identifier">m</span>             <span class="identifier">M</span> <span class="special">|</span>     <span class="identifier">M</span> <span class="identifier">M</span>   <span class="identifier">M</span>
 413 </pre>
 414 <p>
 415           The second group can be viewed as an <span class="emphasis"><em>erasure by key objects</em></span>
 416
 417 </p>
 418 <pre class="programlisting"><span class="comment">/* (2) Erasure by key objects */</span>   <span class="identifier">T</span><span class="special">\</span><span class="identifier">P</span><span class="special">|</span> <span class="identifier">e</span> <span class="identifier">b</span> <span class="identifier">s</span> <span class="identifier">m</span>            <span class="identifier">T</span><span class="special">\</span><span class="identifier">P</span><span class="special">|</span> <span class="identifier">e</span> <span class="identifier">i</span> <span class="identifier">b</span> <span class="identifier">p</span> <span class="identifier">S</span> <span class="identifier">M</span>
 419                                    <span class="special">---+--------</span>            <span class="special">---+------------</span>
 420                                     <span class="identifier">s</span> <span class="special">|</span> <span class="identifier">s</span>   <span class="identifier">s</span>               <span class="identifier">S</span> <span class="special">|</span> <span class="identifier">S</span> <span class="identifier">S</span>     <span class="identifier">S</span>
 421                                     <span class="identifier">m</span> <span class="special">|</span> <span class="identifier">m</span>   <span class="identifier">m</span>               <span class="identifier">M</span> <span class="special">|</span> <span class="identifier">M</span> <span class="identifier">M</span>     <span class="identifier">M</span>
 422 </pre>
 423 <p>
 424         </p>
 425 <p>
 426           On Maps <span class="emphasis"><em><span class="bold"><strong>reverse insertion (1)</strong></span></em></span>
 427           is different from <span class="bold"><strong>stl's</strong></span> erase semantics,
 428           because value pairs are deleted only, if key <span class="emphasis"><em><span class="bold"><strong>and</strong></span></em></span>
 429           data values are found. Only <span class="emphasis"><em><span class="bold"><strong>erasure by
 430           key objects (2)</strong></span></em></span> works like the erase function on
 431           <span class="bold"><strong>stl's</strong></span> std::maps, that passes a <span class="emphasis"><em><span class="bold"><strong>key value</strong></span></em></span> as argument.
 432         </p>
 433 <p>
 434           On Sets both function groups fall together as <span class="emphasis"><em><span class="bold"><strong>set
 435           difference</strong></span></em></span>.
 436         </p>
 437 <p>
 438           Complexity characteristics for inplace erasure operations are given by
 439           the next tables where
 440 </p>
 441 <pre class="programlisting"><span class="identifier">n</span> <span class="special">=</span> <span class="identifier">iterative_size</span><span class="special">(</span><span class="identifier">y</span><span class="special">);</span>
 442 <span class="identifier">m</span> <span class="special">=</span> <span class="identifier">iterative_size</span><span class="special">(</span><span class="identifier">x</span><span class="special">);</span> <span class="comment">//if P is a container type
 443 </span></pre>
 444 <p>
 445         </p>
 446 <div class="table">
 447 <a name="id1169691"></a><p class="title"><b>Table&#160;1.32.&#160;Time Complexity for inplace erasure on element
 448         containers</b></p>
 449 <div class="table-contents"><table class="table" summary="Time Complexity for inplace erasure on element
 450         containers">
 451 <colgroup>
 452 <col>
 453 <col>
 454 <col>
 455 <col>
 456 <col>
 457 </colgroup>
 458 <thead><tr>
 459 <th>
 460               <p>
 461                 <code class="computeroutput"><span class="identifier">T</span><span class="special">&amp;</span>
 462                 <span class="identifier">erase</span><span class="special">(</span><span class="identifier">T</span><span class="special">&amp;</span>
 463                 <span class="identifier">y</span><span class="special">,</span>
 464                 <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;</span> <span class="identifier">x</span><span class="special">)</span></code>
 465               </p>
 466               </th>
 467 <th>
 468               <p>
 469                 domain<br> type
 470               </p>
 471               </th>
 472 <th>
 473               <p>
 474                 domain<br> mapping<br> type
 475               </p>
 476               </th>
 477 <th>
 478               <p>
 479                 std::set
 480               </p>
 481               </th>
 482 <th>
 483               <p>
 484                 icl::map
 485               </p>
 486               </th>
 487 </tr></thead>
 488 <tbody>
 489 <tr>
 490 <td>
 491               <p>
 492                 <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> </a>
 493               </p>
 494               </td>
 495 <td>
 496               <p>
 497                 <span class="emphasis"><em>O(log n)</em></span>
 498               </p>
 499               </td>
 500 <td>
 501               <p>
 502               </p>
 503               </td>
 504 <td>
 505               <p>
 506                 <span class="emphasis"><em>O(m log n)</em></span>
 507               </p>
 508               </td>
 509 <td>
 510               <p>
 511               </p>
 512               </td>
 513 </tr>
 514 <tr>
 515 <td>
 516               <p>
 517                 <code class="computeroutput"><a class="link" href="../../boost/icl/map.html" title="Class template map">icl::map</a></code>
 518               </p>
 519               </td>
 520 <td>
 521               <p>
 522                 <span class="emphasis"><em>O(log n)</em></span>
 523               </p>
 524               </td>
 525 <td>
 526               <p>
 527                 <span class="emphasis"><em>O(log n)</em></span>
 528               </p>
 529               </td>
 530 <td>
 531               <p>
 532                 <span class="emphasis"><em>O(m log n)</em></span>
 533               </p>
 534               </td>
 535 <td>
 536               <p>
 537                 <span class="emphasis"><em>O(m log n)</em></span>
 538               </p>
 539               </td>
 540 </tr>
 541 </tbody>
 542 </table></div>
 543 </div>
 544 <br class="table-break"><div class="table">
 545 <a name="id1169926"></a><p class="title"><b>Table&#160;1.33.&#160;Time Complexity for inplace erasure on
 546         interval containers</b></p>
 547 <div class="table-contents"><table class="table" summary="Time Complexity for inplace erasure on
 548         interval containers">
 549 <colgroup>
 550 <col>
 551 <col>
 552 <col>
 553 <col>
 554 <col>
 555 <col>
 556 <col>
 557 </colgroup>
 558 <thead><tr>
 559 <th>
 560               <p>
 561                 <code class="computeroutput"><span class="identifier">T</span><span class="special">&amp;</span>
 562                 <span class="identifier">erase</span><span class="special">(</span><span class="identifier">T</span><span class="special">&amp;</span>
 563                 <span class="identifier">y</span><span class="special">,</span>
 564                 <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;</span> <span class="identifier">x</span><span class="special">)</span></code>
 565               </p>
 566               </th>
 567 <th>
 568               <p>
 569                 domain<br> type
 570               </p>
 571               </th>
 572 <th>
 573               <p>
 574                 interval<br> type
 575               </p>
 576               </th>
 577 <th>
 578               <p>
 579                 domain<br> mapping<br> type
 580               </p>
 581               </th>
 582 <th>
 583               <p>
 584                 interval<br> mapping<br> type
 585               </p>
 586               </th>
 587 <th>
 588               <p>
 589                 interval<br> sets
 590               </p>
 591               </th>
 592 <th>
 593               <p>
 594                 interval<br> maps
 595               </p>
 596               </th>
 597 </tr></thead>
 598 <tbody>
 599 <tr>
 600 <td>
 601               <p>
 602                 interval_sets
 603               </p>
 604               </td>
 605 <td>
 606               <p>
 607                 <span class="emphasis"><em>O(log n)</em></span>
 608               </p>
 609               </td>
 610 <td>
 611               <p>
 612                 <span class="emphasis"><em>amortized<br> O(log n)</em></span>
 613               </p>
 614               </td>
 615 <td>
 616               <p>
 617               </p>
 618               </td>
 619 <td>
 620               <p>
 621               </p>
 622               </td>
 623 <td>
 624               <p>
 625                 <span class="emphasis"><em>O(m log(n+m))</em></span>
 626               </p>
 627               </td>
 628 <td>
 629               <p>
 630               </p>
 631               </td>
 632 </tr>
 633 <tr>
 634 <td>
 635               <p>
 636                 interval_maps
 637               </p>
 638               </td>
 639 <td>
 640               <p>
 641                 <span class="emphasis"><em>O(log n)</em></span>
 642               </p>
 643               </td>
 644 <td>
 645               <p>
 646                 <span class="emphasis"><em>amortized<br> O(log n)</em></span>
 647               </p>
 648               </td>
 649 <td>
 650               <p>
 651                 <span class="emphasis"><em>O(log n)</em></span>
 652               </p>
 653               </td>
 654 <td>
 655               <p>
 656                 <span class="emphasis"><em>O(n)</em></span>
 657               </p>
 658               </td>
 659 <td>
 660               <p>
 661                 <span class="emphasis"><em>O(m log(n+m))</em></span>
 662               </p>
 663               </td>
 664 <td>
 665               <p>
 666                 <span class="emphasis"><em>O(m log(n+m))</em></span>
 667               </p>
 668               </td>
 669 </tr>
 670 </tbody>
 671 </table></div>
 672 </div>
 673 <br class="table-break">
 674 </div>
 675 <div class="section boost_icl_function_reference_erasure_erasure_by_iterators" lang="en">
 676 <div class="titlepage"><div><div><h4 class="title">
 677 <a name="boost_icl.function_reference.erasure.erasure_by_iterators"></a><a class="link" href="erasure.html#boost_icl.function_reference.erasure.erasure_by_iterators" title="Erasure by Iterators">Erasure
 678         by Iterators</a>
 679 </h4></div></div></div>
 680 <p>
 681           The next table shows the <span class="bold"><strong>icl</strong></span> containers
 682           that erasure with iterators is available for. Erase on iterators erases
 683           always one <code class="computeroutput"><span class="identifier">value</span></code> of <code class="computeroutput"><span class="identifier">value_type</span></code> for an iterator pointing to
 684           it. So we erase
 685         </p>
 686 <div class="itemizedlist"><ul type="disc">
 687 <li>
 688             elements from <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">sets</span></code></a>
 689 </li>
 690 <li>
 691             element-value pairs from <code class="computeroutput"><a class="link" href="../../boost/icl/map.html" title="Class template map">icl::maps</a></code>
 692 </li>
 693 <li>
 694             intervals from <code class="computeroutput"><a class="link" href="../../boost/icl/interval_set.html" title="Class template interval_set">interval_sets</a></code>
 695             and
 696           </li>
 697 <li>
 698             interval-value-pairs from <code class="computeroutput"><a class="link" href="../../boost/icl/interval_map.html" title="Class template interval_map">interval_maps</a></code>
 699 </li>
 700 </ul></div>
 701 <div class="informaltable"><table class="table">
 702 <colgroup>
 703 <col>
 704 <col>
 705 <col>
 706 <col>
 707 <col>
 708 </colgroup>
 709 <thead><tr>
 710 <th>
 711                 <p>
 712                   <span class="emphasis"><em><span class="bold"><strong>Erasure by iterators</strong></span></em></span>
 713                 </p>
 714                 </th>
 715 <th>
 716                 <p>
 717                   interval<br> sets
 718                 </p>
 719                 </th>
 720 <th>
 721                 <p>
 722                   interval<br> maps
 723                 </p>
 724                 </th>
 725 <th>
 726                 <p>
 727                   element<br> sets
 728                 </p>
 729                 </th>
 730 <th>
 731                 <p>
 732                   element<br> maps
 733                 </p>
 734                 </th>
 735 </tr></thead>
 736 <tbody>
 737 <tr>
 738 <td>
 739                 <p>
 740                   <code class="computeroutput"><span class="keyword">void</span> <span class="identifier">T</span><span class="special">::</span><span class="identifier">erase</span><span class="special">(</span><span class="identifier">iterator</span>
 741                   <span class="identifier">pos</span><span class="special">)</span></code>
 742                 </p>
 743                 </td>
 744 <td>
 745                 <p>
 746                   <span class="emphasis"><em>amortized O(1)</em></span>
 747                 </p>
 748                 </td>
 749 <td>
 750                 <p>
 751                   <span class="emphasis"><em>amortized O(1)</em></span>
 752                 </p>
 753                 </td>
 754 <td>
 755                 <p>
 756                   <span class="emphasis"><em>amortized O(1)</em></span>
 757                 </p>
 758                 </td>
 759 <td>
 760                 <p>
 761                   <span class="emphasis"><em>amortized O(1)</em></span>
 762                 </p>
 763                 </td>
 764 </tr>
 765 <tr>
 766 <td>
 767                 <p>
 768                   <code class="computeroutput"><span class="keyword">void</span> <span class="identifier">T</span><span class="special">::</span><span class="identifier">erase</span><span class="special">(</span><span class="identifier">iterator</span>
 769                   <span class="identifier">first</span><span class="special">,</span>
 770                   <span class="identifier">iterator</span> <span class="identifier">past</span><span class="special">)</span></code>
 771                 </p>
 772                 </td>
 773 <td>
 774                 <p>
 775                   <span class="emphasis"><em>O(k)</em></span>
 776                 </p>
 777                 </td>
 778 <td>
 779                 <p>
 780                   <span class="emphasis"><em>O(k)</em></span>
 781                 </p>
 782                 </td>
 783 <td>
 784                 <p>
 785                   <span class="emphasis"><em>O(k)</em></span>
 786                 </p>
 787                 </td>
 788 <td>
 789                 <p>
 790                   <span class="emphasis"><em>O(k)</em></span>
 791                 </p>
 792                 </td>
 793 </tr>
 794 </tbody>
 795 </table></div>
 796 <p>
 797           Erasing by a single iterator need only <span class="emphasis"><em><span class="bold"><strong>amortized
 798           constant time</strong></span></em></span>. Erasing via a range of iterators
 799           <code class="computeroutput"><span class="special">[</span><span class="identifier">first</span><span class="special">,</span> <span class="identifier">past</span><span class="special">)</span></code> is of <span class="emphasis"><em><span class="bold"><strong>linear
 800           time</strong></span></em></span> in the number <code class="computeroutput"><span class="identifier">k</span></code>
 801           of iterators in range <code class="computeroutput"><span class="special">[</span><span class="identifier">first</span><span class="special">,</span> <span class="identifier">past</span><span class="special">)</span></code>.
 802         </p>
 803 </div>
 804 <p>
 805         <span class="emphasis"><em><span class="bold"><strong>See also . . .</strong></span></em></span>
 806       </p>
 807 <div class="informaltable"><table class="table">
 808 <colgroup><col></colgroup>
 809 <thead><tr></tr></thead>
 810 <tbody>
 811 <tr><td>
 812               <p>
 813                 <a class="link" href="insertion.html" title="Insertion"><span class="emphasis"><em><span class="bold"><strong>Insertion</strong></span></em></span></a>
 814               </p>
 815               </td></tr>
 816 <tr><td>
 817               <p>
 818                 <a class="link" href="subtraction.html" title="Subtraction"><span class="emphasis"><em><span class="bold"><strong>Subtraction</strong></span></em></span></a>
 819               </p>
 820               </td></tr>
 821 </tbody>
 822 </table></div>
 823 <p>
 824         <span class="emphasis"><em><span class="bold"><strong>Back to section . . .</strong></span></em></span>
 825       </p>
 826 <div class="informaltable"><table class="table">
 827 <colgroup><col></colgroup>
 828 <thead><tr></tr></thead>
 829 <tbody>
 830 <tr><td>
 831               <p>
 832                 <a class="link" href="../interface/function_synopsis.html#function_synopsis_table"><span class="emphasis"><em><span class="bold"><strong>Function
 833                 Synopsis</strong></span></em></span></a>
 834               </p>
 835               </td></tr>
 836 <tr><td>
 837               <p>
 838                 <a class="link" href="../interface.html" title="Interface"><span class="emphasis"><em><span class="bold"><strong>Interface</strong></span></em></span></a>
 839               </p>
 840               </td></tr>
 841 </tbody>
 842 </table></div>
 843 </div>
 844 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
 845 <td align="left"></td>
 846 <td align="right"><div class="copyright-footer">Copyright &#169; 2007 -2010 Joachim Faulhaber<br>Copyright &#169; 1999 -2006 Cortex Software GmbH<p>
 847         Distributed under the Boost Software License, Version 1.0. (See accompanying
 848         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>)
 849       </p>
 850 </div></td>
 851 </tr></table>
 852 <hr>
 853 <div class="spirit-nav">
 854 <a accesskey="p" href="insertion.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../function_reference.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="intersection.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
 855 </div>
 856 </body>
 857 </html>