Re: [boost] Unordered Map/Set in VC++/Boost?

From: Daniel James (daniel_james_at_[hidden])
Date: 2007-05-20 15:07:44

Péter Szilágyi wrote:

> does boost or does it not contain the unordered_map, 

Boost doesn't currently have unordered containers. I'm going to ask for 
a review soon, but given the amount of time it's taken libraries to get 
into boost recently, don't hold your breath. The review won't be for a 
while and, if it's accepted, it'll have to wait for an appropriate 
release to be included. For now, you can get the work in progress from:

http://boost-consulting.com/vault/index.php?directory=Containers

It's called 'unordered.tar.gz'. It should be pretty reliable.

 > then anyone has any idea how I could use the boost hash class with the
 > VC++ (2005) hash_map class?

Looking at the MSDN documentation, boost::hash will have a couple of 
issues with Visual C++'s hash_map.

One is that Visual C++'s hash_map uses power of 2 sized buckets - while 
boost::hash is really designed to work with a container that uses a 
prime number of buckets. So if your key's hash values don't vary much in 
the lower bits you'll get a lot of collisions. Whether this is likely 
depends on your data, but you'll need to be careful.

The other issue is that while unordered_map uses an equality predicate 
to compare elements, Visual C++'s hash_map uses a 'less' predicate. 
Although, as long as the comparison is consistent with the hash value I 
think it should be okay.

But if you do want to use Boost.Hash, then you'll need to implement your 
own hash_compare which uses boost::hash. Here's a sketch of how this 
might be done - although, completely untested, as I'm using Linux at the 
moment.

template<class Key>
class my_hash_compare
{
     boost::hash<Key> hasher_;
public:
     const std::size_t bucket_size = 4;
     const std::size_t min_buckets = 8;
     hash_compare() : hasher_() {}
     std::size_t operator()(const Key& k) const {
         return hasher_(k);
     }
     bool operator()(const Key& k1, const Key& k2) const {
         return k1 < k2;
     }
};

stdext::hash_map<std::string, int, my_hash_compare<std::string> > map;

For more info on hash_compare see:

http://msdn2.microsoft.com/en-us/library/8zz3703d(VS.80).aspx

Hope that helps,

Daniel