C++ std::unordered_map key custom hashing

Question

I've got the following test.cpp file

#include <string>
#include <functional>
#include <unordered_map>
#include <iostream>

class Mystuff {
public:
   std::string key1;
   int key2;
public:
    Mystuff(std::string _key1, int _key2) 
        : key1(_key1)
        , key2(_key2)
    {}
};

namespace std {
template<>
struct hash<Mystuff *> {
    size_t operator()(Mystuff * const& any) const {
        size_t hashres = std::hash<std::string>()(any->key1);
        hashres ^= std::hash<int>()(any->key2);
        std::cout << "Hash for find/insert is [" << hashres << "]" << std::endl;
        return (hashres);
    }
};
}; /* eof namespace std */

typedef std::unordered_map<Mystuff *, Mystuff *>mystuff_map_t;

mystuff_map_t map;

int insert_if_not_there(Mystuff * stuff) {
    std::cout << "Trying insert for " << stuff->key1 << std::endl;
    if (map.find(stuff) != map.end()) {
        std::cout << "It's there already..." << std::endl;
        return (-1);
    } else {
        map[stuff] = stuff;
        std::cout << "Worked..."  << std::endl;
    }
    return (0);
}

int main(){
    Mystuff first("first", 1);
    Mystuff second("second", 2);
    Mystuff third("third", 3);
    Mystuff third_duplicate("third", 3);

    insert_if_not_there(&first);
    insert_if_not_there(&second);
    insert_if_not_there(&third);
    insert_if_not_there(&third_duplicate);

}

You can compile with g++ -o test test.cpp -std=gnu++11.

I don't get what I'm doing wrong with it: the hash keying algorithm is definitely working, but for some reason (which is obviously in the - bad - way I'm doing something), third_duplicate is inserted as well in the map, while I'd wish it wasn't.

What am I doing wrong?

user180247 · Accepted Answer · 2016-12-14 12:11:25Z

1

IIRC unordered containers need operator== as well as std::hash. Without it, I'd expect a compilation error. Except that your key is actually MyStuff* - the pointer, not the value.

That means you get the duplicate key stored as a separate item because it's actually not, to unordered_map, a real duplicate - it has a different address, and address equality is how unordered_map is judging equality.

Simple solution - use std::unordered_map<Mystuff,Mystuff> instead. You will need to overload operator== (or there's IIRC some alternative template, similar to std::hash, that you can specialize). You'll also need to change your std::hash to also accept the value rather than the pointer.

Don't over-use pointers in C++, especially not raw pointers. For pass-by-reference, prefer references to pointers (that's a C++-specific meaning of "reference" vs. "pointer"). For containers, the normal default is to use the type directly for content, though there are cases where you might want a pointer (or a smart pointer) instead.

I haven't thoroughly checked your code - there may be more issues than I caught.

answered Dec 14, 2016 at 12:11

user180247

Sign up to request clarification or add additional context in comments.

3 Comments

Riccardo Manfrin Over a year ago

I belive you did point out the issue .. please confirm my thoughts: you just cannot define things like bool operator==(Mystuff*, Mystuff*) because must have an argument of class or enumerated type. Motivation is that by defining the above, you're denying the ability to compare by the actual pointer's address value, which is required for example on insert key collision within a map. In facts, what is happening in my sample is exactly that the hash keys match, and therefore, the insert function compares the objects by they address and inserts them regardless the key match.

user180247 Over a year ago

@RiccardoManfrin - you can't define bool operator==(MyStuff*,MyStuff*) because it already exists. It compares the pointers - ie addresses - for equality. Comparison of pointers is inherited from C, and happens the same for all pointer types, even those that can't exist in C. What you need to define is either bool operator==(MyStuff,MyStuff) or bool operator==(const MyStuff&,const MyStuff&) - equality on the values, either passing by value or passing by const-reference.

user180247 Over a year ago

All arguments in C++ are passed by value. When you pass a pointer, you are passing the pointer by value - the function should be seen as working with the pointer, and only via indirection potentially with the pointed-to value. Even reference parameters are values of reference types passed by value, but you aren't working directly with the reference (because its self-dereferencing), so it makes more intuitive sense to think of it as passing the value by reference. It's not strictly true, though - reference types can be for other things, and using them for parameters doesn't do anything special.

Collectives™ on Stack Overflow

C++ std::unordered_map key custom hashing

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related