Re: [boost] Re: BOOST_NO_HASH

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
Ali
-- 
Albrecht Fritzsche, Software Developer
alfabet meta-modelling ag, 
leibnitzstr. 53, 10629 berlin, germany
http://www.alfabet.de