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