Boost logo

Boost :

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


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


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