Is MultiIndex right for me?
Hello everyone, 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. I was wondering if boost might be handy here. Thanks & Cheers!
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); }
On 7/22/13 7:47pm, Daniel James wrote:
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.
Thanks Daniel. I have a question, though. Forgive me if I'm being too naive, but I'm trying to understand what's going on here! :) The code you posted seems to be bound at compile time to the integer p chosen as modulus (i.e., 53). How can I, for instance, find all values that are equal modulo 2 now, without instantiating another unordered_map? Finding elements modulo p, with p given at runtime, is the "something" I'm trying to do here :) The reason I was looking into MultiIndex is this: decoupling the hashing from the actual "equal" predicate. Thanks for any hints!
On Tue, 23 Jul 2013, at 10:10 AM, Sensei wrote:
On 7/22/13 7:47pm, Daniel James wrote:
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.
Thanks Daniel. I have a question, though. Forgive me if I'm being too naive, but I'm trying to understand what's going on here! :)
The code you posted seems to be bound at compile time to the integer p chosen as modulus (i.e., 53).
The modulus is bound at construction, you can also overwrite it by assignment or swapping.
How can I, for instance, find all values that are equal modulo 2 now, without instantiating another unordered_map? Finding elements modulo p, with p given at runtime, is the "something" I'm trying to do here :)
Currently, you'd need to create a new unordered_multimap, e.g. typedef std::unordered_multimap<int, int, modulo_hash, modulo_equals> multimap; multimap x1(0, modulo_hash(2), modulo_equals(2)); // Insert some values into x1 here. // .... // Copy elements into new container using a different modulo: multimap x2(x1.begin(), x1.end(), x1.bucket_count(), modulo_hash(p), modulo_equals(p)); // Can now swap x1 and x2 to get the newly hashed values in x1: x1.swap(x2); By the way, that '0' and 'x1.bucket_count()' specify the minimum number of buckets to create. I could possibly extend the boost implementation to allow you to change the hash and equal functions (they'd have to have the same type, but could have different values). It would have to rehash all the nodes, but would avoid having to allocate any new one. So the example becomes: typedef boost::unordered_multimap<int, int, modulo_hash, modulo_equals> multimap; multimap x1(0, modulo_hash(2), modulo_equals(2)); // Insert some values into x1 here. // .... x1.set_hash_and_equals(modulo_hash(p), modulo_equals(p));
The reason I was looking into MultiIndex is this: decoupling the hashing from the actual "equal" predicate.
You can't decouple the hash and the equal predicate - they must always match. I suppose using a modulo hash and normal equality is sort of okay, since you will get equal hash values for equal elements, but you might get very poor performance and you won't be able to assume that unequal hash values will map to different buckets - even if the number of buckets is greater than the number of hash values.
participants (2)
-
Daniel James -
Sensei