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.

Creation

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

Operations

void	S.insert(E x)	adds x to S.
void	S.del(E x)	deletes x from S.
bool	S.member(E x)	returns true if x in S, false otherwise.
E	S.choose()	returns an element of S. Precondition: S is not empty.
set<E>	S.join(set<E> T)	returns S <union> T.
set<E>	S.diff(set<E> T)	returns S - T.
set<E>	S.intersect(set<E> T)	returns S <intersection> T.
set<E>	S.symdiff(set<E> T)	returns the symetric difference of S and T.
set<E>	S + T	returns S.join(T).
set<E>	S - T	returns S.diff(T).
set<E>	S & T	returns S.intersect(T).
set<E>	S
set<E>&	S += T	assigns S.join(T) to S and returns S.
set<E>&	S -= T	assigns S.diff(T) to S and returns S.
set<E>&	S &= T	assigns S.intersect(T) to S and returns S.
set<E>&	S
bool	S <= T	returns true if S subset of T, false otherwise.
bool	S >= T	returns true if T subset of S, false otherwise.
bool	S == T	returns true if S = T, false otherwise.
bool	S != T	returns true if S != T, false otherwise.
bool	S < T	returns true if S proper subset of T, false otherwise.
bool	S > T	returns true if T proper subset of 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.