Compare struct of owned with struct of references?

help
#1

I have a number of Events like this:

struct Event {
  a: String,
  b: String,
  v: u32,
}

and I would like to sum v by a and b:

To do that I store them in a BTreeMap. The only way to do that (as far as I know) is to define a struct for the keys:

#[derive(Ord,PartialOrd,Eq,PartialEq)]
struct Key {
  a: String,
  b: String,
}

let map = BTreeMap<Key, u32>;

Now, if I want to look up a group, I have to construct a Key by cloning the strings for a and b:

let a = "abc";
let b = "abc";
let key = Key {
  a: a.clone(),
  b: b.clone(),
};

Even if I'd define a struct for borrowed strings:

struct RefKey {
  a: &String,
  b: &String,
}

that RefKey can't be compared to a Key.

In general owned strings can be compared to references. Can I tell the compiler to extend that property to my pair of structs? Or maybe I didn't choose my map keys well?

#2

I don't think this is possible as-is, because get(), index(), and similar methods require a K: Borrow<Q> bound on the key, which means that your key has to be a reference type itself, and it can't be a value-type-holding-references. This is somewhat of an oversight in the design of the Borrow API (or in BTreeMap, depending on your point of view).

However, it's possible to avoid allocations by defining the fields of the key as Cows, because then you can construct a "cheap" key from borrowed values. Playground.

#3

That... is a lot of code (and a lot of lifetimes). Couldn't I just implement Eq and Deref for my key type or something like that?

#4

Deref and Borrow are limited to returning a single reference; they don't work for values that aggregate multiple references.

The third-party indexmap crate uses a custom Equivalent trait instead of the standard Borrow trait, to support use cases like this. Unfortunately, I don't know of any BTreeMap replacement that does the same. (IndexMap is a HashMap replacement.)

There's also this workaround with trait objects.

#5

The two From impls are there only for visual clarity at the call site, you can do it all without those. And no, you can't implement Deref in this manner, because it needs to return a reference, not a value containing a reference, just like Borrow.