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