Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext

Subtraction

Synopsis
Member functions
Inplace operators
Infix operators

Subtraction

interval
sets

interval
maps

itl::set

itl::map

T& T::subtract(const P&)

e i

b p

e

b

T& operator -=(T&, const P&)

e i S

e i S b p M

e s

b m

T operator - (T, const P&)

e i S

e i S b p M

e s

b m

Functions and operators that implement Subtraction on itl objects are given in the table above.

Description of Subtraction

Sets

Subtraction on Sets implements set difference

Maps

Subtraction on Maps implements a map difference function similar to set difference. If, on subtraction of an element value pair (k,v) it's key k is in the map already, the subtraction function is propagated to the associated value. On the associated value an aggregation is performed, that reverses the effect of the corresponding addition function.

Find more on subtractability of maps and related semantical issues following the links.

The admissible combinations of types for member function T& T::add(const P&) can be summarized in the overload table below:

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

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

The next table contains complexity characteristics for subtract.

Table1.21.Time Complexity for member function subtract on itl containers

T& T::subtract(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 operator -= more type combinations are provided for subtraction than for addition.

// overload tables for
T& operator -= (T&, const P&)

element containers:     interval containers:  
-= | e b s m            -= | 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    

Subtraction provides the reverse operation of an addition for these overloads,

// Reverse addition
-= | e b s m            -= | e i b p S M    
---+--------            ---+------------    
s  | s   s              S  | S S     S       
m  |   m   m            M  |     M M   M    

and you can erase parts of itl::maps or interval_maps using key values, intervals or element or interval sets using these overloads:

// Erasure by key objects
-= | e b s m            -= | e i b p S M    
---+--------            ---+------------    
s  | s   s              S  | S S     S       
m  | m   m              M  | M M     M    

On Sets both function groups fall together as set difference.

Complexity characteristics for inplace subtraction operations are given by the next tables where

n = y.iterative_size();
m = x.iterative_size(); //if P is a container type

Table1.22.Time Complexity for inplace Subtraction on element containers

T& operator -= (T&, const P&)

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.23.Time Complexity for inplace Subtraction on interval containers

T& operator -= (T&, const P&)

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 admissible overloads for the infix subtraction operator - which is a non commutative operation is given by the next overload table.

// overload tables for
T operator - (T, const P&)

-  | e b s m      -  | 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    

See also . . .

Addition

Erasure

Back to section . . .

Function Synopsis

Interface


PrevUpHomeNext