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

From: Daniel James (daniel_at_[hidden])
Date: 2005-02-20 16:56:04

JOAQUIN LOPEZ MU?Z wrote:

> 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.

I had thought of that, but dismissed it as too slow. But on second 
thoughts, maybe you could say:

     bool is_bucket(node_or_bucket* ptr) const {
         return static_cast<std::size_t>(ptr - buckets_) < bucket_count_;
     }

I'm not sure how portable or fast/slow that would be.

> 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.)

Maybe not. The most important operation is a bucket lookup, here's the 
traditional single-linked implementation:

     node* ptr = bucket[i].head_;
     while(ptr && !key_equal_(get_key(*ptr), k))
         ptr = ptr->next;

This becomes:

     node* ptr = bucket[i].next_;
     while(!(ptr & 1) && !key_equal_(get_key(*ptr), k))
         ptr = ptr->next;

Which is pretty good. Iteration becomes faster (unless you have a lot of 
empty buckets), insert remains the same, erase suffers (unless you don't 
care about iteration).

I'm just comparing with a singly linked implementation, not doubly-linked.

Daniel