next up previous contents index
Next: Integer Sets ( int_set Up: Basic Data Types Previous: Singly Linked Lists (   Contents   Index


Sets ( set )

Definition

An instance S of the parameterized data type set<E> is a collection of elements of the linearly ordered type E , called the element type of S . The size of S is the number of elements in S , a set of size zero is called the empty set.

#include < LEDA/core/set.h >

Creation

set< E> S creates an instance S of type set<E> and initializes it to the empty set.

Operations

void S.insert(const E& x) adds x to S.

void S.del(const E& x) deletes x from S.

bool S.member(const E& x) returns true if x in S, false otherwise.

const E& S.choose() returns an element of S.
Precondition S is not empty.

set< E,set_impl> S.join(const set< E,set_impl> & T)
    returns S $ \cup$ T.

set< E,set_impl> S.diff(const set< E,set_impl> & T)
    returns S - T.

set< E,set_impl> S.intersect(const set< E,set_impl> & T)
    returns S $ \cap$ T.

set< E,set_impl> S.symdiff(const set< E,set_impl> & T)
    returns the symetric difference of S and T.

set< E,set_impl> S + const set< E,set_impl> & T
    returns S.join(T).

set< E,set_impl> S - const set< E,set_impl> & T
    returns S.diff(T).

set< E,set_impl> S & const set< E,set_impl> & T
    returns S.intersect(T).

set< E,set_impl> S % const set< E,set_impl> & T
    returns S.symdiff(T).

set< E,set_impl> & S += const set< E,set_impl> & T
    assigns S.join(T) to S and returns S.

set< E,set_impl> & S -= const set< E,set_impl> & T
    assigns S.diff(T) to S and returns S.

set< E,set_impl> & S &= const set< E,set_impl> & T
    assigns S.intersect(T) to S and returns S.

set< E,set_impl> & S %= const set< E,set_impl> & T
    assigns S.symdiff(T) to S and returns S.

bool S < = const set< E,set_impl> & T
    returns true if S $ \subseteq$ T , false otherwise.

bool S > = const set< E,set_impl> & T
    returns true if T $ \subseteq$ S , false otherwise.

bool S == const set< E,set_impl> & T
    returns true if S = T , false otherwise.

bool S != const set< E,set_impl> & T
    returns true if S $ \not=$T , false otherwise.

bool S < const set< E,set_impl> & T
    returns true if S $ \subset$ T , false otherwise.

bool S > const set< E,set_impl> & T
    returns true if T $ \subset$ S , false otherwise.

bool S.empty() returns true if S is empty, false otherwise.

int S.size() returns the size of S.

void S.clear() makes S the empty set.


Iteration


forall(x, S ) { ``the elements of S are successively assigned to x '' }

Implementation

Sets are implemented by randomized search trees [2]. Operations insert, del, member take time O(log n) , empty, size take time O(1) , and clear takes time O(n) , where n is the current size of the set.

The operations join, intersect, and diff have the following running times: Let S1 and S2 be a two sets of type T with | S1 | = n1 and | S2 | = n2 . Then S1 .join(S2 ) and S1 .diff(S2 ) need time O(n2log(n1 + n2)) , S1 .intersect(S2 ) needs time O(n1log(n1 + n2) .


next up previous contents index
Next: Integer Sets ( int_set Up: Basic Data Types Previous: Singly Linked Lists (   Contents   Index
Christian Uhrig 2017-04-07