Re: [boost] Re: [multi_index][hash][rfc] Hashed indices preview+Boost.Hash

From: JOAQUIN LOPEZ MU?Z (joaquin_at_[hidden])
Date: 2005-02-20 15:57:17

----- Mensaje original -----
De: Daniel James <daniel_at_[hidden]>
Fecha: Domingo, Febrero 20, 2005 7:53 pm
Asunto: [boost] Re: [multi_index][hash][rfc] Hashed indices	preview
        +Boost.Hash

> JOAQUIN LOPEZ MU?Z wrote:
> > The implementation I adopted (2 pointers per node + 2 pointers
> > per bucket) has O(1) iteration, insert() and erase(), whatever
> > the load conditions (provided the hash function behaves, of
> > course.) I agree with you bidirectional iteration is of little
> > value, and my main motivation was to achieve O(1). So, I'll be
> > happy to go for a lighter implementation if these issues
> > can be solved in another way --or if there's consensum that
> > costly iteration under low load conditions is acceptable.
> 
> FWIW, if you can find a spare bit in a pointer, I've thought of a 
> non-portable way to get something closer to O(1) without the extra 
> memory load. The nodes are stored in a singly-linked list which 
> includes 
> the buckets, so the last node in a bucket points to the next 
> bucket. The 
> spare bit is used to indicate if a pointer is pointing to a node 
> or a 
> bucket. So the data structure is something like:
> 
[...]

Hi Daniel,

We can get rid of the spare bit if only iterators store
a pointer to the container: then we can test whether a 
pointer points to a true element or a bucket just by
checking if it is in the range
[buckets.begin(),buckets.end()). Still constant, though
admittedly slower than the bit thing.

Main problem with this is, as you point out, that traces
of empty buckets will be left when erasing. Still, it
seems somewhat better than the classic implementation,
at least wrt to theoretical complexity (in practice it'd
probably be significantly slower.)

Joaquín M López Muñoz
Telefónica, Investigación y Desarrpññp