123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163 |
- [/
- Copyright (c) 2008-2010 Joachim Faulhaber
- Distributed under the Boost Software License, Version 1.0.
- (See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt)
- ]
- [/ //= Erasure ===================================================================]
- [section Erasure]
- [section Synopsis][/ Erasure]
- [table
- [[['*Erasure*]] [__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__] ]
- [[`T& T::erase(const P&)`] [__ei ] [__ei __bp] [__e] [__bp] ]
- [[`T& erase(T&, const P&)`] [__eiS] [__eiS __bpM] [__es] [__bm] ]
- [[`void T::erase(iterator)`] [1] [1] [1] [1] ]
- [[`void T::erase(iterator,iterator)`] [1] [1] [1] [1] ]
- ]
- [h5 Erasure]
- The effects of ['*erasure*] implemented by `erase` and ['*subtraction*]
- implemented by `subtract` and `operator -=` are identical for all Set-types of
- the *icl*.
- For Map-types, `erase` provides the *stl* semantics of erasure in
- contrast to `subtract` and `operator -=`, that implement a generalized subtraction,
- that performs inverse aggregations if key values collide or key intervals overlap.
- Using iterators it is possible to erase objects or ranges of
- objects the iterator is pointing at from icl Sets and Maps.
- [endsect][/ Synopsis Erasure]
- [section Erasure of Objects]
- ``
- /* overload table for */ T\P| e i b p
- T& T::erase(const P&) ---+--------
- T& erase(T&, const P&) s | s
- m | m
- S | S S
- M | M M
- ``
- The next table contains complexity characteristics for the `erase` function on elements and segments.
- [table Time Complexity for erasure of elements and segments on icl containers
- [[`T& T::erase(const P&)`\n
- `T& erase(T&, const P&)`] [__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__]]
- [[__icl_set__] [__Olgn__] [] [] [] ]
- [[__icl_map__] [__Olgn__] [] [__Olgn__] [] ]
- [[__itv_sets__] [__Olgn__] [__a_Olgn__] [] [] ]
- [[__itv_maps__] [__Olgn__] [__On__] [__Olgn__] [__On__] ]
- ]
- As presented in the overload tables for inplace function `erase` below,
- more type combinations are available for /erasure/ than for
- /insertion/.
- ``
- // overload tables for function element containers: interval containers:
- T& erase(T&, const P&) T\P| e b s m T\P| e i b p S M
- ---+-------- ---+------------
- s | s s S | S S S
- m | m m m m M | M M M M M M
- ``
- We can split up these overloads in two groups.
- The first group can be called /reverse insertion/.
- ``
- /* (1) Reverse insertion */ T\P| e b s m T\P| e i b p S M
- ---+-------- ---+------------
- s | s s S | S S S
- m | m m M | M M M
- ``
- The second group can be viewed as an /erasure by key objects/
- ``
- /* (2) Erasure by key objects */ T\P| e b s m T\P| e i b p S M
- ---+-------- ---+------------
- s | s s S | S S S
- m | m m M | M M M
- ``
- On Maps ['*reverse insertion (1)*] is different from
- *stl's* erase semantics, because value pairs are deleted only,
- if key ['*and*] data values are found. Only
- ['*erasure by key objects (2)*] works like the erase function
- on *stl's* std::maps, that passes a ['*key value*] as argument.
- On Sets both function groups fall together
- as ['*set difference*].
- Complexity characteristics for inplace erasure operations are
- given by the next tables where
- ``
- n = iterative_size(y);
- m = iterative_size(x); //if P is a container type
- ``
- [table Time Complexity for inplace erasure on element containers
- [[`T& erase(T& y, const P& x)`][__ch_dom_t__][__ch_dom_mp_t__][__ch_icl_set__][__ch_icl_map__]]
- [[__icl_set__] [__Olgn__] [] [__Omlgn__] [] ]
- [[__icl_map__] [__Olgn__] [__Olgn__] [__Omlgn__] [__Omlgn__] ]
- ]
- [table Time Complexity for inplace erasure on interval containers
- [[`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__]]
- [[interval_sets] [__Olgn__] [__a_Olgn__] [] [] [__Omlgnpm__] [] ]
- [[interval_maps] [__Olgn__] [__a_Olgn__] [__Olgn__] [__On__] [__Omlgnpm__] [__Omlgnpm__] ]
- ]
- [endsect][/ Erasure of Objects]
- [section Erasure by Iterators]
- The next table shows the *icl* containers that erasure with iterators is
- available for. Erase on iterators erases always one `value` of `value_type`
- for an iterator pointing to it.
- So we erase
- * elements from __icl_sets__
- * element-value pairs from __icl_maps__
- * intervals from __itv_sets__ and
- * interval-value-pairs from __itv_maps__
- [table
- [[['*Erasure by iterators*]] [__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__] ]
- [[`void T::erase(iterator pos)`] [__aO1__] [__aO1__] [__aO1__] [__aO1__] ]
- [[`void T::erase(iterator first, iterator past)`] [__Ok__] [__Ok__] [__Ok__] [__Ok__] ]
- ]
- Erasing by a single iterator need only ['*amortized constant time*].
- Erasing via a range of iterators `[first, past)` is of ['*linear time*]
- in the number `k` of iterators in range `[first, past)`.
- [endsect][/ Erasure by Iterators]
- ['*See also . . .*]
- [table
- []
- [[[link boost_icl.function_reference.insertion ['*Insertion*]] ]]
- [[[link boost_icl.function_reference.subtraction ['*Subtraction*]] ]]
- ]
- ['*Back to section . . .*]
- [table
- []
- [[[link function_synopsis_table ['*Function Synopsis*]] ]]
- [[[link boost_icl.interface ['*Interface*]] ]]
- ]
- [endsect][/ Erasure]
|