3

Let's say I have a hashtable like this:

let table: HashMap<(usize, Vec<i32>), SomeStruct> = HashMap::new();

(in the actual application, the type is not Vec<i32> but is some other struct which is not Copy)

The key type is (usize, Vec<i32>). However, if I try to perform a lookup where I only have a (usize, &Vec<i32>), this is not allowed since HashMap::get requires Borrow<(usize, Vec<i32>)> which cannot be satisfied by (usize, &Vec<i32>).

The context looks something like this:

fn lookup(table: &mut HashMap<(usize, Vec<i32>), SomeStruct>, index: usize, vector: &Vec<i32>) {
  // Note the 'vector.clone()' - would like to avoid doing that
  if let Some(value) = table.get(&(index, vector.clone())) { 
    // ..
  }
}

Is there a way to avoid the .clone() when performing a lookup with this key type? I was thinking a struct wrapper type around the key type might allow me to write a custom implementation of Borrow but wasn't too sure if this was on the right track or how that would work.

Peter Hall
  • 53,120
  • 14
  • 139
  • 204
Joe the Person
  • 4,470
  • 3
  • 22
  • 32
  • 2
    [This answer](https://stackoverflow.com/a/45795699/1600898) might provide a solution, but it's more complex than I expected, and it appears to require dynamic dispatch. – user4815162342 Jan 29 '21 at 07:49
  • Here's the issue with what you're trying to do. Imagine a tuple to be two values directly adjacent to each other in memory (this isn't always true but just assume that it is for a bit). A `(usize, Vec)` would need to be a `usize` directly followed by a `Vec`, and a reference to it would require a pointer to a region of memory that contains the `usize` followed by a `Vec`. When you just have an `&Vec`, you have a reference to a `Vec`, but there are no guarantees that there's a `usize` before it, and there's no guarantee that you can write a `usize` before it. – Aplet123 Jan 29 '21 at 12:55
  • This leads to it being extremely difficult (basically impossible to do safely unless I'm missing something) to generate a reference to the whole tuple without cloning the `Vec` or using `unsafe` (although I don't think there's a way to use `unsafe` in a way that's not actually unsafe) – Aplet123 Jan 29 '21 at 12:58
  • 1
    On second thought, it might be possible to use [`Vec::from_raw_parts`](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.from_raw_parts) in order to avoid having to clone the actual `Vec` contents. – Aplet123 Jan 29 '21 at 13:15
  • 1
    @Aplet123 Note that the OP is willing to modify the hash map definition to use a custom type for the key. Would it be possible to define a key type that consists of `(usize, Vec)` but can be coerced to `(usize, &Vec)` for purposes of hashing and comparison? Hash maps already support something similar through `Borrow` that allows owned strings to be compared and hashed along with string slices. It seems that something similar should be possible here as well, but it's not obvious that `Borrow` allows it, except through [a trait object](https://stackoverflow.com/a/45795699/1600898). – user4815162342 Jan 29 '21 at 20:44
  • @Aplet123 I tried that out and was able to make something similar work using `std::mem::forget` and by re-constructing the type, but I wonder if there is a better solution. If we have some `x: &T`, and need to get a `y: (usize, T)`, could we do the equivalent of `memcpy(src: x, dst: y.1, size: sizeof(T))` and then not run the destructor? – Joe the Person Jan 29 '21 at 20:55

0 Answers0