Home Libraries People FAQ More

### Subtraction

Synopsis
Functions
Inplace operators
Infix operators
Subtraction on Intervals

#### Synopsis

Subtraction

intervals

interval
sets

interval
maps

element
sets

element
maps

```T& T::subtract(const P&)```

```T& subtract(T&, const P&)```

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

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

```T left_subtract(T, const T&)```

1

```T right_subtract(T, const T&)```

1

Functions and operators that implement Subtraction on icl 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 semantic issues following the links.

#### Functions

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

```T& T::subtract(const P&)```
```T& subtract(T&, const P&)```

domain
type

interval
type

domain
mapping
type

interval
mapping
type

O(log n)

`icl::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)

#### Inplace operators

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

```// 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.25. Time Complexity for inplace Subtraction on element containers

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

domain
type

domain
mapping
type

std::set

icl::map

O(log n)

O(m log n)

`icl::map`

O(log n)

O(log n)

O(m log n)

O(m log n)

Table 1.26. 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))

#### Infix operators

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 on Intervals

Subtraction

Types

Description

```T left_subtract(T right, const T& left_minuend)```

subtract `left_minuend` from the interval `right` on it's left side.

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

```T right_subtract(T left, const T& right_minuend)```

subtract `right_minuend` from the interval `left` on it's right side.

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