Writing classes to be used with unordered_map.

Question

I want to use the boost map and the documentation says I need an equality function and a hash function. I think understand what they should do but since I can't find any examples I'm not sure how to do it so I am looking for a trivial example, like a point class with members x, y or something close.

Edit: Finally got it working. Wish I hadn't had to waste so much time for this. Thanks anyway guys.

#include <boost/functional/hash.hpp>
#include <boost/unordered_map.hpp>
#include <boost/foreach.hpp>
#include <iostream>

namespace test { // class whose source i can't edit
    class point
    {
    public:
        float x;
        float y;
        point() : x(0), y(0) {}
        point(int x, int y) : x(x), y(y) {}
        point(float x, float y) : x(x), y(y) {}
        point(double x, double y) : x((float) x), y((float) y) {}

        bool operator==(point const& other) const
        {
            return x == other.x && y == other.y;
        }
    };
}

namespace test { // my source file
    std::size_t hash_value(point const &p) {
        boost::hash<int> hasher;
        return hasher(p.x) + hasher(p.y);
    }
} 

int main() {
    boost::unordered_map<test::point, std::string> myMap;
    test::point p1(1, 2);
    myMap[p1] = "1"; //now it works
    std::cout << myMap[p1] << std::endl;
    return 0;
}

There are examples of this very scenario (a 2-d point class) in [the documentation](http://www.boost.org/doc/libs/1_46_0/doc/html/unordered/hash_equality.html). — James McNellis, Jul 30 '11 at 20:15
Are you interested also in using C++0x's `std::unordered_map` or the TR1 `std::tr1::unordered_map`? — Kerrek SB, Jul 30 '11 at 22:38
@Kerrek: C++0x is not 100% compatible with C++ in subtle ways. For a big project that is already using `boost` switching language just for this reason is IMO nonsense. — 6502, Jul 31 '11 at 05:23
6502: You could use TR1, which requires no change of language and is included in most modern compilers... — Kerrek SB, Jul 31 '11 at 09:56

score 3 · Accepted Answer · answered Jul 30 '11 at 20:15

3

Equality and hash aren't too tough to define. Equality:

class Point {
    int x, y;
    bool operator==(const Point& p) {
        return (x == p.x && y == p.y);
    }
};

Hashing tends to involve specializing a function or class.

template<> class boost::hash<Point> {
public:
    size_t operator()(const Point& p) {
        return boost::hash<int>(p.x) + boost::hash<int>(p.y);
    }
};

You may need to read up on the specifics of your hash_map implementation for details, and you may also want to define a different hash algorithm.

answered Jul 30 '11 at 20:15

Puppy

144,682
38
256
465

You need a separate class to implement the hash? Is there a reason for that? – problem Jul 30 '11 at 20:19
@problem: It's just a functor; it's nothing special. – Nicol Bolas Jul 30 '11 at 20:25
When I try to compile code using this example I get `specialization of ‘template struct boost::hash’ in different namespace`. Do I have to set namespaces to use this functor thing? There's an answer on stackoverflow about it but it's just an example without any explanation which I don't understand atm. – problem Jul 30 '11 at 21:29
you can either put your specialization functor inside std::tr1, or pass it as the third template argument to your container. If you don't know what functors are, start here http://stackoverflow.com/questions/356950/c-functors-and-their-uses – KarlM Jul 30 '11 at 22:34
1

Using sum gives a bad distribution in general... is both non uniform and symmetric. There is a specific `hash_combine` function that works better. – 6502 Jul 31 '11 at 05:19

score 3 · Answer 2 · answered Jul 30 '11 at 20:20

3

This is right from boost documentation...

class point
{
    int x;
    int y;
public:
    point() : x(0), y(0) {}
    point(int x, int y) : x(x), y(y) {}

    bool operator==(point const& other) const
    {
        return x == other.x && y == other.y;
    }
};

class point
{
    ...

    friend std::size_t hash_value(point const& p)
    {
        std::size_t seed = 0;
        boost::hash_combine(seed, p.x);
        boost::hash_combine(seed, p.y);

        return seed;
    }

    ...
};

answered Jul 30 '11 at 20:20

6502

112,025
15
165
265

Is there a situation when the seed shouldn't be 0? – problem Jul 30 '11 at 21:32
@problem - I dont think it matters what the seed is, as long as its always the same for all instances of the type. – Node Jul 31 '11 at 00:30
@problem: you can start from any value you like, but using `hash_combine` instead of `+` or `^` is slightly better because keeps a better distribution and the hash is not symmetric in XY (using sum or xor the points (a, b) and (b, a) end up with the same hash so if your input has this kind of symmetry the hash map will be slightly less efficient). – 6502 Jul 31 '11 at 05:17

Writing classes to be used with unordered_map.

2 Answers2