All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Member Functions | List of all members
Aux::SetIntersector< T > Class Template Reference

Provides set intersection for sets with entries from 0 to an upper bound (exclusive). More...

#include <SetIntersector.h>

Public Member Functions

 SetIntersector (T upperBound)
 
std::set< T > intersect (const std::vector< T > &A, const std::vector< T > &B)
 

Detailed Description

template<class T>
class Aux::SetIntersector< T >

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.

Constructor & Destructor Documentation

template<class T >
Aux::SetIntersector< T >::SetIntersector ( upperBound)
inline
Parameters
upperBoundExclusive upper bound for IDs of set members.

Member Function Documentation

template<class T >
std::set< T > Aux::SetIntersector< T >::intersect ( const std::vector< T > &  A,
const std::vector< T > &  B 
)
inline
Returns
Intersection of sets provided in A and B.

The documentation for this class was generated from the following file: