An unordered set of structs

Question

I have been trying to make an unordered_set of structs in c++ but it seems to give me this error-

error: call to implicitly-deleted default constructor
      of 'std::__1::hash<coor>'
  __compressed_pair_elem(__default_init_tag) {}

I included a == operator, can assist me in making a unordered_set of structures?

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;
struct coor{
    int x,y;
    bool operator==(coor a) const{
        if(a.x == x && a.y == y){
            return true;
        }
        else return false;
    };
};
int main(){
    unordered_set<coor> myset;
}

Answer 1

Many people use the solution given in the cppreference. Please see here.

But they always open the std namespace and specialize the template for std::hash

Basically that is not necessary.

According to the definition of the std::unordered_set as defined here, we need a hash function and an equal function. And for the hash function we just need an operator().

So, we can make this easily as a part of our struct. We need to overide the ()-operator and implement the hash function. And then we need to override the ==-operator to get the equal function.

Then we add the our struct name as an additional template parameter.

In my humble opinion, it is better to encapsulate the hash and equal functions in our struct, because only this datatype should know, how to calculate values.

Please see here:

#include <unordered_set>
#include <vector>
#include <iostream>

struct coor {
    int x{}, y{};

    // Hash function
    size_t operator()(const coor& c) const { return std::hash<int>()(c.x) ^ std::hash<int>()(c.y); }
    // Equal Function
    bool operator==(const coor& other) const { return (x == other.x && y == other.y); }
    
};

int main() {

    // Some test values
    std::vector<coor> test{ {1,2}, {3,4}, {5,6}, {1,2} };

    // Define the unordered set anf fill it with test value
    std::unordered_set<coor, coor> myset(test.begin(), test.end());

    // Show result. There is no double value 1,2
    for (const coor& c : myset) std::cout << c.x << ' ' << c.y << '\n';

    return 0;
}

---

Of course you may also Lambdas as "free" functions for the hash and the equal.

In the following example, we will define 2 Lambdas, one for calculating the hash and one calculating the equal function.

Since the type of the Lambda is only known to the compiler, we use decltype in the template parameter, to inform the compiler, which function "type" we will use in the template.

As an example I defined variable definitions using all 5 available constructors. Please see here for the description.

Please note: You can always and everywhere delete the "myEqual" function, if you add the operator== to the struct as shown above.

Please see the next example below:

#include <unordered_set>
#include <vector>
#include <iostream>

struct coor {
    int x{}, y{};
};

constexpr size_t BucketCount = 20u;
int main() {
    // Hash function
    auto myHash = [](const coor& c) { return std::hash<int>()(c.x) ^ std::hash<int>()(c.y); };
    // Equal function
    auto myEqual = [](const coor& c1, const coor& c2) { return c1.x == c2.x && c1.y == c2.y; };

    // Constructor Number 1
    std::unordered_set<coor, decltype(myHash), decltype(myEqual)> myset1(BucketCount, myHash, myEqual);
    myset1.insert({ 1,2 }); myset1.insert({ 3,4 }); myset1.insert({ 5,6 }); myset1.insert({ 1,2 });

    // Constructor Number 2
    std::vector<coor> test{ {1,2}, {3,4}, {5,6}, {1,2} };// Some test values
    std::unordered_set<coor, decltype(myHash), decltype(myEqual)> myset2(test.begin(),test.end(), BucketCount, myHash, myEqual);

    // Constructor Number 3
    std::unordered_set<coor, decltype(myHash), decltype(myEqual)> myset3(myset2);

    // Constructor Number 4
    std::unordered_set<coor, decltype(myHash), decltype(myEqual)> mysetTemp(myset2);
    std::unordered_set<coor, decltype(myHash), decltype(myEqual)> myset4(std::move(mysetTemp));

    // Constructor Number 5
    std::unordered_set<coor, decltype(myHash), decltype(myEqual)> myset5({ {1,2}, {3,4}, {5,6}, {1,2} }, BucketCount, myHash, myEqual);

    // Show result. There is no double value 1,2
    for (const coor& c : myset1) std::cout << c.x << ' ' << c.y << '\n'; std::cout << '\n';
    for (const coor& c : myset2) std::cout << c.x << ' ' << c.y << '\n'; std::cout << '\n';
    for (const coor& c : myset3) std::cout << c.x << ' ' << c.y << '\n'; std::cout << '\n';
    for (const coor& c : myset4) std::cout << c.x << ' ' << c.y << '\n'; std::cout << '\n';
    for (const coor& c : myset5) std::cout << c.x << ' ' << c.y << '\n'; std::cout << '\n';
    return 0;
}

---

Developed compiled and tested with Microsoft Visual Studio Community 2019, Version 16.8.2

Additionally compiled and tested with gcc10 amnd clang 11

Language: C++17

---

If you have any questions to the above, then I am happy to answer

Answer 2

std::unordered_set uses hashes to identify objects uniquely. It computes the hash using std::hash<> structure. This is fine for primitive or STL containers as they have defined a hash structure for them. But for your case, there isn't a hash structure to generate the hash. The error says it: std::__1::hash<coor>.

To resolve this, we need to implement a std::hash<> for coor.

namespace std {
    template<>
    struct hash<coor> {
        const size_t operator()(const coor& c) const
        {
            return std::hash<int>()(c.x) ^ std::hash<int>()(c.y);   
        }
    };
}

Now the std::unordered_set has the required hash structure to compute the hash.