# STL map and SHA1 hash

## Recommended Posts

chrisjubb    100
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 on other sites
mattd    1078
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 on other sites
Ferneu    100
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 on other sites
chrisjubb    100
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 on other sites
mattd    1078
(Just to point out, Ferneu's code there is actually doing the same thing as std::lexicographical_compare.)