1[/ 2 Copyright (c) 2008-2010 Joachim Faulhaber 3 4 Distributed under the Boost Software License, Version 1.0. 5 (See accompanying file LICENSE_1_0.txt or copy at 6 http://www.boost.org/LICENSE_1_0.txt) 7] 8 9 10[/ //= Erasure ===================================================================] 11[section Erasure] 12 13[section Synopsis][/ Erasure] 14 15[table 16[[['*Erasure*]] [__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__] ] 17[[`T& T::erase(const P&)`] [__ei ] [__ei __bp] [__e] [__bp] ] 18[[`T& erase(T&, const P&)`] [__eiS] [__eiS __bpM] [__es] [__bm] ] 19[[`void T::erase(iterator)`] [1] [1] [1] [1] ] 20[[`void T::erase(iterator,iterator)`] [1] [1] [1] [1] ] 21] 22 23[h5 Erasure] 24 25The effects of ['*erasure*] implemented by `erase` and ['*subtraction*] 26implemented by `subtract` and `operator -=` are identical for all Set-types of 27the *icl*. 28 29For Map-types, `erase` provides the *stl* semantics of erasure in 30contrast to `subtract` and `operator -=`, that implement a generalized subtraction, 31that performs inverse aggregations if key values collide or key intervals overlap. 32 33Using iterators it is possible to erase objects or ranges of 34objects the iterator is pointing at from icl Sets and Maps. 35 36[endsect][/ Synopsis Erasure] 37 38 39[section Erasure of Objects] 40 41 42`` 43/* overload table for */ T\P| e i b p 44T& T::erase(const P&) ---+-------- 45T& erase(T&, const P&) s | s 46 m | m 47 S | S S 48 M | M M 49`` 50 51The next table contains complexity characteristics for the `erase` function on elements and segments. 52 53[table Time Complexity for erasure of elements and segments on icl containers 54[[`T& T::erase(const P&)`\n 55 `T& erase(T&, const P&)`] [__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__]] 56[[__icl_set__] [__Olgn__] [] [] [] ] 57[[__icl_map__] [__Olgn__] [] [__Olgn__] [] ] 58[[__itv_sets__] [__Olgn__] [__a_Olgn__] [] [] ] 59[[__itv_maps__] [__Olgn__] [__On__] [__Olgn__] [__On__] ] 60] 61 62 63As presented in the overload tables for inplace function `erase` below, 64more type combinations are available for /erasure/ than for 65/insertion/. 66 67`` 68// overload tables for function element containers: interval containers: 69T& erase(T&, const P&) T\P| e b s m T\P| e i b p S M 70 ---+-------- ---+------------ 71 s | s s S | S S S 72 m | m m m m M | M M M M M M 73`` 74We can split up these overloads in two groups. 75The first group can be called /reverse insertion/. 76`` 77/* (1) Reverse insertion */ T\P| e b s m T\P| e i b p S M 78 ---+-------- ---+------------ 79 s | s s S | S S S 80 m | m m M | M M M 81`` 82The second group can be viewed as an /erasure by key objects/ 83`` 84/* (2) Erasure by key objects */ T\P| e b s m T\P| e i b p S M 85 ---+-------- ---+------------ 86 s | s s S | S S S 87 m | m m M | M M M 88`` 89 90On Maps ['*reverse insertion (1)*] is different from 91*stl's* erase semantics, because value pairs are deleted only, 92if key ['*and*] data values are found. Only 93['*erasure by key objects (2)*] works like the erase function 94on *stl's* std::maps, that passes a ['*key value*] as argument. 95 96On Sets both function groups fall together 97as ['*set difference*]. 98 99 100Complexity characteristics for inplace erasure operations are 101given by the next tables where 102`` 103n = iterative_size(y); 104m = iterative_size(x); //if P is a container type 105`` 106 107[table Time Complexity for inplace erasure on element containers 108[[`T& erase(T& y, const P& x)`][__ch_dom_t__][__ch_dom_mp_t__][__ch_icl_set__][__ch_icl_map__]] 109[[__icl_set__] [__Olgn__] [] [__Omlgn__] [] ] 110[[__icl_map__] [__Olgn__] [__Olgn__] [__Omlgn__] [__Omlgn__] ] 111] 112 113 114[table Time Complexity for inplace erasure on interval containers 115[[`T& erase(T& y, const P& x)`][__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__][__ch_itv_sets__][__ch_itv_maps__]] 116[[interval_sets] [__Olgn__] [__a_Olgn__] [] [] [__Omlgnpm__] [] ] 117[[interval_maps] [__Olgn__] [__a_Olgn__] [__Olgn__] [__On__] [__Omlgnpm__] [__Omlgnpm__] ] 118] 119 120[endsect][/ Erasure of Objects] 121 122[section Erasure by Iterators] 123 124The next table shows the *icl* containers that erasure with iterators is 125available for. Erase on iterators erases always one `value` of `value_type` 126for an iterator pointing to it. 127So we erase 128 129* elements from __icl_sets__ 130* element-value pairs from __icl_maps__ 131* intervals from __itv_sets__ and 132* interval-value-pairs from __itv_maps__ 133 134[table 135[[['*Erasure by iterators*]] [__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__] ] 136[[`void T::erase(iterator pos)`] [__aO1__] [__aO1__] [__aO1__] [__aO1__] ] 137[[`void T::erase(iterator first, iterator past)`] [__Ok__] [__Ok__] [__Ok__] [__Ok__] ] 138] 139 140Erasing by a single iterator need only ['*amortized constant time*]. 141Erasing via a range of iterators `[first, past)` is of ['*linear time*] 142in the number `k` of iterators in range `[first, past)`. 143 144[endsect][/ Erasure by Iterators] 145 146 147['*See also . . .*] 148[table 149[] 150[[[link boost_icl.function_reference.insertion ['*Insertion*]] ]] 151[[[link boost_icl.function_reference.subtraction ['*Subtraction*]] ]] 152] 153 154['*Back to section . . .*] 155[table 156[] 157[[[link function_synopsis_table ['*Function Synopsis*]] ]] 158[[[link boost_icl.interface ['*Interface*]] ]] 159] 160 161[endsect][/ Erasure] 162 163 164