U64 -> T, T -> u64 w/o storing twice

We have T: Hash + Eq

Furthermore, we want to be able to maintain a set and do u64 -> T and T -> u64.

One way to do this is

pub struct Foo {
  a: HashMap<u64, T>,
  b: HashMap<T, u64>,
}

However, this requires storing every T twice. Is there a way to do this while storing each T only once ?

Arc<T>?

If T is small and cheap to copy (eg i32) then that's probably the best representation. If T is large/expensive to copy, then you could make it Foo<Arc<T>> - ie, make it a requirement in the API that T has a cheap Clone implementation (in time and space). Or just make it use Arc/Rc itself, though that will be much more expensive if T doesn't need it.

1 Like

Not without some extra indirection. But might as well leave that up to the caller -- if you require T: Clone then people can always pass Arc<Whatever> if they don't want multiple copies.

2 Likes

You may be interested in the bimap crate

2 Likes

This also sounds like a problem potentially solved by [internment] (https://crates.io/crates/internment), if you don't mind having an opaque pointer type instead of a u64. Depends on what you're trying to accomplish. Internment works by replacing the u64 with a pointer to T, which further requires a stable heap location for the T.

1 Like

If you don't need to control the actual u64 values, but just have them as cheap keys, then you might be able to work with usize in an IndexSet. You'll get a usize index from insert_full, or later you can look that up with get_index_of(&T). You can retrieve items with get_index(usize)/[usize] or get(&T).

1 Like

I got inspired by this post and here's my take at this problem (playground link),
let me know if you find any bug. Key points:

  • No unsafe code
  • Allocates only a Vec and 2 HashMaps. No Rcs needed
  • Requires nightly because of the currently unstable hash_raw_entry feature
2 Likes

You could use hashbrown directly to get stable raw_entry, or even use RawTable if you allow unsafe. The split storage is pretty close to how IndexMap works, for another reference.

1 Like

RawTable::get, RawTable::insert_entry and RawTable::remove_entry looks exactly like what I needed, and they're also safe! Here's the modified version playground link

2 Likes

Great! It happens that I added those safe methods myself in hashbrown#202, so I'm happy to see them get more use. :slightly_smiling_face:

1 Like