Next: Dynamic Integer Sets (
Up: Basic Data Types
Previous: Sets ( set )
Integer Sets ( int_set )
Definition
An instance S of the data type
intset 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
intset for elements from
[a..b] and initializes it to the empty set. |
int_set |
S(int n) |
creates an instance S of type
intset 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. |
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).
Next: Dynamic Integer Sets (
Up: Basic Data Types
Previous: Sets ( set )
LEDA research project
1999-04-23