From: Albrecht Fritzsche (albrecht.fritzsche_at_[hidden])
Date: 2001-01-10 04:39:07
Howard Hinnant wrote:
> Design A ... Now insert an entry at buckets_. Now (I would
> guess) the first half of the buckets_ list needs to point at the
> beginning of the list. So in a worst case, insert complexity is
> on the order of buckets_.size().
> Design B on the other hand is more efficient at insert/erase, even when
> the buckets_ is empty (constant complexity). But iteration can become
> expensive on a large but empty buckets_ list (linear complexity).
> Depending upon your feelings about favoring design A or B (favoring
> iteration vs insert/erase), the second design decision will probably fall
> into place more easily: Do you favor iteration (being able to iterate
> backward), or do you favor smaller overhead (which may lead to faster
> find/insert/erase due to cache hits)?
Correct me if I'm wrong but I thought the main point in favour of
hash tables is the insertion/removal/find in constant time. Hence
Design A would not allow to meet this "requirement". If the traversal
through the container is more important as the constant time insertion/
retrieval than you should/might use another container.
Hence I would be surprised to use a hash with insert complexity at
buckets_.size(), but not with one having a buckets_.size() complexity
for traversing sparsely populated hashes. For accelerating the latter
you still might use a cursor table onto the populated buckets say as
long as just a third of those is populated.
Just my opinion
-- Albrecht Fritzsche, Software Developer alfabet meta-modelling ag, leibnitzstr. 53, 10629 berlin, germany http://www.alfabet.de
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk