Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Click here to view the latest version of this page.
PrevUpHomeNext

Symmetric Difference

Synopsis
Functions
Inplace operators
Infix operators

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.

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)


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


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


PrevUpHomeNext