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/set.h >

Creation

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

Next: Integer Sets ( int_set Up: Basic Data Types Previous: Singly Linked Lists (   Contents   Index
LEDA research project
2000-10-12