Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext

Erasure

Synopsis
Erasure of Objects
Erasure by Iterators

Erasure

interval
sets

interval
maps

itl::set

itl::map

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 itl.

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 itl Sets and Maps.

// overload table for
T& T::erase(const P&)

erase | e i b p    
------+--------
  s   | s
  m   |     m
  S   | S S         
  M   |     M M    

The next table contains complexity characteristics for member function erase.

Table1.28.Time Complexity for member function erase on itl containers

T& T::erase(const P&)

domain
type

interval
type

domain
mapping
type

interval
mapping
type

itl::set

O(log n)

itl::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 inplace function
T& operator erase(T&, const P&)

element containers:     interval containers:  
erase | e b s m         erase | 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
erase | e b s m         erase | 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
erase | e b s m         erase | 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 = y.iterative_size();
m = x.iterative_size(); //if P is a container type

Table1.29.Time Complexity for inplace erasure on element containers

T& erase(T& y, const P& x)

domain
type

domain
mapping
type

interval
sets

interval
maps

itl::set

O(log n)

O(m log n)

itl::map

O(log n)

O(log n)

O(m log n)

O(m log n)


Table1.30.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))


The next table shows the itl 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

Erasure by iterators

interval
sets

interval
maps

itl::set

itl::map

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


PrevUpHomeNext