...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
Subtraction 
intervals 
interval 
interval 
element 
element 










1 


1 
Functions and operators that implement Subtraction on icl objects are given in the table above.
Description of Subtraction 



Subtraction on Sets implements set difference 

Subtraction on Maps implements a map
difference function similar to set
difference. If, on subtraction of an element value
pair Find more on subtractability of maps and related semantic issues following the links. 
The admissible combinations of types for subtraction functions can be summarized in the overload table below:
// overload table for T\P e i b p T& T::subtract(const P&) + T& subtract(T&, const P&) s  s m  m S  S S M  M M
The next table contains complexity characteristics for subtract
.
Table 1.24. Time Complexity for function subtract 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 operator
=
more type combinations are provided
for subtraction than for addition.
// overload tables for element containers: interval containers: 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
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 icl::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 = iterative_size(y); m = iterative_size(x); //if P is a container type
Table 1.26. Time Complexity for inplace Subtraction 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 admissible overloads for the infix subtraction
operator 
which is a non commutative operation is given by the next overload table.
// overload tables for   e b s m   e i b p S M T operator  (T, const P&) + + s  s s S  S S S m  m m m m M  M M M M M M
Subtraction 
Types 
Description 


subtract right_over = left_subtract(right, left_minuend); ... d) : right ... c) : left_minuend [c d) : right_over



subtract left_over = right_subtract(left, right_minuend); [a ... : left [b ... : right_minuend [a b) : left_over

See also . . .
Back to section . . .