Implement hash for custom class C++

Question

I have a circle defined like so:


class Circle {
public:
    int x;
    int y;
    int r;

    Circle() : x(0), y(0), r(0) {}

    Circle(int x, int y, int r) {
        this->x = x;
        this->y = y;
        this->r = r;
    }

    double area() {
        return PI * pow(r, 2);
    }
};

I want to be able to add it to a set, based on the hash of its center (x and y)

What's the correct and idiomatic way of doing this in C++ 11?

My question is two-fold

(1) Is there a way I can ask C++ to hash it for me? In Kotlin, there is the notion of a dataclass which automatically hashes the class attributes. I am looking for something similar.

(2) If not, how do I hash it myself, and relatedly - what are operators I need to overload?

@roottraveller there are several pitfalls associated with hash implementations; ensuring x == y implies hash(x) == hash(y) (and not the other way around), among others. It's easy to get the implementation wrong in a language you're unfamiliar with, and I wanted some guidance. You can suggest a link to a similar question; no one really cares for your snark. — nz_21, Nov 26 '19 at 22:10
Maybe use a [std::pair as the key in a map?](https://www.techiedelight.com/use-std-pair-key-std-unordered_map-cpp/) — Kai, Nov 26 '19 at 22:14
There are an infinite number of hash functions you could implement. — Jesper Juhl, Nov 26 '19 at 22:20
@roottraveller The Internet, just like everything else, is 90% crud. If you don't know enough of what you're looking for to tell the crud from the gems, you're 90% likely to learn from crud. Take care when suggesting people just jump into google for answers. nz_21, `std::pair` might be all you need, but without more details there's no way to be sure. — user4581301, Nov 26 '19 at 22:27
A side note about `pow`: It's designed to handle really nasty cases like pi to the power of e. Using to square a number is often much more expensive than `r*r`. — user4581301, Nov 26 '19 at 22:29
@nz_21 Are you asking how to define a custom hash function which is automatically used by e.g. `std::unordered_set` or are you asking what hashing algorithm is appropriate for this class? Also note that a "set", i.e. `std::set` does not require or use hashes, only `std::unordered_set` does. Why would you not include `r` in the hash as well? How is equality supposed to be defined for this class? — walnut, Nov 26 '19 at 22:51
You can provide [your own hashing algorithm](https://en.cppreference.com/w/cpp/utility/hash) for use with `std::unordered_set` or you can can implement a `operator<` or a [comparison function](https://en.cppreference.com/w/cpp/named_req/Compare) to use with `std::set`. — user4581301, Nov 26 '19 at 23:22
`std::pair` with `int` will use the `<` operators of its contained types and may be all you need with `std::set`. Give it a try and see. — user4581301, Nov 26 '19 at 23:24
Does this answer your question? [C++ unordered\_map using a custom class type as the key](https://stackoverflow.com/questions/17016175/c-unordered-map-using-a-custom-class-type-as-the-key) Note that `std::unordered_set` works the same way as `std::unordered_map`. Again, for `std::set` hashes are not required. — walnut, Nov 26 '19 at 23:28
https://en.cppreference.com/w/cpp/utility/hash You have an example there. Also https://stackoverflow.com/questions/2590677/how-do-i-combine-hash-values-in-c0x and https://stackoverflow.com/questions/17016175/c-unordered-map-using-a-custom-class-type-as-the-key Also be aware that `unordered_set` should be preffered unless you have reasons for needed `set` instead — bolov, Nov 26 '19 at 23:29

borievka · Answer 1 · 2019-11-26T23:33:47.853

I want to be able to add it to a set, based on the hash of its center (x and y)

If you wan't to put your circle in the std::set, you don't need to provide a hash function. You need to provide it only if you'd like to use std::unordered_set or any other unordered associative container (more info in hash).

As it goes for the most idiomatic way of implementation, I would go with something like this (taken from the std::hash example):

#include <cmath>
#include <unordered_set>
#include <set>

class Circle {
public:
    int x;
    int y;
    int r;

    Circle() : x(0), y(0), r(0) {}

    Circle(int x, int y, int r) {
        this->x = x;
        this->y = y;
        this->r = r;
    }

    double area() {
        return 3.1415 * pow(r, 2);
    }
};

bool operator==(const Circle& lhs, const Circle& rhs) {
    return lhs.x == rhs.x && lhs.y == rhs.y;
}

template<> struct std::hash<Circle> {
    std::size_t operator()(Circle const& s) const noexcept {
        std::size_t h1 = std::hash<int>{}(s.x);
        std::size_t h2 = std::hash<int>{}(s.y);
        return h1 ^ (h2 << 1); // or use boost::hash_combine (see Discussion) https://en.cppreference.com/w/Talk:cpp/utility/hash
    }
};

int main() {
    std::unordered_set<Circle> circles;
    return 0;
}

Link to example

EDIT:

(1) Is there a way I can ask C++ to hash it for me? In Kotlin, there is the notion of a dataclass which automatically hashes the class attributes. I am looking for something similar.

There is hash function for the basic types (list is on std::hash). You need to provide hashing function for your custom type. You can take an inspiration from the cppreference or create an own hashing function.

the op said he/she wants only `x` and `y` to participate – bolov Nov 26 '19 at 23:31 — bolov, Nov 26 '19 at 23:31

Implement hash for custom class C++

1 Answers1