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

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 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=170500678...

Info: http://www.boost.org Wiki: http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl Unsubscribe: mailto:boost-users-unsubscribe@yahoogroups.com

Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service http://docs.yahoo.com/info/terms/.