How can I lookup in a HashMap using a reference type without cloning my data members?

help
1

I'm trying to use a HashMap<(Graph, usize), bool> to memoize answers for a given Graph and node. I'm trying to write

// Extract the corresponding bool from the HashMap without copying an
// entire Graph.
fn get(
  m: HashMap<(Graph, usize), bool>,
  graph: &Graph,
  pos: usize,
) -> Option<bool> {
  // Error: expected struct `Graph`, found `&Graph`
  m.get(&(graph, pos))
}

I could "solve" this problem by making Graph implement Clone and calling graph.clone() here, but that's not really a solution I'm okay with :sweat_smile: Similarly, if the map were just a HashMap<Graph, bool>, indexing into it with a &Graph would be easy. But it's not - I need the key to represent both the graph and a position.

I've read the docs on Borrow, which describe the problem and the motivation to declare HashMap::get()'s signature in terms of Q: Borrow<K>, but the docs don't give an example of a successful value-type / reference-type pair used to store and retrieve values from the map.

Here's a minimal repro where I try to declare the tuple as an owning Key struct and describe its relationship to a borrowed KeyRef struct. It doesn't compile because Key::borrow() should return a reference, but I don't know how to tell Rust that a KeyRef struct is a reference.

2

You can't, because it isn't one. This isn't really a problem that is easily solvable with HashMap and Borrow at this point.

3

This is a known limitation of the Borrow trait: it requires there to already be an instance of the borrowed type in order to return a reference to it. There are some crates with an alternative HashMap implementation that works around this (I don’t know the names, unfortunately). It’s also possible to use a trait object to get around the limitation.

4

The indexmap crate has an Equivalent trait for this purpose.