]> git.proxmox.com Git - ceph.git/blame - ceph/src/boost/libs/icl/doc/html/boost_icl/function_reference/subtraction.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 / subtraction.html
CommitLineData
7c673cae
FG		 1<html>
2<head>
3<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
4<title>Subtraction</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="addition.html" title="Addition">
10<link rel="next" href="insertion.html" title="Insertion">
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="addition.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="insertion.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
24</div>
25<div class="section boost_icl_function_reference_subtraction" lang="en">
26<div class="titlepage"><div><div><h3 class="title">
27<a name="boost_icl.function_reference.subtraction"></a><a class="link" href="subtraction.html" title="Subtraction">Subtraction</a>
28</h3></div></div></div>
29<div class="toc"><dl>
30<dt><span class="section"><a href="subtraction.html#boost_icl.function_reference.subtraction.synopsis">Synopsis</a></span></dt>
31<dt><span class="section"><a href="subtraction.html#boost_icl.function_reference.subtraction.functions">Functions</a></span></dt>
32<dt><span class="section"><a href="subtraction.html#boost_icl.function_reference.subtraction.inplace_operators">Inplace
33 operators</a></span></dt>
34<dt><span class="section"><a href="subtraction.html#boost_icl.function_reference.subtraction.infix_operators">Infix
35 operators</a></span></dt>
36<dt><span class="section"><a href="subtraction.html#boost_icl.function_reference.subtraction.subtraction_on_intervals">Subtraction
37 on Intervals</a></span></dt>
38</dl></div>
39<div class="section boost_icl_function_reference_subtraction_synopsis" lang="en">
40<div class="titlepage"><div><div><h4 class="title">
41<a name="boost_icl.function_reference.subtraction.synopsis"></a><a class="link" href="subtraction.html#boost_icl.function_reference.subtraction.synopsis" title="Synopsis">Synopsis</a>
42</h4></div></div></div>
43<div class="informaltable"><table class="table">
44<colgroup>
45<col>
46<col>
47<col>
48<col>
49<col>
50<col>
51</colgroup>
52<thead><tr>
53<th>
54 <p>
55 Subtraction
56 </p>
57 </th>
58<th>
59 <p>
60 intervals
61 </p>
62 </th>
63<th>
64 <p>
65 interval<br> sets
66 </p>
67 </th>
68<th>
69 <p>
70 interval<br> maps
71 </p>
72 </th>
73<th>
74 <p>
75 element<br> sets
76 </p>
77 </th>
78<th>
79 <p>
80 element<br> maps
81 </p>
82 </th>
83</tr></thead>
84<tbody>
85<tr>
86<td>
87 <p>
88 <code class="computeroutput"><span class="identifier">T</span><span class="special">&amp;</span>
89 <span class="identifier">T</span><span class="special">::</span><span class="identifier">subtract</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span></code>
90 </p>
91 </td>
92<td>
93 <p>
94 </p>
95 </td>
96<td>
97 <p>
98 <a class="link" href="../interface/function_synopsis.html#element_type"><span class="bold"><strong>e</strong></span></a>
99 <a class="link" href="../interface/function_synopsis.html#interval_type"><span class="bold"><strong>i</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<td>
109 <p>
110 </p>
111 </td>
112<td>
113 <p>
114 <a class="link" href="../interface/function_synopsis.html#element_mapping_type"><span class="bold"><strong>b</strong></span></a>
115 </p>
116 </td>
117</tr>
118<tr>
119<td>
120 <p>
121 <code class="computeroutput"><span class="identifier">T</span><span class="special">&amp;</span>
122 <span class="identifier">subtract</span><span class="special">(</span><span class="identifier">T</span><span class="special">&amp;,</span>
123 <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span></code>
124 </p>
125 </td>
126<td>
127 <p>
128 </p>
129 </td>
130<td>
131 <p>
132 <a class="link" href="../interface/function_synopsis.html#element_type"><span class="bold"><strong>e</strong></span></a>
133 <a class="link" href="../interface/function_synopsis.html#interval_type"><span class="bold"><strong>i</strong></span></a>
134 </p>
135 </td>
136<td>
137 <p>
138 <a class="link" href="../interface/function_synopsis.html#element_mapping_type"><span class="bold"><strong>b</strong></span></a>
139 <a class="link" href="../interface/function_synopsis.html#interval_mapping_type"><span class="bold"><strong>p</strong></span></a>
140 </p>
141 </td>
142<td>
143 <p>
144 <a class="link" href="../interface/function_synopsis.html#element_type"><span class="bold"><strong>e</strong></span></a>
145 </p>
146 </td>
147<td>
148 <p>
149 <a class="link" href="../interface/function_synopsis.html#element_mapping_type"><span class="bold"><strong>b</strong></span></a>
150 </p>
151 </td>
152</tr>
153<tr>
154<td>
155 <p>
156 <code class="computeroutput"><span class="identifier">T</span><span class="special">&amp;</span>
157 <span class="keyword">operator</span> <span class="special">-=(</span><span class="identifier">T</span><span class="special">&amp;,</span>
158 <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span></code>
159 </p>
160 </td>
161<td>
162 <p>
163 </p>
164 </td>
165<td>
166 <p>
167 <a class="link" href="../interface/function_synopsis.html#element_type"><span class="bold"><strong>e</strong></span></a>
168 <a class="link" href="../interface/function_synopsis.html#interval_type"><span class="bold"><strong>i</strong></span></a>
169 <a class="link" href="../interface/function_synopsis.html#interval_set_types"><span class="bold"><strong>S</strong></span></a>
170 </p>
171 </td>
172<td>
173 <p>
174 <a class="link" href="../interface/function_synopsis.html#element_type"><span class="bold"><strong>e</strong></span></a>
175 <a class="link" href="../interface/function_synopsis.html#interval_type"><span class="bold"><strong>i</strong></span></a>
176 <a class="link" href="../interface/function_synopsis.html#interval_set_types"><span class="bold"><strong>S</strong></span></a>
177 <a class="link" href="../interface/function_synopsis.html#element_mapping_type"><span class="bold"><strong>b</strong></span></a>
178 <a class="link" href="../interface/function_synopsis.html#interval_mapping_type"><span class="bold"><strong>p</strong></span></a>
179 <a class="link" href="../interface/function_synopsis.html#interval_map_types"><span class="bold"><strong>M</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 <a class="link" href="../interface/function_synopsis.html#itl_set_type"><span class="bold"><strong>s</strong></span></a>
186 </p>
187 </td>
188<td>
189 <p>
190 <a class="link" href="../interface/function_synopsis.html#element_mapping_type"><span class="bold"><strong>b</strong></span></a>
191 <a class="link" href="../interface/function_synopsis.html#itl_map_type"><span class="bold"><strong>m</strong></span></a>
192 </p>
193 </td>
194</tr>
195<tr>
196<td>
197 <p>
198 <code class="computeroutput"><span class="identifier">T</span> <span class="keyword">operator</span>
199 <span class="special">-</span> <span class="special">(</span><span class="identifier">T</span><span class="special">,</span>
200 <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span></code>
201 </p>
202 </td>
203<td>
204 <p>
205 </p>
206 </td>
207<td>
208 <p>
209 <a class="link" href="../interface/function_synopsis.html#element_type"><span class="bold"><strong>e</strong></span></a>
210 <a class="link" href="../interface/function_synopsis.html#interval_type"><span class="bold"><strong>i</strong></span></a>
211 <a class="link" href="../interface/function_synopsis.html#interval_set_types"><span class="bold"><strong>S</strong></span></a>
212 </p>
213 </td>
214<td>
215 <p>
216 <a class="link" href="../interface/function_synopsis.html#element_type"><span class="bold"><strong>e</strong></span></a>
217 <a class="link" href="../interface/function_synopsis.html#interval_type"><span class="bold"><strong>i</strong></span></a>
218 <a class="link" href="../interface/function_synopsis.html#interval_set_types"><span class="bold"><strong>S</strong></span></a>
219 <a class="link" href="../interface/function_synopsis.html#element_mapping_type"><span class="bold"><strong>b</strong></span></a>
220 <a class="link" href="../interface/function_synopsis.html#interval_mapping_type"><span class="bold"><strong>p</strong></span></a>
221 <a class="link" href="../interface/function_synopsis.html#interval_map_types"><span class="bold"><strong>M</strong></span></a>
222 </p>
223 </td>
224<td>
225 <p>
226 <a class="link" href="../interface/function_synopsis.html#element_type"><span class="bold"><strong>e</strong></span></a>
227 <a class="link" href="../interface/function_synopsis.html#itl_set_type"><span class="bold"><strong>s</strong></span></a>
228 </p>
229 </td>
230<td>
231 <p>
232 <a class="link" href="../interface/function_synopsis.html#element_mapping_type"><span class="bold"><strong>b</strong></span></a>
233 <a class="link" href="../interface/function_synopsis.html#itl_map_type"><span class="bold"><strong>m</strong></span></a>
234 </p>
235 </td>
236</tr>
237<tr>
238<td>
239 <p>
240 <code class="computeroutput"><span class="identifier">T</span> <span class="identifier">left_subtract</span><span class="special">(</span><span class="identifier">T</span><span class="special">,</span> <span class="keyword">const</span>
241 <span class="identifier">T</span><span class="special">&amp;)</span></code>
242 </p>
243 </td>
244<td>
245 <p>
246 1
247 </p>
248 </td>
249<td>
250 <p>
251 </p>
252 </td>
253<td>
254 <p>
255 </p>
256 </td>
257<td>
258 <p>
259 </p>
260 </td>
261<td>
262 <p>
263 </p>
264 </td>
265</tr>
266<tr>
267<td>
268 <p>
269 <code class="computeroutput"><span class="identifier">T</span> <span class="identifier">right_subtract</span><span class="special">(</span><span class="identifier">T</span><span class="special">,</span> <span class="keyword">const</span>
270 <span class="identifier">T</span><span class="special">&amp;)</span></code>
271 </p>
272 </td>
273<td>
274 <p>
275 1
276 </p>
277 </td>
278<td>
279 <p>
280 </p>
281 </td>
282<td>
283 <p>
284 </p>
285 </td>
286<td>
287 <p>
288 </p>
289 </td>
290<td>
291 <p>
292 </p>
293 </td>
294</tr>
295</tbody>
296</table></div>
297<p>
298 Functions and operators that implement <span class="emphasis"><em><span class="bold"><strong>Subtraction</strong></span></em></span>
299 on <span class="bold"><strong>icl</strong></span> objects are given in the table
300 above.
301 </p>
302<div class="informaltable"><table class="table">
303<colgroup>
304<col>
305<col>
306</colgroup>
307<thead><tr>
308<th>
309 <p>
310 </p>
311 </th>
312<th>
313 <p>
314 Description of Subtraction
315 </p>
316 </th>
317</tr></thead>
318<tbody>
319<tr>
320<td>
321 <p>
322 <code class="computeroutput"><span class="identifier">Sets</span></code>
323 </p>
324 </td>
325<td>
326 <p>
327 Subtraction on Sets implements <span class="emphasis"><em><span class="bold"><strong>set
328 difference</strong></span></em></span>
329 </p>
330 </td>
331</tr>
332<tr>
333<td>
334 <p>
335 <code class="computeroutput"><span class="identifier">Maps</span></code>
336 </p>
337 </td>
338<td>
339 <p>
340 Subtraction on Maps implements a <span class="emphasis"><em><span class="bold"><strong>map
341 difference</strong></span></em></span> function similar to <span class="emphasis"><em>set
342 difference</em></span>. If, on subtraction of an element value pair
343 <code class="computeroutput"><span class="special">(</span><span class="identifier">k</span><span class="special">,</span><span class="identifier">v</span><span class="special">)</span></code> it's key <code class="computeroutput"><span class="identifier">k</span></code>
344 is in the map already, the subtraction function is propagated to
345 the associated value. On the associated value an aggregation is
346 performed, that reverses the effect of the corresponding addition
347 function.
348 </p>
349 <p>
350 Find more on <a class="link" href="../concepts/aggrovering.html" title="Addability, Subtractability and Aggregate on Overlap"><span class="emphasis"><em>subtractability
351 of maps</em></span></a> and related <a class="link" href="../semantics/maps.html" title="Maps"><span class="emphasis"><em>semantic
352 issues</em></span></a> following the links.
353 </p>
354 <p>
355 </p>
356 </td>
357</tr>
358</tbody>
359</table></div>
360</div>
361<div class="section boost_icl_function_reference_subtraction_functions" lang="en">
362<div class="titlepage"><div><div><h4 class="title">
363<a name="boost_icl.function_reference.subtraction.functions"></a><a class="link" href="subtraction.html#boost_icl.function_reference.subtraction.functions" title="Functions">Functions</a>
364</h4></div></div></div>
365<p>
366 The admissible combinations of types for subtraction functions can be summarized
367 in the <span class="emphasis"><em><span class="bold"><strong>overload table</strong></span></em></span>
368 below:
369 </p>
370<p>
371
372</p>
373<pre class="programlisting"><span class="comment">// overload table for T\P| e i b p
374</span><span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">T</span><span class="special">::</span><span class="identifier">subtract</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span> <span class="special">---+--------</span>
375<span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">subtract</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>
376 <span class="identifier">m</span> <span class="special">|</span> <span class="identifier">m</span>
377 <span class="identifier">S</span> <span class="special">|</span> <span class="identifier">S</span> <span class="identifier">S</span>
378 <span class="identifier">M</span> <span class="special">|</span> <span class="identifier">M</span> <span class="identifier">M</span>
379</pre>
380<p>
381 </p>
382<p>
383 The next table contains complexity characteristics for <code class="computeroutput"><span class="identifier">subtract</span></code>.
384 </p>
385<div class="table">
386<a name="id1160128"></a><p class="title"><b>Table&#160;1.24.&#160;Time Complexity for function subtract on icl containers</b></p>
387<div class="table-contents"><table class="table" summary="Time Complexity for function subtract on icl containers">
388<colgroup>
389<col>
390<col>
391<col>
392<col>
393<col>
394</colgroup>
395<thead><tr>
396<th>
397 <p>
398 <code class="computeroutput"><span class="identifier">T</span><span class="special">&amp;</span>
399 <span class="identifier">T</span><span class="special">::</span><span class="identifier">subtract</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span></code><br> <code class="computeroutput"><span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">subtract</span><span class="special">(</span><span class="identifier">T</span><span class="special">&amp;,</span> <span class="keyword">const</span>
400 <span class="identifier">P</span><span class="special">&amp;)</span></code>
401 </p>
402 </th>
403<th>
404 <p>
405 domain<br> type
406 </p>
407 </th>
408<th>
409 <p>
410 interval<br> type
411 </p>
412 </th>
413<th>
414 <p>
415 domain<br> mapping<br> type
416 </p>
417 </th>
418<th>
419 <p>
420 interval<br> mapping<br> type
421 </p>
422 </th>
423</tr></thead>
424<tbody>
425<tr>
426<td>
427 <p>
428 <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>
429 </p>
430 </td>
431<td>
432 <p>
433 <span class="emphasis"><em>O(log n)</em></span>
434 </p>
435 </td>
436<td>
437 <p>
438 </p>
439 </td>
440<td>
441 <p>
442 </p>
443 </td>
444<td>
445 <p>
446 </p>
447 </td>
448</tr>
449<tr>
450<td>
451 <p>
452 <code class="computeroutput"><a class="link" href="../../boost/icl/map.html" title="Class template map">icl::map</a></code>
453 </p>
454 </td>
455<td>
456 <p>
457 <span class="emphasis"><em>O(log n)</em></span>
458 </p>
459 </td>
460<td>
461 <p>
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 </p>
472 </td>
473</tr>
474<tr>
475<td>
476 <p>
477 <code class="computeroutput"><a class="link" href="../../boost/icl/interval_set.html" title="Class template interval_set">interval_sets</a></code>
478 </p>
479 </td>
480<td>
481 <p>
482 <span class="emphasis"><em>O(log n)</em></span>
483 </p>
484 </td>
485<td>
486 <p>
487 <span class="emphasis"><em>amortized<br> O(log n)</em></span>
488 </p>
489 </td>
490<td>
491 <p>
492 </p>
493 </td>
494<td>
495 <p>
496 </p>
497 </td>
498</tr>
499<tr>
500<td>
501 <p>
502 <code class="computeroutput"><a class="link" href="../../boost/icl/interval_map.html" title="Class template interval_map">interval_maps</a></code>
503 </p>
504 </td>
505<td>
506 <p>
507 <span class="emphasis"><em>O(log n)</em></span>
508 </p>
509 </td>
510<td>
511 <p>
512 <span class="emphasis"><em>O(n)</em></span>
513 </p>
514 </td>
515<td>
516 <p>
517 <span class="emphasis"><em>O(log n)</em></span>
518 </p>
519 </td>
520<td>
521 <p>
522 <span class="emphasis"><em>O(n)</em></span>
523 </p>
524 </td>
525</tr>
526</tbody>
527</table></div>
528</div>
529<br class="table-break">
530</div>
531<div class="section boost_icl_function_reference_subtraction_inplace_operators" lang="en">
532<div class="titlepage"><div><div><h4 class="title">
533<a name="boost_icl.function_reference.subtraction.inplace_operators"></a><a class="link" href="subtraction.html#boost_icl.function_reference.subtraction.inplace_operators" title="Inplace operators">Inplace
534 operators</a>
535</h4></div></div></div>
536<p>
537 As presented in the overload tables for <code class="computeroutput"><span class="keyword">operator</span>
538 <span class="special">-=</span></code> more type combinations are provided
539 for subtraction than for addition.
540 </p>
541<p>
542
543</p>
544<pre class="programlisting"><span class="comment">// overload tables for element containers: interval containers:
545</span><span class="identifier">T</span><span class="special">&amp;</span> <span class="keyword">operator</span> <span class="special">-=</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="special">-=</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="special">-=</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>
546 <span class="special">---+--------</span> <span class="special">---+------------</span>
547 <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>
548 <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>
549</pre>
550<p>
551 </p>
552<p>
553 Subtraction provides the <span class="emphasis"><em>reverse</em></span> operation of an addition
554 for these overloads,
555 </p>
556<p>
557
558</p>
559<pre class="programlisting"><span class="comment">// Reverse addition -= | e b s m -= | e i b p S M
560</span> <span class="special">---+--------</span> <span class="special">---+------------</span>
561 <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>
562 <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>
563</pre>
564<p>
565 </p>
566<p>
567 <span class="bold"><strong>and</strong></span> you can erase parts of <code class="computeroutput"><a class="link" href="../../boost/icl/map.html" title="Class template map">icl::maps</a></code> or <code class="computeroutput"><a class="link" href="../../boost/icl/interval_map.html" title="Class template interval_map">interval_maps</a></code>
568 using <span class="emphasis"><em>key values</em></span>, <span class="emphasis"><em>intervals</em></span> or
569 <span class="emphasis"><em>element or interval sets</em></span> using these overloads:
570 </p>
571<p>
572
573</p>
574<pre class="programlisting"><span class="comment">// Erasure by key objects -= | e b s m -= | e i b p S M
575</span> <span class="special">---+--------</span> <span class="special">---+------------</span>
576 <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>
577 <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>
578</pre>
579<p>
580 </p>
581<p>
582 On Sets both function groups fall together as <span class="emphasis"><em><span class="bold"><strong>set
583 difference</strong></span></em></span>.
584 </p>
585<p>
586 Complexity characteristics for inplace subtraction operations are given
587 by the next tables where
588</p>
589<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>
590<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
591</span></pre>
592<p>
593 </p>
594<div class="table">
595<a name="id1161092"></a><p class="title"><b>Table&#160;1.25.&#160;Time Complexity for inplace Subtraction on element
596 containers</b></p>
597<div class="table-contents"><table class="table" summary="Time Complexity for inplace Subtraction on element
598 containers">
599<colgroup>
600<col>
601<col>
602<col>
603<col>
604<col>
605</colgroup>
606<thead><tr>
607<th>
608 <p>
609 <code class="computeroutput"><span class="identifier">T</span><span class="special">&amp;</span>
610 <span class="keyword">operator</span> <span class="special">-=</span>
611 <span class="special">(</span><span class="identifier">T</span><span class="special">&amp;,</span> <span class="keyword">const</span>
612 <span class="identifier">P</span><span class="special">&amp;)</span></code>
613 </p>
614 </th>
615<th>
616 <p>
617 domain<br> type
618 </p>
619 </th>
620<th>
621 <p>
622 domain<br> mapping<br> type
623 </p>
624 </th>
625<th>
626 <p>
627 std::set
628 </p>
629 </th>
630<th>
631 <p>
632 icl::map
633 </p>
634 </th>
635</tr></thead>
636<tbody>
637<tr>
638<td>
639 <p>
640 <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>
641 </p>
642 </td>
643<td>
644 <p>
645 <span class="emphasis"><em>O(log n)</em></span>
646 </p>
647 </td>
648<td>
649 <p>
650 </p>
651 </td>
652<td>
653 <p>
654 <span class="emphasis"><em>O(m log n)</em></span>
655 </p>
656 </td>
657<td>
658 <p>
659 </p>
660 </td>
661</tr>
662<tr>
663<td>
664 <p>
665 <code class="computeroutput"><a class="link" href="../../boost/icl/map.html" title="Class template map">icl::map</a></code>
666 </p>
667 </td>
668<td>
669 <p>
670 <span class="emphasis"><em>O(log n)</em></span>
671 </p>
672 </td>
673<td>
674 <p>
675 <span class="emphasis"><em>O(log n)</em></span>
676 </p>
677 </td>
678<td>
679 <p>
680 <span class="emphasis"><em>O(m log n)</em></span>
681 </p>
682 </td>
683<td>
684 <p>
685 <span class="emphasis"><em>O(m log n)</em></span>
686 </p>
687 </td>
688</tr>
689</tbody>
690</table></div>
691</div>
692<br class="table-break"><div class="table">
693<a name="id1161316"></a><p class="title"><b>Table&#160;1.26.&#160;Time Complexity for inplace Subtraction
694 on interval containers</b></p>
695<div class="table-contents"><table class="table" summary="Time Complexity for inplace Subtraction
696 on interval containers">
697<colgroup>
698<col>
699<col>
700<col>
701<col>
702<col>
703<col>
704<col>
705</colgroup>
706<thead><tr>
707<th>
708 <p>
709 <code class="computeroutput"><span class="identifier">T</span><span class="special">&amp;</span>
710 <span class="keyword">operator</span> <span class="special">-=</span>
711 <span class="special">(</span><span class="identifier">T</span><span class="special">&amp;,</span> <span class="keyword">const</span>
712 <span class="identifier">P</span><span class="special">&amp;)</span></code>
713 </p>
714 </th>
715<th>
716 <p>
717 domain<br> type
718 </p>
719 </th>
720<th>
721 <p>
722 interval<br> type
723 </p>
724 </th>
725<th>
726 <p>
727 domain<br> mapping<br> type
728 </p>
729 </th>
730<th>
731 <p>
732 interval<br> mapping<br> type
733 </p>
734 </th>
735<th>
736 <p>
737 interval<br> sets
738 </p>
739 </th>
740<th>
741 <p>
742 interval<br> maps
743 </p>
744 </th>
745</tr></thead>
746<tbody>
747<tr>
748<td>
749 <p>
750 interval_sets
751 </p>
752 </td>
753<td>
754 <p>
755 <span class="emphasis"><em>O(log n)</em></span>
756 </p>
757 </td>
758<td>
759 <p>
760 <span class="emphasis"><em>amortized<br> O(log n)</em></span>
761 </p>
762 </td>
763<td>
764 <p>
765 </p>
766 </td>
767<td>
768 <p>
769 </p>
770 </td>
771<td>
772 <p>
773 <span class="emphasis"><em>O(m log(n+m))</em></span>
774 </p>
775 </td>
776<td>
777 <p>
778 </p>
779 </td>
780</tr>
781<tr>
782<td>
783 <p>
784 interval_maps
785 </p>
786 </td>
787<td>
788 <p>
789 <span class="emphasis"><em>O(log n)</em></span>
790 </p>
791 </td>
792<td>
793 <p>
794 <span class="emphasis"><em>amortized<br> O(log n)</em></span>
795 </p>
796 </td>
797<td>
798 <p>
799 <span class="emphasis"><em>O(log n)</em></span>
800 </p>
801 </td>
802<td>
803 <p>
804 <span class="emphasis"><em>O(n)</em></span>
805 </p>
806 </td>
807<td>
808 <p>
809 <span class="emphasis"><em>O(m log(n+m))</em></span>
810 </p>
811 </td>
812<td>
813 <p>
814 <span class="emphasis"><em>O(m log(n+m))</em></span>
815 </p>
816 </td>
817</tr>
818</tbody>
819</table></div>
820</div>
821<br class="table-break">
822</div>
823<div class="section boost_icl_function_reference_subtraction_infix_operators" lang="en">
824<div class="titlepage"><div><div><h4 class="title">
825<a name="boost_icl.function_reference.subtraction.infix_operators"></a><a class="link" href="subtraction.html#boost_icl.function_reference.subtraction.infix_operators" title="Infix operators">Infix
826 operators</a>
827</h4></div></div></div>
828<p>
829 The admissible overloads for the infix <span class="emphasis"><em>subtraction</em></span>
830 <code class="computeroutput"><span class="keyword">operator</span> <span class="special">-</span></code>
831 which is a non commutative operation is given by the next overload table.
832 </p>
833<p>
834
835</p>
836<pre class="programlisting"><span class="comment">// overload tables for - | e b s m - | e i b p S M
837</span><span class="identifier">T</span> <span class="keyword">operator</span> <span class="special">-</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">&amp;)</span> <span class="special">---+--------</span> <span class="special">---+------------</span>
838 <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>
839 <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>
840</pre>
841<p>
842 </p>
843</div>
844<div class="section boost_icl_function_reference_subtraction_subtraction_on_intervals" lang="en">
845<div class="titlepage"><div><div><h4 class="title">
846<a name="boost_icl.function_reference.subtraction.subtraction_on_intervals"></a><a class="link" href="subtraction.html#boost_icl.function_reference.subtraction.subtraction_on_intervals" title="Subtraction on Intervals">Subtraction
847 on Intervals</a>
848</h4></div></div></div>
849<div class="informaltable"><table class="table">
850<colgroup>
851<col>
852<col>
853<col>
854</colgroup>
855<thead><tr>
856<th>
857 <p>
858 <span class="emphasis"><em><span class="bold"><strong>Subtraction</strong></span></em></span>
859 </p>
860 </th>
861<th>
862 <p>
863 Types
864 </p>
865 </th>
866<th>
867 <p>
868 Description
869 </p>
870 </th>
871</tr></thead>
872<tbody>
873<tr>
874<td>
875 <p>
876 <code class="computeroutput"><span class="identifier">T</span> <span class="identifier">left_subtract</span><span class="special">(</span><span class="identifier">T</span>
877 <span class="identifier">right</span><span class="special">,</span>
878 <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">left_minuend</span><span class="special">)</span></code>
879 </p>
880 </td>
881<td>
882 <p>
883 <a class="link" href="../interface/function_synopsis.html#interval_type"><span class="bold"><strong>i</strong></span></a>
884 </p>
885 </td>
886<td>
887 <p>
888 subtract <code class="computeroutput"><span class="identifier">left_minuend</span></code>
889 from the interval <code class="computeroutput"><span class="identifier">right</span></code>
890 on it's left side.
891</p>
892<pre xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" class="table-programlisting"><span class="identifier">right_over</span> <span class="special">=</span> <span class="identifier">left_subtract</span><span class="special">(</span><span class="identifier">right</span><span class="special">,</span> <span class="identifier">left_minuend</span><span class="special">);</span>
893<span class="special">...</span> <span class="identifier">d</span><span class="special">)</span> <span class="special">:</span> <span class="identifier">right</span>
894<span class="special">...</span> <span class="identifier">c</span><span class="special">)</span> <span class="special">:</span> <span class="identifier">left_minuend</span>
895 <span class="special">[</span><span class="identifier">c</span> <span class="identifier">d</span><span class="special">)</span> <span class="special">:</span> <span class="identifier">right_over</span>
896</pre>
897<p>
898 </p>
899 </td>
900</tr>
901<tr>
902<td>
903 <p>
904 <code class="computeroutput"><span class="identifier">T</span> <span class="identifier">right_subtract</span><span class="special">(</span><span class="identifier">T</span>
905 <span class="identifier">left</span><span class="special">,</span>
906 <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">right_minuend</span><span class="special">)</span></code>
907 </p>
908 </td>
909<td>
910 <p>
911 <a class="link" href="../interface/function_synopsis.html#interval_type"><span class="bold"><strong>i</strong></span></a>
912 </p>
913 </td>
914<td>
915 <p>
916 subtract <code class="computeroutput"><span class="identifier">right_minuend</span></code>
917 from the interval <code class="computeroutput"><span class="identifier">left</span></code>
918 on it's right side.
919</p>
920<pre xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" class="table-programlisting"><span class="identifier">left_over</span> <span class="special">=</span> <span class="identifier">right_subtract</span><span class="special">(</span><span class="identifier">left</span><span class="special">,</span> <span class="identifier">right_minuend</span><span class="special">);</span>
921<span class="special">[</span><span class="identifier">a</span> <span class="special">...</span> <span class="special">:</span> <span class="identifier">left</span>
922 <span class="special">[</span><span class="identifier">b</span> <span class="special">...</span> <span class="special">:</span> <span class="identifier">right_minuend</span>
923<span class="special">[</span><span class="identifier">a</span> <span class="identifier">b</span><span class="special">)</span> <span class="special">:</span> <span class="identifier">left_over</span>
924</pre>
925<p>
926 </p>
927 </td>
928</tr>
929</tbody>
930</table></div>
931</div>
932<p>
933 <span class="emphasis"><em><span class="bold"><strong>See also . . .</strong></span></em></span>
934 </p>
935<div class="informaltable"><table class="table">
936<colgroup><col></colgroup>
937<thead><tr></tr></thead>
938<tbody>
939<tr><td>
940 <p>
941 <a class="link" href="addition.html" title="Addition"><span class="emphasis"><em><span class="bold"><strong>Addition</strong></span></em></span></a>
942 </p>
943 </td></tr>
944<tr><td>
945 <p>
946 <a class="link" href="erasure.html" title="Erasure"><span class="emphasis"><em><span class="bold"><strong>Erasure</strong></span></em></span></a>
947 </p>
948 </td></tr>
949</tbody>
950</table></div>
951<p>
952 <span class="emphasis"><em><span class="bold"><strong>Back to section . . .</strong></span></em></span>
953 </p>
954<div class="informaltable"><table class="table">
955<colgroup><col></colgroup>
956<thead><tr></tr></thead>
957<tbody>
958<tr><td>
959 <p>
960 <a class="link" href="../interface/function_synopsis.html#function_synopsis_table"><span class="emphasis"><em><span class="bold"><strong>Function
961 Synopsis</strong></span></em></span></a>
962 </p>
963 </td></tr>
964<tr><td>
965 <p>
966 <a class="link" href="../interface.html" title="Interface"><span class="emphasis"><em><span class="bold"><strong>Interface</strong></span></em></span></a>
967 </p>
968 </td></tr>
969</tbody>
970</table></div>
971</div>
972<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
973<td align="left"></td>
974<td align="right"><div class="copyright-footer">Copyright &#169; 2007 -2010 Joachim Faulhaber<br>Copyright &#169; 1999 -2006 Cortex Software GmbH<p>
975 Distributed under the Boost Software License, Version 1.0. (See accompanying
976 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>)
977 </p>
978</div></td>
979</tr></table>
980<hr>
981<div class="spirit-nav">
982<a accesskey="p" href="addition.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="insertion.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
983</div>
984</body>
985</html>
Ceph