That’s a bit unusual trip to side roads for me. I’ve been working with C++ for many years and considered myself pretty experienced with STL containers. I remembered (I thought) how to extend a class so. C++ is a language that does not forgive hiatuses. My approach to custom hash function was similar to what highest ranking answer in this stackoverflow answer is showing:<\/p>\n
http:\/\/stackoverflow.com\/questions\/647967\/how-to-extend-stdtr1hash-for-custom-types<\/p>\n
First of all, it’s a bit outdated, because with introduction of C++11 tr1 namespace became obsolete. Secondly, to my shame, I was unable to make my example compile. So after some head scratching, I decided to go for even simpler solution. It may be not as beautiful as what you can find in C++ books, but it works. So here it is.<\/p>\n
Our sample class looks like this:<\/p>\n
struct Square\r\n{\r\nunsigned long long x;\r\nunsigned long long y;\r\n\r\nSquare(unsigned long long _x, unsigned long long _y) : x(_x), y(_y) {};\r\n};\r\n<\/pre>\nTo make class work with STL containers like map and set you need to implement a method returning a hash value of the object.<\/p>\n
struct SquareHash\r\n{\r\nsize_t operator() (const Square& square) const\r\n{\r\nreturn square.y * 1000 + square.y;\r\n}\r\n};\r\n<\/pre>\nBesides that you either need to implement a function that compares two values. In case of regular std::map or std::set it should be “<” and in case of unordered_map and unordered_set – “==”. You can do it by implementing an operator< or operator== for operands of your custom class, but I found it even clearer syntactically to implement a class:<\/p>\n
struct SquareEqual\r\n{\r\nbool operator() (const Square& lhs, const Square& rhs) const\r\n{\r\nreturn (lhs.x == rhs.x) && (lhs.y == rhs.y);\r\n}\r\n};<\/pre>\nJust in case, look at unordered_map declaration:<\/p>\n
template < class Key, \/\/ unordered_map::key_type\r\nclass T, \/\/ unordered_map::mapped_type\r\nclass Hash = hash, \/\/ unordered_map::hasher\r\nclass Pred = equal_to, \/\/ unordered_map::key_equal\r\nclass Alloc = allocator < pair<const Key,T> >\/\/ unordered_map::allocator_type\r\nclass unordered_map;<\/pre>\nThat’s it! Now you can declare an unordered_map:<\/p>\n
unordered_set <Square, SquareHash, SquareEqual> visitedSquares;<\/pre>\n","protected":false},"excerpt":{"rendered":"That’s a bit unusual trip to side roads for me. I’ve been working with C++ for many years and considered myself pretty experienced with STL containers. I remembered (I thought) how to extend a class so. C++ is a language … Continue reading