Definition
An instance S of the data type int_set is a subset of a fixed interval [a..b] of the integers, called the range of S.
#include < LEDA/int_set.h >
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. |
bool | S.member(int x) | returns true if x in S, false otherwise.
Precondition a < = x < = b. |
int | S.min() | returns the minimal integer in the range of of S. |
int | S.max() | returns the maximal integer in the range of of S. |
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. |
int_set | S | returns the complement of S. |
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).