 Home Libraries People FAQ More

### Symmetric Difference

Synopsis
Functions
Inplace operators
Infix operators

#### Synopsis

Symmetric difference

interval
sets

interval
maps

element
sets

element
maps

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

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

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

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

Functions and operators that implement symmetric difference on icl objects are given in the table above.

Description of symmetric difference

`Sets`

`operator ^` implements set symmetric difference

`Maps`

`operator ^` implements a map symmetric difference function similar to set symmetric difference. All pairs that are common to both arguments are removed. All others unified.

#### Functions

Symmetric difference is implemented on interval containers by the function ```T& flip(T&, const P& operand)```.

```flip(y,x)
```

deletes every element of `y`, if it is contained in `x`. Elements of `x` not contained in `y` are added. For icl containers flip is also availabel as memeber function `T& T::flip(const P& operand)`.

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

```/* overload table for */           T\P| e i b p
T& T::flip(const P&)               ---+--------
T& flip(T&, const P&)               s | s
m |     m
S | S S
M |     M M
```

The next table contains complexity characteristics for functions `flip`.

Table 1.37. Time Complexity for member functions flip on icl containers

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

domain
type

interval
type

domain
mapping
type

interval
mapping
type

O(log n)

`icl::map`

O(log n)

`interval_set`
`separate_interval_set`

O(log n)

O(n)

`split_interval_set`

O(log n)

O(n)

`interval_map`
`split_interval_map`

O(log n)

O(n)

#### Inplace operators

The overload tables below are giving admissible type combinations for `operator ^=` that implements symmetric difference.

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

Complexity characteristics for inplace operators that implement symmetric difference are given by the next tables where

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

Table 1.38. Time Complexity for inplace symmetric difference on element containers

```T& operator &= (T& y, const P& x)```

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.39. Time Complexity for inplace symmetric difference 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)

O(n)

O(m log(n+m))

interval_maps

O(log n)

O(n)

O(log n)

O(n)

O(m log(n+m))

O(m log(n+m))

#### Infix operators

For the infix version of symmetric difference the following overloads are available:

```// overload tables for             element containers:     interval containers:
T operator ^ (T, const P&)         ^  | e b s m            ^  | e  i  b  p  S1 S2 S3 M1 M3
T operator ^ (const P&, T)         ---+--------            ---+---------------------------
e  |     s              e  |             S1 S2 S3
b  |       m            i  |             S1 S2 S3
s  | s   s              b  |                      M1 M3
m  |   m   m            p  |                      M1 M3
S1 | S1 S1       S1 S2 S3
S2 | S2 S2       S2 S2 S3
S3 | S3 S3       S3 S3 S3
M1 |       M1 M1          M1 M3
M3 |       M3 M3          M3 M3
```

To resolve ambiguities among interval containers the finer container type is chosen as result type.