How can I index a collection of records by one of their field?

Question

I have a Record type, with a get_key(&self) -> &str method (borrowing the returned str from inside the record). Records may be mutable, but their key is guaranteed not to change.

I want to store a list of records in a collection, and be able to retrieve a record by its key. The first idea is to use a HashMap<String, Record>, but that looks like a waste of space (because the strings in the key position are copies of the record's keys).

I would rather have a HashMap<&str, Record>, but I can't provide a lifetime for the &str keys (since they are borrowed from inside the hashmap). This is the kind of self-reference that crates like rental or owning_ref are designed to handle. However, none of them provide an out-of-the-box solution for this use-case.

I looked for a crate providing this kind of "indexed collection", but to no avail. Am I missing something? (I started hacking a solution of my own, but I'd rather not re-invent the wheel)

Maybe you can use a `HashSet`, having `WrapperRecord` contain a `Record` and implement `Hash` and `Borrow`. — rodrigo, Dec 11 '18 at 08:59

rodrigo · Accepted Answer · 2018-12-11T09:44:14.787

3

If you want a container where the key itself is part of the value, you can use HashSet with a newtype to reimplement the required traits: Hash, Borrow<str>, PartialEq and Eq.

For example (link to playground):

struct HRecord(Record);
impl Hash for HRecord {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.0.get_key().hash(state);
    }
}
impl PartialEq for HRecord {
    fn eq(&self, r: &HRecord) -> bool {
        self.0.get_key().eq(r.0.get_key())
    }
}
impl Eq for HRecord {}
impl Borrow<str> for HRecord {
    fn borrow(&self) -> &str {
        self.0.get_key()
    }
}

And now the HashMap just works:

let mut h = HashSet::new();
h.insert(HRecord(Record { ... }));
let obj = h.get("...").map(|h| &h.0);

edited Dec 11 '18 at 09:44

answered Dec 11 '18 at 09:19

rodrigo

94,151
12
143
190

That's indeed a nice way to implement it without a self-reference. I didn't think of implementing Borrow so that I could use &str in h.get(...). – Pierre-Antoine Dec 11 '18 at 11:00
However, what I would like is a type abstracting this mechanism so that the user does not have to juggle btw Records and HRecords... Any crate providing that? – Pierre-Antoine Dec 11 '18 at 11:02
@Pierre-Antoine: Well, you can easily wrap a `HashSet` into a `RecordSet` and expose the proper `insert(&mut self, r: Record)` and `get(&self, &str) -> &Record` functions, and keep the `HRecord` private. – rodrigo Dec 11 '18 at 11:03
indeed, but then I would have to mirror all the usual container methods (iter, len, shrink_to_fit...), which is cumbersome, and could be factorized in to a generic type, hence my question. – Pierre-Antoine Dec 11 '18 at 12:37
that being said, I realized that, if I have control over the Record type (which is the case in my actual scenario), I don't need HRecord, I can simply implement Hash, Eq and Borrow (thanks again for that tip) for Record itself, and then use a HashSet. E.g.: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=a17a3af31afc43ebb1ecf594d997e55a – Pierre-Antoine Dec 11 '18 at 12:40
1

@Pierre-Antoine: That is up to you, of course. But implementing `Eq` for that may not be a good idea: being equal for indexing purposes does not necessarily mean being equal for everything. And a similar caveat for `Borrow`. – rodrigo Dec 11 '18 at 12:46
You can instead implement `impl Deref for HRecord` and `impl From Record for HRecord` That would minimize user inconvenience while keeping the `Record` unaltered. – rodrigo Dec 11 '18 at 12:46

How can I index a collection of records by one of their field?

1 Answers1