next up previous contents index
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<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 [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 up previous contents index
Next: Integer Sets ( int_set Up: Basic Data Types Previous: Singly Linked Lists (   Contents   Index
root 2008-01-09