Home | Libraries | People | FAQ | More |
Symmetric difference |
interval |
interval |
itl::set |
itl::map |
---|---|---|---|---|
|
||||
|
||||
|
Functions and operators that implement symmetric difference on itl objects are given in the table above.
|
Description of symmetric difference |
---|---|
|
|
|
|
Symmetric difference is implemented on interval containers
by the member function T& T::flip(const P& operand)
.
y.flip(x)
deletes every element of y
,
if it is contained in x
.
Elements of x
not contained
in y
are added.
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& T::flip(const P&) flip | e i b p -----+-------- s | s m | m S | S S M | M M
The next table contains complexity characteristics for member functions
flip
.
Table 1.34. Time Complexity for member functions flip on itl containers
|
domain |
interval |
domain |
interval |
---|---|---|---|---|
O(log n) |
|
|
|
|
|
|
O(log n) |
|
|
O(log n) |
O(n) |
|
|
|
O(log n) |
O(n) |
|
|
|
|
|
O(log n) |
O(n) |
The overload tables below are giving admissible type combinations for
operator ^=
that implements symmetric difference.
// 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
Complexity characteristics for inplace operators that implement symmetric difference are given by the next tables where
n = y.iterative_size(); m = x.iterative_size(); //if P is a container
Table 1.36. Time Complexity for inplace symmetric difference on interval containers
|
domain |
interval |
domain |
interval |
interval |
interval |
---|---|---|---|---|---|---|
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)) |
For the infix version of symmetric difference the following overloads are available:
// overload tables for T operator ^ (T, const P&) T operator ^ (const P&, T) element containers: interval containers: ^ | e b s m ^ | e i b p S1 S2 S3 M1 M3 ---+-------- ---+--------------------------- 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 . . .
Back to section . . .