Dynamic Integer Sets
The data type d_int_set can be used to store a set of ints. Dynamic
Integer Sets are an extension of Integer
Sets.
Example
The following program shows how to use Dynamic Integer Sets. It generates
a d_int_set DIS and inserts 100 ints into DIS. Then it searches
for entries 37 and 168 in IS.
#include <LEDA/core/d_int_set.h>
int main()
{
leda::d_int_set DIS;
DIS.insert(1);
DIS.insert(200);
int i;
for (i=2; i<=99; i++) DIS.insert(2*i);
if (DIS.member(37)) std::cout << "37 is stored in S\n";
else std::cout << "37 is not an element of S\n";
if (DIS.member(168)) std::cout << "168 is stored in S\n";
else std::cout << "168 is not an element of S\n";
return 0;
}
Strengths
-
insert(), delete() need only constant time if the minimum and
maximum is not changed
- all operations are fast (data type uses parallelism at word level)
- data type is space efficient
- various set operations predefined
Disadvantages
- inserting a new minimum or maximum results in a reallocation operation
- restricted to ints (alternative: Sets)
Tips
- Use Dynamic Integer Sets instead of Integer
Sets if you do not know in advance the interval of the ints
you want to store.
- If you want to store objects other than int, consider using a Set,
a Linear List or a One
Dimensional Array.
- To avoid unnecessary reallocations store minimal and maximal element
first.
|
See also:
Integer Sets
Sets
Linear Lists
One Dimensional Arrays
Manual
page Dynamic Integer Sets
|