If the elements of a set are non-negative integer numbers from a not too large interval, there is a particularly efficient representation for them: Every integer number is understood as the number of a bit and the set is implemented as an array of int in which the bit with the number i is set if and only if the number i is part of the set. Figure 2.28 shows such a representation of a set of integer numbers as a bit vector.

Figure 2.28. A set of integer numbers, realized as a bit vector

Every bit with value 1 corresponds to a number from the interval [0..31]. Here only one single int, that is 4 bytes, is needed to store 28 numbers.

In this representation, 0 does not necessarily have to be the lower bound of the interval. By a corresponding index arithmetic also negative integer numbers can be represented in a bit vector, of course.

This implementation saves space and time in contrast to a conventional array or list if the numbers are from a not too large range and many of these numbers belong to the set: If N is the size of the interval, then this structure needs approximately N/M ints on a machine on which the type int has M bits. The access to a single element is particularly fast: It is possible with a constant number of operations whereas one would have to search in an array or a list first.

For set representations of this type, LEDA offers the classes int_set and d_int_set. For the former class, the minimum and the maximum of the numbers to be stored must be known in advance and be specified at the definition. The second class comes in handy if this is not possible or not desired.

These classes do not offer any advantage if only few numbers are stored altogether or if the interval size N is very large. Then a set, an ordinary array or a list are rather worthwhile.