#include <userver/utils/filter_bloom.hpp>
Space-efficient probabilistic data structure.
Used to test whether a count number of a given element is smaller than a given threshold when a sequence of elements is given. As a generalized form of Bloom filter, false positive matches are possible, but false negatives are not.
T | the type of element that counts |
Counter | the type of counter |
Hash1 | the first callable hash struct |
Hash2 | the second callable hash struct |
Example:
Definition at line 38 of file filter_bloom.hpp.
Public Member Functions | |
FilterBloom (std::size_t counters_num=256, Hash1 hash_1=Hash1{}, Hash2 hash_2=Hash2{}) | |
Constructs filter Bloom with the specified number of counters. | |
void | Increment (const T &item) |
Increments the smallest item counters. | |
Counter | Estimate (const T &item) const |
Returns the value of the smallest item counter. | |
bool | Has (const T &item) const |
Checks that all counters of the item have been incremented. | |
void | Clear () |
Resets all counters. | |
|
inlineexplicit |
Constructs filter Bloom with the specified number of counters.
Definition at line 43 of file filter_bloom.hpp.
void utils::FilterBloom< T, Counter, Hash1, Hash2 >::Clear | ( | ) |
Resets all counters.
Definition at line 141 of file filter_bloom.hpp.
Counter utils::FilterBloom< T, Counter, Hash1, Hash2 >::Estimate | ( | const T & | item | ) | const |
Returns the value of the smallest item counter.
Definition at line 129 of file filter_bloom.hpp.
bool utils::FilterBloom< T, Counter, Hash1, Hash2 >::Has | ( | const T & | item | ) | const |
Checks that all counters of the item have been incremented.
Definition at line 136 of file filter_bloom.hpp.
void utils::FilterBloom< T, Counter, Hash1, Hash2 >::Increment | ( | const T & | item | ) |
Increments the smallest item counters.
Definition at line 113 of file filter_bloom.hpp.