2.9.2. If minimum or maximum are unknown (class d_int_set)

Learning objectives

The class d_int_set

To be able to use the class int_set, we must know maximum and minimum of the numbers to be stored in advance. However, there are situations in which this is not possible or in which their computation would mean too much overhead. The class d_int_set is of advantage in these cases. It enlarges its underlying bit vector automatically if the minimum or the maximum changes. So these values do not have to be specified at the definition.

Suppose it is not possible to read the file SomeInts.txt from the previous program example twice. So we must get by on one single pass over the numbers. This means that we cannot determine minimum and maximum in a first step in order to insert the numbers in an appropriately large int_set afterwards. We therefore use a d_int_set into which we immediately store every number at the first read. If we meet a new minimum or maximum, this class is clever enough to adjust its interval.

Filename: FastIntegerSortDynamic.C
LEDA users as of version 5.0: Note that header files are now partitioned into modules (subfolders)!
#include <LEDA/d_int_set.h>
#include <fstream>
#include <iostream>

using leda::d_int_set;

int main()
{
  std::ifstream is("Data/SomeInts.txt");

  int n;

  d_int_set S;
  
  while (is >> n) 
    S.insert(n);
  
  for(int i = S.min(); i <= S.max(); i++)
    if(S.member(i))
      std::cout << i << "\n";  
}

Unlike the class int_set, the constructor of d_int_set does not need the specification of minimum and maximum:

d_int_set S;

The class d_int_set has exactly the same, powerful interface as the class set and the efficiency of the class int_set. So the advantages of both latter classes can be combined if integer numbers must be stored.

Further information

The class d_int_set, like the class int_set, is implemented by bit vectors of C++. The running times of the individual operations are the same as those of the class int_set.

One finds more information about the class d_int_set on the corresponding manual page.




Imprint-Dataprotection