]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |