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