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 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 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 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 T , false otherwise. bool S > = const set< E,set_impl> & T returns true if T 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 T , 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 T 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: Integer Sets ( int_set Up: Basic Data Types Previous: Singly Linked Lists (   Contents   Index
Christian Uhrig 2017-04-07