Quotient Filter

template<std::size_t F, std::size_t Q, template<typename...> class HF = mmh3_hash_factory, typename T = std::string, typename S = uint32_t>
class pdstl::quotient_filter : public pdstl::membership<T>

Quotient Filter.

quotient_filter class implements quotient filter algorithm for solving membership problem.

Template Parameters

  • F: - Fingerprint bits, must be smaller than or equal to hash output size

  • Q: - Number of bits for quotient part, remainder bit size is (F - Q)

  • HF: - Hash factory method class (default: pdstl::mmh3_hash_factory)

  • T: - Element type which will be inserted into quotient filter (default: std::string)

  • S: - Hash output type (default: uint32_t)

Public Functions

quotient_filter()

Default constructor.

void insert(const T &item) override

insert an item into quotient filter

Parameters

  • item: - the item to insert into the quotient filter.

void erase(const T &item) override

Erase is not supported in standard quotient filter. will throw an exception.

Parameters

  • item: - the item to erase from filter.

void clear() override

Clear filter and resets its internal memory.

bool contains(const T &item) const override

Check the item and report that it’s in the filter or not.

Return

false if the item is not in the filter, true if item may be in the filter.

Parameters

  • item: - the item to check for existence.