Problem 6.2 Fast Sets Using Bit Vectors

Introduction

In this problem, you will implement a FastSet class using a bit vector. A FastSet allows efficient storage and lookup of numbers from a given range [0, N]. Unlike traditional data structures such as hash tables or arrays, a bit vector provides a space-efficient and cache-friendly way to store and operate on sets of numbers.

Objective

Implement a C++ class FastSet that supports the following set operations:

• Insert an element into the set.
• Remove an element from the set.
• Compute the union of two sets.
• Compute the intersection of two sets.
• Check if an element is a member of the set.

Implementation

A FastSet is implemented using a bit vector, where each number x is represented by setting the bit at index x. This allows for O(1) insertions, deletions, and lookups.

Union and intersection of two sets

The union of two sets \( A \) and \( B \) results in a set containing all elements that are in either \( A \) or \( B \). This can be computed using a bitwise OR operation:

In terms of bit vectors, we iterate over each block of 32-bit integers and apply the OR operation:

This operation runs in O(N/32) = O(N) time and is much faster than a traditional array-based implementation which would require multiple passes of the array.

Similarly, you can implement other set operations efficiently.

The following code contains the class definition (to be implemented by you) and a main function for testing.