Home | Libraries | People | FAQ | More |
Subtraction |
interval |
interval |
itl::set |
itl::map |
---|---|---|---|---|
|
||||
|
||||
|
Functions and operators that implement Subtraction on itl 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 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
.
Table 1.21. Time Complexity for member function subtract on itl 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 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
Table 1.23. 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 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 . . .
Back to section . . .