| Home | Libraries | People | FAQ | More

### Symmetric Difference

#### Synopsis

Symmetric difference | interval sets | interval maps | element sets | element maps
--- | --- | --- | --- | ---
`T& T::flip(const P&)` | e i | b p |  | b
`T& flip(T&, const P&)` | e i | b p | e | b
`T& operator ^=(T&, const P&)` | e i S | b p M | e s | b m
`T operator ^ (T, const P&)` `T operator ^ (const P&, T)` | e i S | b p M | e s | b m

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
--- | --- | --- | --- | ---
`std::set` | 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
--- | --- | --- | --- | ---
`std::set` | 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.

See also . . .

Intersection
Subtraction
Addition

Back to section . . .

Function Synopsis
Interface