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 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 S.join(const set& T) returns S T. set S.diff(const set& T) returns S - T. set S.intersect(const set& T) returns S T. set S.symdiff(const set& T) returns the symetric difference of S and T. set S + const set& T returns S.join(T). set S - const set& T returns S.diff(T). set S & const set& T returns S.intersect(T). set S % const set& T returns S.symdiff(T). set& S += const set& T assigns S.join(T) to S and returns S. set& S -= const set& T assigns S.diff(T) to S and returns S. set& S &= const set& T assigns S.intersect(T) to S and returns S. set& S %= const set& T assigns S.symdiff(T) to S and returns S. bool S <= const set& T returns true if S T, false otherwise. bool S >= const set& T returns true if T S, false otherwise. bool S == const set& T returns true if S = T, false otherwise. bool S != const set& T returns true if S T, false otherwise. bool S < const set& T returns true if S T, false otherwise. bool S > const set& 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