Re: [Boost-Users] Re: Efficient implementation of associative_property_map

From: Jeff Holle (jeff.holle_at_[hidden])
Date: 2003-03-12 17:08:00

Another caution. Hash containers are much more memory efficient than 
red/black implementations.
This can be significant with 600000 elements...
Don't remember the actual ratio but it somewhere like 3:1.

David Abrahams wrote:

> 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
>
>
> *Yahoo! Groups Sponsor*
> ADVERTISEMENT
> <http://rd.yahoo.com/M=246920.2960106.4328965.2848452/D=egroupweb/S=1705006788:HM/A=1481659/R=0/*http://www.gotomypc.com/u/tr/yh/cpm/grp/300_yh1/g22lp?Target=mm/g22lp.tmpl> 
>
>
>
> Info: <http://www.boost.org>
> Wiki: <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl>
> Unsubscribe: <mailto:boost-users-unsubscribe_at_[hidden]>
>
>
> Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service 
> <http://docs.yahoo.com/info/terms/>.