Boost logo

Boost :

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_[500]. 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

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