This example works well for raw data but not for complex types. You could make the filter a template, taking the key and a "hasher" function as template args.
I don't use c++ so I'm not sure how std:hash works or gets implemented, but the way that guava (Google's java library) does it is by passing in a key and a funnel object. The funnel object is essentially responsible for decomposing the object into a byte stream. The advantage of doing it this way rather than making the caller specify his own hash is that you can use murmurhash3 which you thought had the best properties for the bloom filter.
What's wrong with vector<bool> (other than its name)? The interface is exactly what you need to implement a bit-level abstraction in a language where this isn't a first-class primitive.
Minor nit: it will save readers time if you call out that "p is the false positive error rate". (You reference the error rate, but don't attach a variable name to it.) I had to go to an external reference to figure that out, which meant I learned something else of course.
20 comments
[ 3.2 ms ] story [ 52.3 ms ] threadtemplate< class Key, class Hash = std::hash<Key> > class BloomFilter;
This proposal decouples the implementation of hash functions from how types get hashed.
[1] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n398...
[0] - https://github.com/EricLagergren/bloom [1] - https://github.com/EricLagergren/bloom-c
The Bitcoin codebase has a simple Bloom filter implementation you can take a look at that has been in use for some time
https://github.com/bitcoin/bitcoin/blob/master/src/bloom.h
https://github.com/bitcoin/bitcoin/blob/master/src/bloom.cpp
Minor nit: it will save readers time if you call out that "p is the false positive error rate". (You reference the error rate, but don't attach a variable name to it.) I had to go to an external reference to figure that out, which meant I learned something else of course.
https://github.com/armon/bloomd