Sparse Sets with O(1) insert, delete operations and (sub)linear union, intersection

The paper An efficient representation for sparse sets (1993) by Preston Briggs, Linda Torczon, introduces an efficient data structure for representing a sparse static set (with u elements inserted out of a maximum of n elements). Insert and delete operations have a constant time complexity, while union and intersection are (sub)-linear in n. The space complexity is linear in n. The table on the right side compares the complexity of this data structure with a traditional bit vector.

The key intuition is to maintain two vectors such that dense[sparse[k]] = k, and a variable which maintains the number of elements in the sparse set. sparse[k] contains the number of elements in the set, when element k is inserted. In this way two elements inserted consecutively are mapped into contiguous positions of the dense vector. As a consequence, insert and delete operations are constant, while intersection and union operations are sub-linear.

This is the code for Sparse Sets representation in C++.