Boost logo

Boost :

From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2007-06-11 10:43:32

Hi Yoni,

Yoni Lavi wrote:
> I hope I'm posting it to the correct newsgroup. I wanted to mail this
> directly to the developer of boost::intrusive (Ion Gazta?aga), but I can't
> find his e-mail anywhere, or any way to directly report the bug. I am not a
> boost developer myself.

Posting to the boost.users or boost.devel newsgroups is a very effective
way to report bugs.

> Position of a contained element modulo m (new_buckets_len) is known to
> remain equal to its previous position modulo n (old_buckets_len) ONLY IF m <
> n AND n %m == 0, but the latter condition isn't being checked. The code
> assumes it can skip rehashing of m first buckets if m < n:

Thanks for reporting this.

> Please correct me if I'm wrong on this.. but just to be sure, I made a test
> program that verified rehash() can break the container's invariants when
> shrinking the container in place, which was indeed found to be the case.

You are right. Take for instance integer values with trivial hash
(bucket_count() == 5):

{0, 5}, {11}, {}, {3}, {9}

Now if we rehash it to bucket bucket_count() == 2, it should lead to
something similar to:

{0}, {5, 3, 9}

Which means that the element with value 5 must be rehashed.

> As a totally unrelated note, I don't understand why iunordered_set doesn't
> support a default constructor (so that buckets = 0 and num_buckets = 0,
> given the existence of a rehash() function. I see it like the reset()
> function in a scoped_ptr. If a "reset" style function is supported, the
> class shouldn't force you to initialize it at construction time. Then again,
> it's a matter of taste in design more than anything...

I have no problem to add it. Maybe the programmer wants to delay
resource/bucket allocation and a default constructor can be handy. But
constructs a container where no value can be inserted, and this seems
dangerous. I could add several assertions to catch such errors in debug
mode but, let me think about it a bit more.

Thanks again for the report,


Boost list run by bdawes at, gregod at, cpdaniel at, john at