ceph/src/boost/libs/icl/doc/functions_erasure.qbk

   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
  25 The effects of ['*erasure*] implemented by `erase` and ['*subtraction*]
  26 implemented by `subtract` and `operator -=` are identical for all Set-types of
  27 the *icl*.
  28
  29 For Map-types, `erase` provides the *stl* semantics of erasure in
  30 contrast to `subtract` and `operator -=`, that implement a generalized subtraction,
  31 that performs inverse aggregations if key values collide or key intervals overlap.
  32
  33 Using iterators it is possible to erase objects or ranges of
  34 objects 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
  44 T& T::erase(const P&)          ---+--------
  45 T& erase(T&, const P&)          s | s
  46                                 m |     m
  47                                 S | S S
  48                                 M |     M M
  49 ``
  50
  51 The 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
  63 As presented in the overload tables for inplace function `erase` below,
  64 more type combinations are available for /erasure/ than for
  65 /insertion/.
  66
  67 ``
  68 // overload tables for function    element containers:     interval containers:
  69 T& 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 ``
  74 We can split up these overloads in two groups.
  75 The 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 ``
  82 The 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
  90 On Maps ['*reverse insertion (1)*] is different from
  91 *stl's* erase semantics, because value pairs are deleted only,
  92 if key ['*and*] data values are found. Only
  93 ['*erasure by key objects (2)*] works like the erase function
  94 on *stl's* std::maps, that passes a ['*key value*] as argument.
  95
  96 On Sets both function groups fall together
  97 as ['*set difference*].
  98
  99
 100 Complexity characteristics for inplace erasure operations are
 101 given by the next tables where
 102 ``
 103 n = iterative_size(y);
 104 m = 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
 124 The next table shows the *icl* containers that erasure with iterators is
 125 available for. Erase on iterators erases always one `value` of `value_type`
 126 for an iterator pointing to it.
 127 So 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
 140 Erasing by a single iterator need only ['*amortized constant time*].
 141 Erasing via a range of iterators `[first, past)` is of ['*linear time*]
 142 in 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