Integer Sets (int_set)

Definition

An instance S of the data type int_set is a subset of a fixed interval [a..b] of the integers.

Creation

int_set	S(int a, int b);	creates an instance S of type int_set for elements from [a..b] and initializes it to the empty set.
int_set	S(int n);	creates an instance S of type int_set for elements from [0..n-1] and initializes it to the empty set.

Operations

void	S.insert(int x)	adds x to S. Precondition: a<= x<= b.
void	S.del(int x)	deletes x from S. Precondition: a<= x<= b.
int	S.member(int x)	returns true if x in S, false otherwise. Precondition: a<= x<= b.
void	S.clear()	makes S the empty set.
int_set&	S = S1	assignment.
int_set	S | S1	returns the union of S and S1.
int_set	S & S1	returns the intersection of S and S1.

Implementation

Integer sets are implemented by bit vectors. Operations insert, delete, member, empty, and size take constant time. clear, intersection, union and complement take time O(b-a+1).