Re: Efficient implementation of associative_property_map

From: David Abrahams (dave_at_[hidden])
Date: 2003-03-08 08:56:55

Tarjei Knapstad <tarjeik_at_[hidden]> writes:

>> We don't have SGI STL around here. I've seen that before, but I hoped
>> that there would be an other way than changing my STL version... It's
>> amazing that there is no hashtable in the stdc++, isn't it?
>> 
> More or less... :) Hashed containers were introduced too late to make it
> into the standard IIRC, allthough most STL implementations have them and
> most STL books document them.

A caution: while hashtable lookups are theoretically O(1), it can be
very difficult in practice to come up with a hash function that will
cause a hashtable implementation to outperform a custom-built
associative data structure.  One thing I've used successfully is a
sorted vector of sorted vectors.  A couple of binary searches can be
very fast, and have nice locality properties if the vectors don't
grow too large.

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com