Multi keys for same struct, but not ordered

help
1

See similar question:

I want to do much the same thing. So I tried "shortcut", which is a very simple in-memory database. This would do exactly what I want, except that it requires the keys to be ordered; that is, they must have the "Ord" trait. Not because I want to look up with ">", but because "shortcut" uses a tree structure that needs order. Unfortunately, one of my keys is an opaque handle (the ID of something down inside a GPU) that has "Eq" and "Hash", traits, so it can be used in a hash, but not "Ord".

Is there anything like "shortcut" that doesn't need partial ordering over the keys?

Yes, I know I can write this sort of thing with multiple hashes, but if there's a crate, I don't have to. I'll have other objects like this, and a general solution is helpful.

2

A somewhat ugly solution that immediately pops to mind is that you could create your own struct that has the handle as its only member (which is a zero-cost abstraction), and then implement Ord yourself by comparing the hashes of the handles. That would look something like this:

use std::cmp::Ordering;
use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};

#[derive(Eq, PartialEq)]
struct S<T>(pub T);

impl<T: Hash + Eq> Ord for S<T> {
    fn cmp(&self, other: &S<T>) -> Ordering {
        hash(&self.0).cmp(&hash(&other.0))
    }
}

impl<T: Hash + Eq> PartialOrd for S<T> {
    fn partial_cmp(&self, other: &S<T>) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

fn hash<T: Hash>(t: &T) -> u64 {
    let mut s = DefaultHasher::new();
    t.hash(&mut s);
    s.finish()
}

This gives you a type that fits the trait bound you described. I'm not sure that the performance will be that great, it might be improved by storing the hash as a second value in the struct so it's only calculated once, or that might make things worse. I'll leave that one up to you to play around with. Hope this solves your problem.

3

Thanks. That's kind of clunky, but it could work. I could also use two hashmaps, and my own code to keep them in sync, but I was hoping for a nice off the shelf solution.

4

multi-map exists; I haven't used it and not wildly popular (i.e. battle tested), but you could review it if nothing else.

5

Good idea, messed up crates.io entry. I saw that before, but "no README" made me think it was dead.

It looks like it used to be at

"GitHub - rust-embedded-community/multi-map: Like a Rust std: :HashMap, but allows you to use either of two different keys to retrieve items."

which now redirects to

which has a README, but crates.io didn't pick up the new README or documentation links.

6

Ah, good find. I found it on docs.rs (I think, maybe libs.rs) but like to link to crates.io so that the download stats and whatnot can be easily seen.

7

I would probably use two HashMaps for the two keys and a SlotMap for the values. (And store the keys to the SlotMap in the HashMap.)

That being said, if you just want to look values up and those values are small, duplicating them is indeed more efficient.

8

Multi-map worked for me. Despite the documentation link problem in crates.io that makes it look broken, importing it via Cargo.toml works fine. Thanks, all.