...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
Erasure |
interval |
interval |
element |
element |
---|---|---|---|---|
|
||||
|
||||
|
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
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.
/* 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 1.31. Time Complexity for erasure of elements and segments on icl containers
|
domain |
interval |
domain |
interval |
---|---|---|---|---|
O(log n) |
|
|
|
|
O(log n) |
|
O(log n) |
|
|
O(log n) |
amortized |
|
|
|
O(log n) |
O(n) |
O(log n) |
O(n) |
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 1.33. Time Complexity for inplace erasure on interval containers
|
domain |
interval |
domain |
interval |
interval |
interval |
---|---|---|---|---|---|---|
interval_sets |
O(log n) |
amortized |
|
|
O(m log(n+m)) |
|
interval_maps |
O(log n) |
amortized |
O(log n) |
O(n) |
O(m log(n+m)) |
O(m log(n+m)) |
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
std::sets
icl::maps
interval_sets
and
interval_maps
Erasure by iterators |
interval |
interval |
element |
element |
---|---|---|---|---|
|
amortized O(1) |
amortized O(1) |
amortized O(1) |
amortized O(1) |
|
O(k) |
O(k) |
O(k) |
O(k) |
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)
.
See also . . .
Back to section . . .