Template Class SetIntersector¶

Class Documentation¶

template<class T>
class SetIntersector¶

Provides set intersection for sets with entries from 0 to an upper bound (exclusive). Preprocessing time: Linear time for object creation (creates a bit vector of size upperBound. Query time: O(|A|+|B|) for two sets A and B. Space complexity: upperBound + 64 bits.

Public Functions

inline SetIntersector(T upperBound)¶

Parameters:

upperBound – Exclusive upper bound for IDs of set members.

inline std::set<T> intersect(const std::vector<T> &A, const std::vector<T> &B)¶

Returns:

Intersection of sets provided in A and B.