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