Re: [Boost-users] Is MultiIndex right for me?

Subject: Re: [Boost-users] Is MultiIndex right for me?
From: Daniel James (daniel_at_[hidden])
Date: 2013-07-22 13:47:08

On Mon, 22 Jul 2013, at 04:42 PM, Sensei wrote:
> 
> I was playing with std::unordered_multimap trying to achieve the
> following.
> 
> I need to store values in no particular order. I need to find, however, 
> all values (let's assume they are integers) that satisfy some given 
> criteria that is NOT the simple equality.
> 
> For example, I'd like to store integers, and find all integers that are 
> equal modulo p, for instance given two integers u, v, I may write the 
> equality predicate as return (u % p) == (v % p).
> 
> This requirement might change (at compile time, of course), for example, 
> in another map I'd like to find all integers that have a particular bit 
> set to 1.
> 
> 
> I tried, as I said, with std::unordered_multimap, but I was told 
> (correctly, AFAIK) that the ISO requires that items matching values MUST 
> match also with hash values.
> 
> Of course, in my case matching integers do not possess matching hashes.

You can use a custom hash function. Here's an example. I made the modulo
dynamic, but if it's a compile time constant, then the container will be
a tad bit smaller, and you won't need to pass the hash function and
equality predicate as parameters.

#include <unordered_map>
#include <cassert>

struct modulo_hash {
    int p;

    explicit modulo_hash(int p) : p(p) {}
    std::size_t operator()(int value) const {
        std::hash<int> hf;
        return hf(value % p);
    }
};

struct modulo_equals {
    int p;

    explicit modulo_equals(int p) : p(p) {}
    std::size_t operator()(int x, int y) const {
        return x % p == y % p;
    }
};

int main()
{
    std::unordered_multimap<int, int, modulo_hash, modulo_equals> x(
            0, modulo_hash(53), modulo_equals(53));
    x.insert(std::make_pair(54, 10));
    assert(x.find(1) == x.find(54));
    assert(x.find(1)->second == 10);

    x.insert(std::make_pair(57, 15));
    x.insert(std::make_pair(4, 13));
    assert(x.count(4) == 2);
}