Re: [boost] Interest in a Bloom Filter?

Subject: Re: [boost] Interest in a Bloom Filter?
From: Dean Michael Berris (mikhailberis_at_[hidden])
Date: 2009-06-08 02:55:55

On Mon, Jun 8, 2009 at 2:47 PM, Joaquin M Lopez Munoz<joaquin_at_[hidden]> wrote:
> Dean Michael Berris <mikhailberis <at> gmail.com> writes:
>
>>
>> Attached is what I came up with which I'm submitting as a library for
>> review (and uploading to the vault). Also attached is a sample program
>> which uses the bloom_filter.
>
> I'm definitely interested in having a Bloom filter in
> Boost.
>

This sounds encouraging! :-)

> A couple of comments on your current implementation:
>
> * Seems to me it is more natural (or at least more in sync
> with current custom in std containers) to let the order of
> bloom_filter template parameters be
>
> Â Input,M,K
>

Right. That's something that can easily be changed. ;-)

> * Why not make bloom_filter<M,K,T> interface mimic that
> of a std::map<T,bool> so that instead of
>
> Â bf.contains(x)
>

This can be retained though, for semantic purposes.

> one can write
>
> Â bf[x] // returns a bool
>

I like this. :-)

> Admittedly, one cannot extend this analogy to insertion:
> bf[x]=true could represent bf.insert(x), but bf[x]=false
> is not implementable due to the very nature of Bloom
> filters.
>

Right. I think though that once you know that something is a bloom
filter, you might very well use insert() -- if the operator[] overload
returns a bool, I'm not sure how the above code would compile.

> * Again with the purpose of using as standard a
> terminology as possible I'd rename reset() to clear().
>

I borrowed reset() from std::bitset -- although I agree clear() is
better terminology.

> * state() should return a const reference to bit_set so
> as to avoid copying when not strictly needed.

I was torn with this one, but I agree that this would be a sane
solution. I was worrying about the user doing a const_cast<> and then
doing something stupid with the internal data structure, but then I
guess all bets are off once that happens. ;-)

Thanks for your insights! I'll make the changes and then maybe put it
in the sandbox along with the documentation that I'll be working on.

Have a great day!

-- 
Dean Michael Berris | Software Engineer, Friendster, Inc.
blog.cplusplus-soup.com | twitter.com/mikhailberis |
linkedin.com/in/mikhailberis | profiles.friendster.com/mikhailberis |
deanberris.com