]> git.proxmox.com Git - ceph.git/blame - ceph/src/boost/libs/icl/doc/html/boost_icl/function_reference/insertion.html
projects / ceph.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
bump version to 12.2.2-pve1
[ceph.git] / ceph / src / boost / libs / icl / doc / html / boost_icl / function_reference / insertion.html
CommitLineData
7c673cae
FG		 1<html>
2<head>
3<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
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.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="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 boost_icl_function_reference_insertion" lang="en">
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>
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 boost_icl_function_reference_insertion_synopsis" lang="en">
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">&amp;)</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">&amp;,</span> <span class="keyword">const</span>
109 <span class="identifier">P</span><span class="special">&amp;)</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">&amp;)</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">&amp;,</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">&amp;)</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">&amp;</span>
197 <span class="identifier">insert</span><span class="special">(</span><span class="identifier">T</span><span class="special">&amp;,</span>
198 <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</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">&amp;</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">&amp;)</span></code>
233 </p>
234 </td>
235<td>
236 <p>
237 </p>
238 </td>
239<td>
240 <p>
241 <a class="link" href="../interface/function_synopsis.html#element_mapping_type"><span class="bold"><strong>b</strong></span></a>
242 <a class="link" href="../interface/function_synopsis.html#interval_mapping_type"><span class="bold"><strong>p</strong></span></a>
243 </p>
244 </td>
245<td>
246 <p>
247 </p>
248 </td>
249<td>
250 <p>
251 1
252 </p>
253 </td>
254</tr>
255<tr>
256<td>
257 <p>
258 <code class="computeroutput"><span class="identifier">T</span><span class="special">&amp;</span>
259 <span class="identifier">set_at</span><span class="special">(</span><span class="identifier">T</span><span class="special">&amp;,</span>
260 <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span></code>
261 </p>
262 </td>
263<td>
264 <p>
265 </p>
266 </td>
267<td>
268 <p>
269 <a class="link" href="../interface/function_synopsis.html#element_mapping_type"><span class="bold"><strong>b</strong></span></a>
270 <a class="link" href="../interface/function_synopsis.html#interval_mapping_type"><span class="bold"><strong>p</strong></span></a>
271 </p>
272 </td>
273<td>
274 <p>
275 </p>
276 </td>
277<td>
278 <p>
279 1
280 </p>
281 </td>
282</tr>
283</tbody>
284</table></div>
285<a name="boost_icl.function_reference.insertion.synopsis.insertion"></a><h6>
286<a name="id1163803"></a>
287 <a class="link" href="insertion.html#boost_icl.function_reference.insertion.synopsis.insertion">Insertion</a>
288 </h6>
289<p>
290 The effects of <span class="emphasis"><em><span class="bold"><strong>insertion</strong></span></em></span>
291 implemented by <code class="computeroutput"><span class="identifier">insert</span></code> and
292 <span class="emphasis"><em><span class="bold"><strong>addition</strong></span></em></span> implemented
293 by <code class="computeroutput"><span class="identifier">add</span></code> and <code class="computeroutput"><span class="keyword">operator</span> <span class="special">+=</span></code>
294 are identical for all Set-types of the <span class="bold"><strong>icl</strong></span>.
295 </p>
296<p>
297 For Map-types, <code class="computeroutput"><span class="identifier">insert</span></code> provides
298 the <span class="bold"><strong>stl</strong></span> semantics of insertion in contrast
299 to <code class="computeroutput"><span class="identifier">add</span></code> and <code class="computeroutput"><span class="keyword">operator</span> <span class="special">+=</span></code>,
300 that implement a generalized addition, that performs aggregations if key
301 values collide or key intervals overlap. <code class="computeroutput"><span class="identifier">insert</span></code>
302 on Maps does not alter a maps content at the points, where the keys of
303 the object to inserted overlap or collide with keys that are already in
304 the map.
305 </p>
306<a name="boost_icl.function_reference.insertion.synopsis.setting_values"></a><h6>
307<a name="id1163910"></a>
308 <a class="link" href="insertion.html#boost_icl.function_reference.insertion.synopsis.setting_values">Setting
309 values</a>
310 </h6>
311<p>
312 Overwriting values using <code class="computeroutput"><span class="keyword">operator</span><span class="special">[]</span></code> like in
313</p>
314<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>
315</pre>
316<p>
317 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>
318 because an <code class="computeroutput"><span class="keyword">operator</span><span class="special">[]</span></code>
319 is not implemented for them. As a substitute a function <code class="computeroutput"><span class="identifier">T</span><span class="special">&amp;</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">&amp;)</span></code>
320 can be used to achieve the same effect:
321</p>
322<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>
323</pre>
324<p>
325 </p>
326</div>
327<div class="section boost_icl_function_reference_insertion_insertion" lang="en">
328<div class="titlepage"><div><div><h4 class="title">
329<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>
330</h4></div></div></div>
331<p>
332
333</p>
334<pre class="programlisting"><span class="comment">// overload table for functions T\P| e i b p
335</span><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">&amp;)</span> <span class="special">---+--------</span>
336<span class="identifier">V</span> <span class="identifier">insert</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>
337 <span class="identifier">m</span> <span class="special">|</span> <span class="identifier">m</span>
338 <span class="identifier">S</span> <span class="special">|</span> <span class="identifier">S</span>
339 <span class="identifier">M</span> <span class="special">|</span> <span class="identifier">M</span>
340</pre>
341<p>
342 </p>
343<div class="table">
344<a name="id1164217"></a><p class="title"><b>Table&#160;1.27.&#160;Time Complexity for member function insert on
345 icl containers</b></p>
346<div class="table-contents"><table class="table" summary="Time Complexity for member function insert on
347 icl containers">
348<colgroup>
349<col>
350<col>
351<col>
352<col>
353<col>
354</colgroup>
355<thead><tr>
356<th>
357 <p>
358 <code class="computeroutput"><span class="identifier">T</span><span class="special">&amp;</span>
359 <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">&amp;)</span></code>
360 </p>
361 </th>
362<th>
363 <p>
364 domain<br> type
365 </p>
366 </th>
367<th>
368 <p>
369 interval<br> type
370 </p>
371 </th>
372<th>
373 <p>
374 domain<br> mapping<br> type
375 </p>
376 </th>
377<th>
378 <p>
379 interval<br> mapping<br> type
380 </p>
381 </th>
382</tr></thead>
383<tbody>
384<tr>
385<td>
386 <p>
387 <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>
388 </p>
389 </td>
390<td>
391 <p>
392 <span class="emphasis"><em>O(log n)</em></span>
393 </p>
394 </td>
395<td>
396 <p>
397 </p>
398 </td>
399<td>
400 <p>
401 </p>
402 </td>
403<td>
404 <p>
405 </p>
406 </td>
407</tr>
408<tr>
409<td>
410 <p>
411 <code class="computeroutput"><a class="link" href="../../boost/icl/map.html" title="Class template map">icl::map</a></code>
412 </p>
413 </td>
414<td>
415 <p>
416 </p>
417 </td>
418<td>
419 <p>
420 </p>
421 </td>
422<td>
423 <p>
424 <span class="emphasis"><em>O(log n)</em></span>
425 </p>
426 </td>
427<td>
428 <p>
429 </p>
430 </td>
431</tr>
432<tr>
433<td>
434 <p>
435 <code class="computeroutput"><a class="link" href="../../boost/icl/interval_set.html" title="Class template interval_set">interval_set</a></code><br>
436 <code class="computeroutput"><a class="link" href="../../boost/icl/separate_interval_set.html" title="Class template separate_interval_set">separate_interval_set</a></code>
437 </p>
438 </td>
439<td>
440 <p>
441 <span class="emphasis"><em>O(log n)</em></span>
442 </p>
443 </td>
444<td>
445 <p>
446 <span class="emphasis"><em>amortized<br> O(log n)</em></span>
447 </p>
448 </td>
449<td>
450 <p>
451 </p>
452 </td>
453<td>
454 <p>
455 </p>
456 </td>
457</tr>
458<tr>
459<td>
460 <p>
461 <code class="computeroutput"><a class="link" href="../../boost/icl/split_interval_set.html" title="Class template split_interval_set">split_interval_set</a></code>
462 </p>
463 </td>
464<td>
465 <p>
466 <span class="emphasis"><em>O(log n)</em></span>
467 </p>
468 </td>
469<td>
470 <p>
471 <span class="emphasis"><em>O(n)</em></span>
472 </p>
473 </td>
474<td>
475 <p>
476 </p>
477 </td>
478<td>
479 <p>
480 </p>
481 </td>
482</tr>
483<tr>
484<td>
485 <p>
486 <code class="computeroutput"><a class="link" href="../../boost/icl/interval_map.html" title="Class template interval_map">interval_map</a></code><br>
487 <code class="computeroutput"><a class="link" href="../../boost/icl/split_interval_map.html" title="Class template split_interval_map">split_interval_map</a></code>
488 </p>
489 </td>
490<td>
491 <p>
492 </p>
493 </td>
494<td>
495 <p>
496 </p>
497 </td>
498<td>
499 <p>
500 <span class="emphasis"><em>O(log n)</em></span>
501 </p>
502 </td>
503<td>
504 <p>
505 <span class="emphasis"><em>O(n)</em></span>
506 </p>
507 </td>
508</tr>
509</tbody>
510</table></div>
511</div>
512<br class="table-break"><p>
513
514</p>
515<pre class="programlisting"><span class="comment">// overload tables for function element containers: interval containers:
516</span><span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">insert</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>
517 <span class="special">---+--------</span> <span class="special">---+------------</span>
518 <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>
519 <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>
520</pre>
521<p>
522 </p>
523<div class="table">
524<a name="id1165381"></a><p class="title"><b>Table&#160;1.28.&#160;Time Complexity for inplace insertion on element
525 containers</b></p>
526<div class="table-contents"><table class="table" summary="Time Complexity for inplace insertion on element
527 containers">
528<colgroup>
529<col>
530<col>
531<col>
532<col>
533<col>
534</colgroup>
535<thead><tr>
536<th>
537 <p>
538 <code class="computeroutput"><span class="identifier">T</span><span class="special">&amp;</span>
539 <span class="identifier">insert</span><span class="special">(</span><span class="identifier">T</span><span class="special">&amp;</span>
540 <span class="identifier">y</span><span class="special">,</span>
541 <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>
542 </p>
543 </th>
544<th>
545 <p>
546 domain<br> type
547 </p>
548 </th>
549<th>
550 <p>
551 domain<br> mapping<br> type
552 </p>
553 </th>
554<th>
555 <p>
556 interval<br> sets
557 </p>
558 </th>
559<th>
560 <p>
561 interval<br> maps
562 </p>
563 </th>
564</tr></thead>
565<tbody>
566<tr>
567<td>
568 <p>
569 <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>
570 </p>
571 </td>
572<td>
573 <p>
574 <span class="emphasis"><em>O(log n)</em></span>
575 </p>
576 </td>
577<td>
578 <p>
579 </p>
580 </td>
581<td>
582 <p>
583 <span class="emphasis"><em>O(m)</em></span>
584 </p>
585 </td>
586<td>
587 <p>
588 </p>
589 </td>
590</tr>
591<tr>
592<td>
593 <p>
594 <code class="computeroutput"><a class="link" href="../../boost/icl/map.html" title="Class template map">icl::map</a></code>
595 </p>
596 </td>
597<td>
598 <p>
599 </p>
600 </td>
601<td>
602 <p>
603 <span class="emphasis"><em>O(log n)</em></span>
604 </p>
605 </td>
606<td>
607 <p>
608 </p>
609 </td>
610<td>
611 <p>
612 <span class="emphasis"><em>O(m)</em></span>
613 </p>
614 </td>
615</tr>
616</tbody>
617</table></div>
618</div>
619<br class="table-break"><p>
620 Time complexity characteristics of inplace insertion for interval containers
621 is given by this table.
622 </p>
623<div class="table">
624<a name="id1165618"></a><p class="title"><b>Table&#160;1.29.&#160;Time Complexity for inplace insertion on interval
625 containers</b></p>
626<div class="table-contents"><table class="table" summary="Time Complexity for inplace insertion on interval
627 containers">
628<colgroup>
629<col>
630<col>
631<col>
632<col>
633<col>
634<col>
635<col>
636<col>
637</colgroup>
638<thead><tr>
639<th>
640 <p>
641 <code class="computeroutput"><span class="identifier">T</span><span class="special">&amp;</span>
642 <span class="identifier">insert</span><span class="special">(</span><span class="identifier">T</span><span class="special">&amp;</span>
643 <span class="identifier">y</span><span class="special">,</span>
644 <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>
645 </p>
646 </th>
647<th>
648 <p>
649 </p>
650 </th>
651<th>
652 <p>
653 domain<br> type
654 </p>
655 </th>
656<th>
657 <p>
658 interval<br> type
659 </p>
660 </th>
661<th>
662 <p>
663 domain<br> mapping<br> type
664 </p>
665 </th>
666<th>
667 <p>
668 interval<br> mapping<br> type
669 </p>
670 </th>
671<th>
672 <p>
673 interval<br> sets
674 </p>
675 </th>
676<th>
677 <p>
678 interval<br> maps
679 </p>
680 </th>
681</tr></thead>
682<tbody>
683<tr>
684<td>
685 <p>
686 interval_sets
687 </p>
688 </td>
689<td>
690 <p>
691 <code class="computeroutput"><a class="link" href="../../boost/icl/interval_set.html" title="Class template interval_set">interval_set</a></code><br>
692 <code class="computeroutput"><a class="link" href="../../boost/icl/separate_interval_set.html" title="Class template separate_interval_set">separate_interval_set</a></code>
693 </p>
694 </td>
695<td>
696 <p>
697 <span class="emphasis"><em>O(log n)</em></span>
698 </p>
699 </td>
700<td>
701 <p>
702 <span class="emphasis"><em>amortized<br> O(log n)</em></span>
703 </p>
704 </td>
705<td>
706 <p>
707 </p>
708 </td>
709<td>
710 <p>
711 </p>
712 </td>
713<td>
714 <p>
715 <span class="emphasis"><em>O(m log(n+m))</em></span>
716 </p>
717 </td>
718<td>
719 <p>
720 </p>
721 </td>
722</tr>
723<tr>
724<td>
725 <p>
726 </p>
727 </td>
728<td>
729 <p>
730 <code class="computeroutput"><a class="link" href="../../boost/icl/split_interval_set.html" title="Class template split_interval_set">split_interval_set</a></code>
731 </p>
732 </td>
733<td>
734 <p>
735 <span class="emphasis"><em>O(log n)</em></span>
736 </p>
737 </td>
738<td>
739 <p>
740 <span class="emphasis"><em>O(n)</em></span>
741 </p>
742 </td>
743<td>
744 <p>
745 </p>
746 </td>
747<td>
748 <p>
749 </p>
750 </td>
751<td>
752 <p>
753 <span class="emphasis"><em>O(m log(n+m))</em></span>
754 </p>
755 </td>
756<td>
757 <p>
758 </p>
759 </td>
760</tr>
761<tr>
762<td>
763 <p>
764 interval_maps
765 </p>
766 </td>
767<td>
768 <p>
769 </p>
770 </td>
771<td>
772 <p>
773 </p>
774 </td>
775<td>
776 <p>
777 </p>
778 </td>
779<td>
780 <p>
781 <span class="emphasis"><em>O(log n)</em></span>
782 </p>
783 </td>
784<td>
785 <p>
786 <span class="emphasis"><em>O(n)</em></span>
787 </p>
788 </td>
789<td>
790 <p>
791 </p>
792 </td>
793<td>
794 <p>
795 <span class="emphasis"><em>O(m log(n+m))</em></span>
796 </p>
797 </td>
798</tr>
799</tbody>
800</table></div>
801</div>
802<br class="table-break"><a name="boost_icl.function_reference.insertion.insertion.hinted_insertion"></a><h5>
803<a name="id1165986"></a>
804 <a class="link" href="insertion.html#boost_icl.function_reference.insertion.insertion.hinted_insertion">Hinted
805 insertion</a>
806 </h5>
807<p>
808 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">&amp;</span> <span class="identifier">addend</span><span class="special">)</span></code>
809 allows for an insertion in <span class="emphasis"><em><span class="bold"><strong>constant time</strong></span></em></span>,
810 if <code class="computeroutput"><span class="identifier">addend</span></code> can be inserted
811 right after iterator <code class="computeroutput"><span class="identifier">prior</span></code>
812 without collision. If this is not possible the complexity characteristics
813 are as stated for the non hinted insertion above. Hinted insertion is available
814 for these combinations of types:
815</p>
816<pre class="programlisting"><span class="comment">// overload table for insertion with hint T\P| e i b p
817</span><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">&amp;)</span> <span class="special">---+--------</span>
818<span class="identifier">J</span> <span class="identifier">insert</span><span class="special">(</span><span class="identifier">T</span><span class="special">&amp;,</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">&amp;)</span> <span class="identifier">s</span> <span class="special">|</span> <span class="identifier">s</span>
819 <span class="identifier">m</span> <span class="special">|</span> <span class="identifier">m</span>
820 <span class="identifier">S</span> <span class="special">|</span> <span class="identifier">S</span>
821 <span class="identifier">M</span> <span class="special">|</span> <span class="identifier">M</span>
822</pre>
823<p>
824 </p>
825</div>
826<div class="section boost_icl_function_reference_insertion_setting_values" lang="en">
827<div class="titlepage"><div><div><h4 class="title">
828<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
829 values</a>
830</h4></div></div></div>
831<p>
832
833</p>
834<pre class="programlisting"><span class="comment">// overload table for member function T\P| b p
835</span><span class="identifier">T</span><span class="special">&amp;</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">&amp;)</span> <span class="special">---+----</span>
836<span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">set_at</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">m</span> <span class="special">|</span> <span class="identifier">m</span>
837 <span class="identifier">M</span> <span class="special">|</span> <span class="identifier">M</span>
838</pre>
839<p>
840 </p>
841<div class="table">
842<a name="id1166368"></a><p class="title"><b>Table&#160;1.30.&#160;Time Complexity for member function `set`</b></p>
843<div class="table-contents"><table class="table" summary="Time Complexity for member function `set`">
844<colgroup>
845<col>
846<col>
847<col>
848</colgroup>
849<thead><tr>
850<th>
851 <p>
852 <code class="computeroutput"><span class="identifier">T</span><span class="special">&amp;</span>
853 <span class="identifier">set</span><span class="special">(</span><span class="identifier">T</span><span class="special">&amp;,</span>
854 <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span></code>
855 </p>
856 </th>
857<th>
858 <p>
859 domain_mapping_type
860 </p>
861 </th>
862<th>
863 <p>
864 interval_mapping_type
865 </p>
866 </th>
867</tr></thead>
868<tbody>
869<tr>
870<td>
871 <p>
872 icl::map
873 </p>
874 </td>
875<td>
876 <p>
877 <span class="emphasis"><em>O(log n)</em></span>
878 </p>
879 </td>
880<td>
881 <p>
882 </p>
883 </td>
884</tr>
885<tr>
886<td>
887 <p>
888 interval_maps
889 </p>
890 </td>
891<td>
892 <p>
893 </p>
894 </td>
895<td>
896 <p>
897 <span class="emphasis"><em>amortized<br> O(log n)</em></span>
898 </p>
899 </td>
900</tr>
901</tbody>
902</table></div>
903</div>
904<br class="table-break">
905</div>
906<p>
907 <span class="emphasis"><em><span class="bold"><strong>See also . . .</strong></span></em></span>
908 </p>
909<div class="informaltable"><table class="table">
910<colgroup><col></colgroup>
911<thead><tr></tr></thead>
912<tbody>
913<tr><td>
914 <p>
915 <a class="link" href="addition.html" title="Addition"><span class="emphasis"><em><span class="bold"><strong>Erasure</strong></span></em></span></a>
916 </p>
917 </td></tr>
918<tr><td>
919 <p>
920 <a class="link" href="addition.html" title="Addition"><span class="emphasis"><em><span class="bold"><strong>Addition</strong></span></em></span></a>
921 </p>
922 </td></tr>
923</tbody>
924</table></div>
925<p>
926 <span class="emphasis"><em><span class="bold"><strong>Back to section . . .</strong></span></em></span>
927 </p>
928<div class="informaltable"><table class="table">
929<colgroup><col></colgroup>
930<thead><tr></tr></thead>
931<tbody>
932<tr><td>
933 <p>
934 <a class="link" href="../interface/function_synopsis.html#function_synopsis_table"><span class="emphasis"><em><span class="bold"><strong>Function
935 Synopsis</strong></span></em></span></a>
936 </p>
937 </td></tr>
938<tr><td>
939 <p>
940 <a class="link" href="../interface.html" title="Interface"><span class="emphasis"><em><span class="bold"><strong>Interface</strong></span></em></span></a>
941 </p>
942 </td></tr>
943</tbody>
944</table></div>
945</div>
946<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
947<td align="left"></td>
948<td align="right"><div class="copyright-footer">Copyright &#169; 2007 -2010 Joachim Faulhaber<br>Copyright &#169; 1999 -2006 Cortex Software GmbH<p>
949 Distributed under the Boost Software License, Version 1.0. (See accompanying
950 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>)
951 </p>
952</div></td>
953</tr></table>
954<hr>
955<div class="spirit-nav">
956<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>
957</div>
958</body>
959</html>
Ceph