1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 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.79.1"> 7<link rel="home" href="../../index.html" title="Chapter 1. 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"> 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 class="toc"> 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"> 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">&</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">&)</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">&</span> 113 <span class="identifier">erase</span><span class="special">(</span><span class="identifier">T</span><span class="special">&,</span> 114 <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&)</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<h6> 204<a name="boost_icl.function_reference.erasure.synopsis.h0"></a> 205 <span class="phrase"><a name="boost_icl.function_reference.erasure.synopsis.erasure"></a></span><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"> 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</p> 233<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> 234<span class="identifier">T</span><span class="special">&</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">&)</span> <span class="special">---+--------</span> 235<span class="identifier">T</span><span class="special">&</span> <span class="identifier">erase</span><span class="special">(</span><span class="identifier">T</span><span class="special">&,</span> <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&)</span> <span class="identifier">s</span> <span class="special">|</span> <span class="identifier">s</span> 236 <span class="identifier">m</span> <span class="special">|</span> <span class="identifier">m</span> 237 <span class="identifier">S</span> <span class="special">|</span> <span class="identifier">S</span> <span class="identifier">S</span> 238 <span class="identifier">M</span> <span class="special">|</span> <span class="identifier">M</span> <span class="identifier">M</span> 239</pre> 240<p> 241 </p> 242<p> 243 The next table contains complexity characteristics for the <code class="computeroutput"><span class="identifier">erase</span></code> function on elements and segments. 244 </p> 245<div class="table"> 246<a name="boost_icl.function_reference.erasure.erasure_of_objects.t0"></a><p class="title"><b>Table 1.31. Time Complexity for erasure of elements and segments on icl containers</b></p> 247<div class="table-contents"><table class="table" summary="Time Complexity for erasure of elements and segments on icl containers"> 248<colgroup> 249<col> 250<col> 251<col> 252<col> 253<col> 254</colgroup> 255<thead><tr> 256<th> 257 <p> 258 <code class="computeroutput"><span class="identifier">T</span><span class="special">&</span> 259 <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">&)</span></code><br> <code class="computeroutput"><span class="identifier">T</span><span class="special">&</span> <span class="identifier">erase</span><span class="special">(</span><span class="identifier">T</span><span class="special">&,</span> <span class="keyword">const</span> 260 <span class="identifier">P</span><span class="special">&)</span></code> 261 </p> 262 </th> 263<th> 264 <p> 265 domain<br> type 266 </p> 267 </th> 268<th> 269 <p> 270 interval<br> type 271 </p> 272 </th> 273<th> 274 <p> 275 domain<br> mapping<br> type 276 </p> 277 </th> 278<th> 279 <p> 280 interval<br> mapping<br> type 281 </p> 282 </th> 283</tr></thead> 284<tbody> 285<tr> 286<td> 287 <p> 288 <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> 289 </p> 290 </td> 291<td> 292 <p> 293 <span class="emphasis"><em>O(log n)</em></span> 294 </p> 295 </td> 296<td> 297 </td> 298<td> 299 </td> 300<td> 301 </td> 302</tr> 303<tr> 304<td> 305 <p> 306 <code class="computeroutput"><a class="link" href="../../boost/icl/map.html" title="Class template map">icl::map</a></code> 307 </p> 308 </td> 309<td> 310 <p> 311 <span class="emphasis"><em>O(log n)</em></span> 312 </p> 313 </td> 314<td> 315 </td> 316<td> 317 <p> 318 <span class="emphasis"><em>O(log n)</em></span> 319 </p> 320 </td> 321<td> 322 </td> 323</tr> 324<tr> 325<td> 326 <p> 327 <code class="computeroutput"><a class="link" href="../../boost/icl/interval_set.html" title="Class template interval_set">interval_sets</a></code> 328 </p> 329 </td> 330<td> 331 <p> 332 <span class="emphasis"><em>O(log n)</em></span> 333 </p> 334 </td> 335<td> 336 <p> 337 <span class="emphasis"><em>amortized<br> O(log n)</em></span> 338 </p> 339 </td> 340<td> 341 </td> 342<td> 343 </td> 344</tr> 345<tr> 346<td> 347 <p> 348 <code class="computeroutput"><a class="link" href="../../boost/icl/interval_map.html" title="Class template interval_map">interval_maps</a></code> 349 </p> 350 </td> 351<td> 352 <p> 353 <span class="emphasis"><em>O(log n)</em></span> 354 </p> 355 </td> 356<td> 357 <p> 358 <span class="emphasis"><em>O(n)</em></span> 359 </p> 360 </td> 361<td> 362 <p> 363 <span class="emphasis"><em>O(log n)</em></span> 364 </p> 365 </td> 366<td> 367 <p> 368 <span class="emphasis"><em>O(n)</em></span> 369 </p> 370 </td> 371</tr> 372</tbody> 373</table></div> 374</div> 375<br class="table-break"><p> 376 As presented in the overload tables for inplace function <code class="computeroutput"><span class="identifier">erase</span></code> below, more type combinations are 377 available for <span class="emphasis"><em>erasure</em></span> than for <span class="emphasis"><em>insertion</em></span>. 378 </p> 379<p> 380</p> 381<pre class="programlisting"><span class="comment">// overload tables for function element containers: interval containers: </span> 382<span class="identifier">T</span><span class="special">&</span> <span class="identifier">erase</span><span class="special">(</span><span class="identifier">T</span><span class="special">&,</span> <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&)</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> 383 <span class="special">---+--------</span> <span class="special">---+------------</span> 384 <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> 385 <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> 386</pre> 387<p> 388 We can split up these overloads in two groups. The first group can be called 389 <span class="emphasis"><em>reverse insertion</em></span>. 390</p> 391<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> 392 <span class="special">---+--------</span> <span class="special">---+------------</span> 393 <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> 394 <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> 395</pre> 396<p> 397 The second group can be viewed as an <span class="emphasis"><em>erasure by key objects</em></span> 398</p> 399<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> 400 <span class="special">---+--------</span> <span class="special">---+------------</span> 401 <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> 402 <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> 403</pre> 404<p> 405 </p> 406<p> 407 On Maps <span class="emphasis"><em><span class="bold"><strong>reverse insertion (1)</strong></span></em></span> 408 is different from <span class="bold"><strong>stl's</strong></span> erase semantics, 409 because value pairs are deleted only, if key <span class="emphasis"><em><span class="bold"><strong>and</strong></span></em></span> 410 data values are found. Only <span class="emphasis"><em><span class="bold"><strong>erasure by 411 key objects (2)</strong></span></em></span> works like the erase function on 412 <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. 413 </p> 414<p> 415 On Sets both function groups fall together as <span class="emphasis"><em><span class="bold"><strong>set 416 difference</strong></span></em></span>. 417 </p> 418<p> 419 Complexity characteristics for inplace erasure operations are given by 420 the next tables where 421</p> 422<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> 423<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</span> 424</pre> 425<p> 426 </p> 427<div class="table"> 428<a name="boost_icl.function_reference.erasure.erasure_of_objects.t1"></a><p class="title"><b>Table 1.32. Time Complexity for inplace erasure on element containers</b></p> 429<div class="table-contents"><table class="table" summary="Time Complexity for inplace erasure on element containers"> 430<colgroup> 431<col> 432<col> 433<col> 434<col> 435<col> 436</colgroup> 437<thead><tr> 438<th> 439 <p> 440 <code class="computeroutput"><span class="identifier">T</span><span class="special">&</span> 441 <span class="identifier">erase</span><span class="special">(</span><span class="identifier">T</span><span class="special">&</span> 442 <span class="identifier">y</span><span class="special">,</span> 443 <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&</span> <span class="identifier">x</span><span class="special">)</span></code> 444 </p> 445 </th> 446<th> 447 <p> 448 domain<br> type 449 </p> 450 </th> 451<th> 452 <p> 453 domain<br> mapping<br> type 454 </p> 455 </th> 456<th> 457 <p> 458 std::set 459 </p> 460 </th> 461<th> 462 <p> 463 icl::map 464 </p> 465 </th> 466</tr></thead> 467<tbody> 468<tr> 469<td> 470 <p> 471 <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> 472 </p> 473 </td> 474<td> 475 <p> 476 <span class="emphasis"><em>O(log n)</em></span> 477 </p> 478 </td> 479<td> 480 </td> 481<td> 482 <p> 483 <span class="emphasis"><em>O(m log n)</em></span> 484 </p> 485 </td> 486<td> 487 </td> 488</tr> 489<tr> 490<td> 491 <p> 492 <code class="computeroutput"><a class="link" href="../../boost/icl/map.html" title="Class template map">icl::map</a></code> 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 <span class="emphasis"><em>O(log n)</em></span> 503 </p> 504 </td> 505<td> 506 <p> 507 <span class="emphasis"><em>O(m log n)</em></span> 508 </p> 509 </td> 510<td> 511 <p> 512 <span class="emphasis"><em>O(m log n)</em></span> 513 </p> 514 </td> 515</tr> 516</tbody> 517</table></div> 518</div> 519<br class="table-break"><div class="table"> 520<a name="boost_icl.function_reference.erasure.erasure_of_objects.t2"></a><p class="title"><b>Table 1.33. Time Complexity for inplace erasure on interval containers</b></p> 521<div class="table-contents"><table class="table" summary="Time Complexity for inplace erasure on interval containers"> 522<colgroup> 523<col> 524<col> 525<col> 526<col> 527<col> 528<col> 529<col> 530</colgroup> 531<thead><tr> 532<th> 533 <p> 534 <code class="computeroutput"><span class="identifier">T</span><span class="special">&</span> 535 <span class="identifier">erase</span><span class="special">(</span><span class="identifier">T</span><span class="special">&</span> 536 <span class="identifier">y</span><span class="special">,</span> 537 <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&</span> <span class="identifier">x</span><span class="special">)</span></code> 538 </p> 539 </th> 540<th> 541 <p> 542 domain<br> type 543 </p> 544 </th> 545<th> 546 <p> 547 interval<br> type 548 </p> 549 </th> 550<th> 551 <p> 552 domain<br> mapping<br> type 553 </p> 554 </th> 555<th> 556 <p> 557 interval<br> mapping<br> type 558 </p> 559 </th> 560<th> 561 <p> 562 interval<br> sets 563 </p> 564 </th> 565<th> 566 <p> 567 interval<br> maps 568 </p> 569 </th> 570</tr></thead> 571<tbody> 572<tr> 573<td> 574 <p> 575 interval_sets 576 </p> 577 </td> 578<td> 579 <p> 580 <span class="emphasis"><em>O(log n)</em></span> 581 </p> 582 </td> 583<td> 584 <p> 585 <span class="emphasis"><em>amortized<br> O(log n)</em></span> 586 </p> 587 </td> 588<td> 589 </td> 590<td> 591 </td> 592<td> 593 <p> 594 <span class="emphasis"><em>O(m log(n+m))</em></span> 595 </p> 596 </td> 597<td> 598 </td> 599</tr> 600<tr> 601<td> 602 <p> 603 interval_maps 604 </p> 605 </td> 606<td> 607 <p> 608 <span class="emphasis"><em>O(log n)</em></span> 609 </p> 610 </td> 611<td> 612 <p> 613 <span class="emphasis"><em>amortized<br> O(log n)</em></span> 614 </p> 615 </td> 616<td> 617 <p> 618 <span class="emphasis"><em>O(log n)</em></span> 619 </p> 620 </td> 621<td> 622 <p> 623 <span class="emphasis"><em>O(n)</em></span> 624 </p> 625 </td> 626<td> 627 <p> 628 <span class="emphasis"><em>O(m log(n+m))</em></span> 629 </p> 630 </td> 631<td> 632 <p> 633 <span class="emphasis"><em>O(m log(n+m))</em></span> 634 </p> 635 </td> 636</tr> 637</tbody> 638</table></div> 639</div> 640<br class="table-break"> 641</div> 642<div class="section"> 643<div class="titlepage"><div><div><h4 class="title"> 644<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 645 by Iterators</a> 646</h4></div></div></div> 647<p> 648 The next table shows the <span class="bold"><strong>icl</strong></span> containers 649 that erasure with iterators is available for. Erase on iterators erases 650 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 651 it. So we erase 652 </p> 653<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 654<li class="listitem"> 655 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> 656 </li> 657<li class="listitem"> 658 element-value pairs from <code class="computeroutput"><a class="link" href="../../boost/icl/map.html" title="Class template map">icl::maps</a></code> 659 </li> 660<li class="listitem"> 661 intervals from <code class="computeroutput"><a class="link" href="../../boost/icl/interval_set.html" title="Class template interval_set">interval_sets</a></code> 662 and 663 </li> 664<li class="listitem"> 665 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> 666 </li> 667</ul></div> 668<div class="informaltable"><table class="table"> 669<colgroup> 670<col> 671<col> 672<col> 673<col> 674<col> 675</colgroup> 676<thead><tr> 677<th> 678 <p> 679 <span class="emphasis"><em><span class="bold"><strong>Erasure by iterators</strong></span></em></span> 680 </p> 681 </th> 682<th> 683 <p> 684 interval<br> sets 685 </p> 686 </th> 687<th> 688 <p> 689 interval<br> maps 690 </p> 691 </th> 692<th> 693 <p> 694 element<br> sets 695 </p> 696 </th> 697<th> 698 <p> 699 element<br> maps 700 </p> 701 </th> 702</tr></thead> 703<tbody> 704<tr> 705<td> 706 <p> 707 <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> 708 <span class="identifier">pos</span><span class="special">)</span></code> 709 </p> 710 </td> 711<td> 712 <p> 713 <span class="emphasis"><em>amortized O(1)</em></span> 714 </p> 715 </td> 716<td> 717 <p> 718 <span class="emphasis"><em>amortized O(1)</em></span> 719 </p> 720 </td> 721<td> 722 <p> 723 <span class="emphasis"><em>amortized O(1)</em></span> 724 </p> 725 </td> 726<td> 727 <p> 728 <span class="emphasis"><em>amortized O(1)</em></span> 729 </p> 730 </td> 731</tr> 732<tr> 733<td> 734 <p> 735 <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> 736 <span class="identifier">first</span><span class="special">,</span> 737 <span class="identifier">iterator</span> <span class="identifier">past</span><span class="special">)</span></code> 738 </p> 739 </td> 740<td> 741 <p> 742 <span class="emphasis"><em>O(k)</em></span> 743 </p> 744 </td> 745<td> 746 <p> 747 <span class="emphasis"><em>O(k)</em></span> 748 </p> 749 </td> 750<td> 751 <p> 752 <span class="emphasis"><em>O(k)</em></span> 753 </p> 754 </td> 755<td> 756 <p> 757 <span class="emphasis"><em>O(k)</em></span> 758 </p> 759 </td> 760</tr> 761</tbody> 762</table></div> 763<p> 764 Erasing by a single iterator need only <span class="emphasis"><em><span class="bold"><strong>amortized 765 constant time</strong></span></em></span>. Erasing via a range of iterators 766 <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 767 time</strong></span></em></span> in the number <code class="computeroutput"><span class="identifier">k</span></code> 768 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>. 769 </p> 770</div> 771<p> 772 <span class="emphasis"><em><span class="bold"><strong>See also . . .</strong></span></em></span> 773 </p> 774<div class="informaltable"><table class="table"> 775<colgroup><col></colgroup> 776<thead><tr></tr></thead> 777<tbody> 778<tr><td> 779 <p> 780 <a class="link" href="insertion.html" title="Insertion"><span class="emphasis"><em><span class="bold"><strong>Insertion</strong></span></em></span></a> 781 </p> 782 </td></tr> 783<tr><td> 784 <p> 785 <a class="link" href="subtraction.html" title="Subtraction"><span class="emphasis"><em><span class="bold"><strong>Subtraction</strong></span></em></span></a> 786 </p> 787 </td></tr> 788</tbody> 789</table></div> 790<p> 791 <span class="emphasis"><em><span class="bold"><strong>Back to section . . .</strong></span></em></span> 792 </p> 793<div class="informaltable"><table class="table"> 794<colgroup><col></colgroup> 795<thead><tr></tr></thead> 796<tbody> 797<tr><td> 798 <p> 799 <a class="link" href="../interface/function_synopsis.html#function_synopsis_table"><span class="emphasis"><em><span class="bold"><strong>Function 800 Synopsis</strong></span></em></span></a> 801 </p> 802 </td></tr> 803<tr><td> 804 <p> 805 <a class="link" href="../interface.html" title="Interface"><span class="emphasis"><em><span class="bold"><strong>Interface</strong></span></em></span></a> 806 </p> 807 </td></tr> 808</tbody> 809</table></div> 810</div> 811<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 812<td align="left"></td> 813<td align="right"><div class="copyright-footer">Copyright © 2007-2010 Joachim 814 Faulhaber<br>Copyright © 1999-2006 Cortex Software 815 GmbH<p> 816 Distributed under the Boost Software License, Version 1.0. (See accompanying 817 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>) 818 </p> 819</div></td> 820</tr></table> 821<hr> 822<div class="spirit-nav"> 823<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> 824</div> 825</body> 826</html> 827
