Jump to content
  • Advertisement
Sign in to follow this  
chrisjubb

STL map and SHA1 hash

This topic is 3043 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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
mattd - yes it looks like the hash_map is the more appropriate structure to use. Thanks for your detailed reply.
Ferneu - thanks for that code - will probably need it in the future.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!