...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
Symmetric difference |
interval |
interval |
element |
element |
---|---|---|---|---|
|
|
|||
|
||||
|
||||
|
Functions and operators that implement symmetric difference on icl objects are given in the table above.
|
Description of symmetric difference |
---|---|
|
|
|
|
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
|
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 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.39. 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 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 . . .
Back to section . . .