ceph/src/boost/libs/icl/doc/functions_insertion.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 [/ //= Insertion ===================================================================]
  11 [section Insertion]
  12
  13 [section Synopsis][/ Insertion]
  14
  15 [table
  16 [[['*Insertion*]][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]  ]
  17
  18 [[`V T::insert(const P&)`]                         [__ei]    [__bp]   [__e]    [__b]  ]
  19 [[`V insert(T&, const P&)`]                        [__ei]    [__bp]   [__e]    [__b]  ]
  20 [[`J T::insert(J pos, const P&)`]                  [__i]     [__p]    [__e]    [__b]  ]
  21 [[`J insert(T&, J pos, const P&)`]                 [__i]     [__p]    [__e]    [__b]  ]
  22 [[`T& insert(T&, const P&)`]                      [__eiS]   [__bpM]   [__es]   [__bm] ]
  23 [[`T& T::set(const P&)`]                             [ ]     [__bp]   [ ]      [1]    ]
  24 [[`T& set_at(T&, const P&)`]                         [ ]     [__bp]   [ ]      [1]    ]
  25
  26 ]
  27
  28 [h5 Insertion]
  29
  30 The effects of ['*insertion*] implemented by `insert` and ['*addition*]
  31 implemented by `add` and `operator +=` are identical for all Set-types of
  32 the *icl*.
  33
  34 For Map-types, `insert` provides the *stl* semantics of insertion in
  35 contrast to `add` and `operator +=`, that implement a generalized addition,
  36 that performs aggregations if key values collide or key intervals overlap.
  37 `insert` on Maps does not alter a maps content at the points, where
  38 the keys of the object to inserted overlap or collide with keys that
  39 are already in the map.
  40
  41
  42 [h5 Setting values]
  43
  44 Overwriting values using `operator[]` like in
  45 ``
  46 my_map[key] = new_value;
  47 ``
  48 is not provided for __itv_maps__ because an `operator[]` is not
  49 implemented for them. As a substitute a function
  50 `T& T::set(const P&)` can be used to achieve the same effect:
  51 ``
  52 my_map.set(make_pair(overwrite_this, new_value));
  53 ``
  54
  55 [endsect][/ Synopsis Insertion]
  56
  57 [section Insertion]
  58
  59 ``
  60 // overload table for functions      T\P| e i b p
  61 V T::insert(const P&)                ---+--------
  62 V insert(T&, const P&)                s | s
  63                                       m |     m
  64                                       S |   S
  65                                       M |       M
  66 ``
  67
  68 [table Time Complexity for member function insert on icl containers
  69 [[`T& T::insert(const P&)`]    [__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__]]
  70 [[__icl_set__]                 [__Olgn__] []          []        []          ]
  71 [[__icl_map__]                 []         []          [__Olgn__][]          ]
  72 [[__itv_set__\n__sep_itv_set__][__Olgn__] [__a_Olgn__][]        []          ]
  73 [[__spl_itv_set__]             [__Olgn__] [__On__]    []        []          ]
  74 [[__itv_map__\n__spl_itv_map__][]         []          [__Olgn__][__On__]    ]
  75 ]
  76
  77 ``
  78 // overload tables for function      element containers:     interval containers:
  79 T& insert(T&, const P&)              T\P| e b s m            T\P| e i b p S M
  80                                      ---+--------            ---+------------
  81                                       s | s   s               S | S S     S
  82                                       m |   m   m             M |     M M   M
  83 ``
  84
  85
  86 [table Time Complexity for inplace insertion on element containers
  87 [[`T& insert(T& y, const P& x)`][__ch_dom_t__][__ch_dom_mp_t__][__ch_itv_sets__][__ch_itv_maps__]]
  88 [[__icl_set__]                  [__Olgn__]    []               [__Om__]         []               ]
  89 [[__icl_map__]                  []            [__Olgn__]       []               [__Om__]         ]
  90 ]
  91
  92 Time complexity characteristics of inplace insertion for interval containers
  93 is given by this table.
  94
  95 [table Time Complexity for inplace insertion on interval containers
  96 [[`T& insert(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__]]
  97 [[interval_sets][__itv_set__\n__sep_itv_set__][__Olgn__] [__a_Olgn__][]        []        [__Omlgnpm__]    []               ]
  98 [[]             [__spl_itv_set__]             [__Olgn__] [__On__]    []        []        [__Omlgnpm__]    []               ]
  99 [[interval_maps][]                            []         []          [__Olgn__][__On__]  []               [__Omlgnpm__]    ]
 100 ]
 101
 102
 103 [h4 Hinted insertion]
 104
 105 Function `J T::insert(J prior, const P& addend)` allows
 106 for an insertion in ['*constant time*], if `addend` can be inserted
 107 right after iterator `prior` without collision. If this is not possible
 108 the complexity characteristics are as stated for the non hinted insertion
 109 above. Hinted insertion is available for these combinations of types:
 110 ``
 111 // overload table for insertion with hint        T\P| e i b p
 112 J T::insert(J pos, const P&)                     ---+--------
 113 J insert(T&, J pos, const P&)                     s | s
 114                                                   m |     m
 115                                                   S |   S
 116                                                   M |       M
 117 ``
 118
 119 [endsect][/ Insertion]
 120
 121
 122
 123 [section Setting values]
 124
 125 ``
 126 // overload table for member function         T\P| b p
 127 T& T::set(const P&)                           ---+----
 128 T& set_at(T&, const P&)                        m | m
 129                                                M |   M
 130 ``
 131
 132 [table Time Complexity for member function `set`
 133 [[`T& set(T&, const P&)`] [domain_mapping_type] [interval_mapping_type] ]
 134 [[icl::map]               [__Olgn__]            [ ]                     ]
 135 [[interval_maps]          []                    [__a_Olgn__]            ]
 136 ]
 137
 138 [endsect][/ Set]
 139
 140 ['*See also . . .*]
 141 [table
 142 []
 143 [[[link boost_icl.function_reference.addition ['*Erasure*]]          ]]
 144 [[[link boost_icl.function_reference.addition ['*Addition*]]         ]]
 145 ]
 146
 147 ['*Back to section . . .*]
 148 [table
 149 []
 150 [[[link function_synopsis_table ['*Function Synopsis*]]]]
 151 [[[link boost_icl.interface ['*Interface*]]                          ]]
 152 ]
 153
 154 [endsect][/ Insertion]
 155
 156