Erasure

| Home | Libraries | People | FAQ | More

### Erasure

#### Synopsis

Erasure | interval sets | interval maps | element sets | element maps
--- | --- | --- | --- | ---
`T& T::erase(const P&)` | e i | e i b p | e | b p
`T& erase(T&, const P&)` | e i S | e i S b p M | e s | b m
`void T::erase(iterator)` | 1 | 1 | 1 | 1
`void T::erase(iterator,iterator)` | 1 | 1 | 1 | 1

###### Erasure

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.

#### Erasure of Objects

    /* 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

`T& T::erase(const P&)` `T& erase(T&, const P&)` | domain type | interval type | domain mapping type | interval mapping type
--- | --- | --- | --- | ---
`std::set` | O(log n) |  |  |
`icl::map` | O(log n) |  | O(log n) |
`interval_sets` | O(log n) | amortized O(log n) |  |
`interval_maps` | 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.32. Time Complexity for inplace erasure on element containers

`T& erase(T& y, const P& x)` | domain type | domain mapping type | std::set | icl::map
--- | --- | --- | --- | ---
`std::set` | O(log n) |  | O(m log n) |
`icl::map` | O(log n) | O(log n) | O(m log n) | O(m log n)

Table 1.33. Time Complexity for inplace erasure on interval containers

`T& erase(T& y, const P& x)` | domain type | interval type | domain mapping type | interval mapping type | interval sets | interval maps
--- | --- | --- | --- | --- | --- | ---
interval_sets | O(log n) | amortized O(log n) |  |  | O(m log(n+m)) |
interval_maps | O(log n) | amortized O(log n) | O(log n) | O(n) | O(m log(n+m)) | O(m log(n+m))

#### Erasure by Iterators

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

- elements from `std::sets`
- element-value pairs from `icl::maps`
- intervals from `interval_sets` and
- interval-value-pairs from `interval_maps`

Erasure by iterators | interval sets | interval maps | element sets | element maps
--- | --- | --- | --- | ---
`void T::erase(iterator pos)` | amortized O(1) | amortized O(1) | amortized O(1) | amortized O(1)
`void T::erase(iterator first, iterator past)` | 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 . . .

Insertion
Subtraction

Back to section . . .

Function Synopsis
Interface