Sign in to follow this  
chrisjubb

STL map and SHA1 hash

Recommended Posts

I'm trying to create a hash map using the STL map class and SHA1 for hashing objects. SHA1 produces a 160bit/20byte hash (stored in an array of 5 unsigned ints). The STL map requires me to write a "less than" comparison so that it knows where to insert new elements into the tree. My question is how do I compare the 160bit hashes?

Share this post


Link to post
Share on other sites
Your question is moot, because std::map is usually implemented in terms of balanced trees, and is not a hash map.

You're looking for std::hash_map, a non-standard extension container. This is also in TR1/will be in C++0x as std::tr1::unordered_map. You could also use boost's boost::unordered_map.


EDIT: I just noticed you said "into the tree" in your post.. do you mean you really do want a std::map-based version?

If so, the easiest way would be to put the 20B hashes into a std::string for the keys. This way you already have the necessary comparison already implemented (as std::less<std::string>, i.e. operator< on std::strings.)

If you don't want the overhead std::string would give, you could use an explicit lexicographical comparison:


#include <map>
#include <algorithm>

struct SHA1 {
char hash[20];
};

bool operator<(const SHA1& l, const SHA1& r) {
return std::lexicographical_compare(l.hash, l.hash + 20, r.hash, r.hash + 20);
}

typedef std::map<SHA1, std::string> MyMap;



[Edited by - mattd on February 17, 2010 6:45:05 AM]

Share this post


Link to post
Share on other sites

class HashPredicate
{
public:
bool operator(const Hash& lhs, const Hash& rhs)
{
int diff = lhs[0] - rhs[0];
if(diff == 0)
{
diff = lhs[1] - rhs[1];
if(diff == 0)
{
...
}
}

return diff < 0;
}
};

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this