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 [3]. 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₂).