Why can't I store my objects in an unordered_set?

6
votes

I understand a set is ordered, thus adding an object without overloading the < operator doesn't allow to say which object is smaller to keep the container sorted. However, I don't understand why this isn't possible with an unordered_set.

If I try something like this:

#include <iostream>
#include <string
#include <unordered_set>

struct someType{
    string name;
    int code;
};

int main(){
    std::unordered_set <someType> myset;
    myset.insert({"aaa",123});
    myset.insert({"bbb",321});
    myset.insert({"ccc",213});
    return 0;
}

I get a couple of errors like:

c:\qt\qt5.1.0\tools\mingw48_32\lib\gcc\i686-w64-mingw32\4.8.0\include\c++\bits\hashtable_policy.h:1070: error: invalid use of incomplete type 'struct std::hash'

c:\qt\qt5.1.0\tools\mingw48_32\lib\gcc\i686-w64-mingw32\4.8.0\include\c++\bits\functional_hash.h:58: error: declaration of 'struct std::hash'

error: no matching function for call to 'std::unordered_set::unordered_set()'

c:\qt\qt5.1.0\tools\mingw48_32\lib\gcc\i686-w64-mingw32\4.8.0\include\c++\bits\hashtable_policy.h:1103: error: no match for call to '(const std::hash) (const someType&)'

c:\qt\qt5.1.0\tools\mingw48_32\lib\gcc\i686-w64-mingw32\4.8.0\include\c++\bits\stl_function.h:208: error: no match for 'operator==' (operand types are 'const someType' and 'const someType')

Why is that and how can I fix it?

2
c++c++11unordered-set
Can you post the exact code you're using and the exact error message? – templatetypedef
It seems unlikely that that's your actual error. Are you sure you aren't actually using a set? – Kerrek SB
No, it's an unordered_set. But you're right, that wasn't the exact error. I just edited to add complete code and more detailed error messages. Thanks :) – Vanessa Larralde
Possible duplicate of C++ unordered_map using a custom class type as the key – templatetypedef
Just as std::map requires operator< or a comparator, an unordered_map requires both operator== and a hash implementation. See this question for details. – templatetypedef

2 Answers

11
votes

To use type in unordered_set or unordered_map you need hashing function for your type. For common types, like int or std::string - hashing function is provided by standard library. For your type, you can overload standard std::hash, like this:

namespace std {
    template <> struct hash<someType> {
        size_t operator()(const someType & x) const {
            std::hash<std::string> h;
            return h(x.name);
            // or simply return x.code
            // or do something more interesting,
            // like xor'ing hashes from both members of struct
        }
    };
}

Another way is to provide your own type with overloaded operator() and put it as hash template argument in unordered_set, like this:

struct someTypeHasher {
    size_t operator()(const someType& x) const {
        return x.code;
    }
};
std::unordered_set<someType, someTypeHasher> myset;

Good reading for theory about hash based containers is here

Also, do not forget, that you need to overload operator== for someType, without it - it will also not work.

1
votes

As explained in the answer given by Starl1ght, you need to provide a hash function for someType. However, I would combine all members of your class by that hash function. Otherwise, you might get a lot of collisions, for example, if the same name occurs very often, but with different code values. For creating a hash function, you can make use of Boost, but you can also handcraft it.

Starl1ght also mentioned that you need to overload operator== for someType, but you can also define a separate comparison function instead and provide it to the unordered_set. Moreover, you can use lambda expressions instead of defining the hash and comparison functions. If you put everything together, then your code could be written as follows:

auto hash = [](const someType& st){
    return std::hash<std::string>()(st.name) * 31 + std::hash<int>()(st.code);
};
auto equal = [](const someType& st1, const someType& st2){
    return st1.name == st2.name && st1.code == st2.code;
};
std::unordered_set<someType, decltype(hash), decltype(equal)> myset(8, hash, equal);

Code on Ideone