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/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(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,set_impl>	S.join(set<E,set_impl> T)	returns S $\cup$ T.
set<E,set_impl>	S.diff(set<E,set_impl> T)	returns S - T.
set<E,set_impl>	S.intersect(set<E,set_impl> T)
		returns S $\cap$ T.
set<E,set_impl>	S.symdiff(set<E,set_impl> T)
		returns the symetric difference of S and T.
set<E,set_impl>	S + set<E,set_impl> T	returns S.join(T).
set<E,set_impl>	S - set<E,set_impl> T	returns S.diff(T).
set<E,set_impl>	S & set<E,set_impl> T	returns S.intersect(T).
set<E,set_impl>	S
set<E,set_impl>&	S += set<E,set_impl> T	assigns S.join(T) to S and returns S.
set<E,set_impl>&	S -= set<E,set_impl> T	assigns S.diff(T) to S and returns S.
set<E,set_impl>&	S &= set<E,set_impl> T	assigns S.intersect(T) to S and returns S.
set<E,set_impl>&	S
bool	S <= set<E,set_impl> T	returns true if S $\subseteq$ T, false otherwise.
bool	S >= set<E,set_impl> T	returns true if T $\subseteq$ S, false otherwise.
bool	S == set<E,set_impl> T	returns true if S = T, false otherwise.
bool	S != set<E,set_impl> T	returns true if S $\not=$T, false otherwise.
bool	S < set<E,set_impl> T	returns true if S $\subset$ T, false otherwise.
bool	S > 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 S₁ and S₂ be a two sets of type T with | S₁ | = n₁ and | S₂ | = n₂. Then S₁.join(S₂) and S₁.diff(S₂) need time O(n₂log(n₁ + n₂)), S₁.intersect(S₂) needs time O(n₁log(n₁ + n₂).