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@chemcon.no> 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@yahoogroups.com>
Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service <http://docs.yahoo.com/info/terms/>.