...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
Insertion |
interval |
interval |
element |
element |
---|---|---|---|---|
|
||||
|
||||
|
||||
|
||||
|
||||
|
|
|
1 |
|
|
|
|
1 |
The effects of insertion
implemented by insert
and
addition implemented
by add
and operator +=
are identical for all Set-types of the icl.
For Map-types, insert
provides
the stl semantics of insertion in contrast
to add
and operator +=
,
that implement a generalized addition, that performs aggregations if key
values collide or key intervals overlap. insert
on Maps does not alter a maps content at the points, where the keys of
the object to inserted overlap or collide with keys that are already in
the map.
Overwriting values using operator[]
like in
my_map[key] = new_value;
is not provided for interval_maps
because an operator[]
is not implemented for them. As a substitute a function T& T::set(const P&)
can be used to achieve the same effect:
my_map.set(make_pair(overwrite_this, new_value));
// overload table for functions T\P| e i b p V T::insert(const P&) ---+-------- V insert(T&, const P&) s | s m | m S | S M | M
Table 1.27. Time Complexity for member function insert on icl containers
|
domain |
interval |
domain |
interval |
---|---|---|---|---|
O(log n) |
|
|
|
|
|
|
O(log n) |
|
|
O(log n) |
amortized |
|
|
|
O(log n) |
O(n) |
|
|
|
|
|
O(log n) |
O(n) |
// overload tables for function element containers: interval containers: T& insert(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
Time complexity characteristics of inplace insertion for interval containers is given by this table.
Table 1.29. Time Complexity for inplace insertion on interval containers
|
|
domain |
interval |
domain |
interval |
interval |
interval |
---|---|---|---|---|---|---|---|
interval_sets |
O(log n) |
amortized |
|
|
O(m log(n+m)) |
|
|
|
O(log n) |
O(n) |
|
|
O(m log(n+m)) |
|
|
interval_maps |
|
|
|
O(log n) |
O(n) |
|
O(m log(n+m)) |
Function T&
T::insert(T::iterator
prior,
const P& addend)
allows for an insertion in constant time, if addend
can be inserted right after iterator prior
without collision. If this is not possible the complexity characteristics
are as stated for the non hinted insertion above. Hinted insertion is available
for these combinations of types:
// overload table for insertion with hint T\P| e i b p V T::insert(J pos, const P&) ---+-------- V insert(T&, J pos, const P&) s | s m | m S | S M | M
// overload table for member function T\P| b p T& T::set(const P&) ---+---- T& set_at(T&, const P&) m | m M | M
Table 1.30. Time Complexity for member function `set`
|
domain_mapping_type |
interval_mapping_type |
---|---|---|
icl::map |
O(log n) |
|
interval_maps |
|
amortized |
See also . . .
Back to section . . .