Map where keys are a part of a value

help
1

Often, I am in a situation when I need a mapping from keys to values, and a key happens to be a part of a value. For example, I have a

struct Person {
  name: Name,
  age: u16,
}

And I want to have Map<Name, Person>. Is there any map collection which allows me to supply a value type and a key function, so as to avoid cloning names?

Also, is there any special names for such associative containers, where a key is a part of a value?

1 Like
2

I hacked this data structure together as a part of another project, but haven't yet split it out into its own crate. The code is in this file: https://github.com/radix/pandt/blob/master/pandt/src/indexed.rs

It involves two things: a trait called DeriveKey which you would implement for Person, and have its derive_key method return self.name. Then you can create an IndexedHashMap<Person>.

The unfortunate thing is that there's no get_mut(K), because there's no way for me to implement it without potentially leading to inconsistencies -- if you retrieve a mutable object and changed its key, there's no way for the IndexedHashMap to pick that up and update its internal HashMap. So instead there is a mutate method that takes a closure that gets a mutable reference to the object, and it can do the book-keeping after the closure returns.

edit: Sorry, I just noticed you were asking about avoiding clones of the key. Unfortunately my module doesn't do that, and I'm not sure it's even possible to do safely. Maybe something involving rental?

1 Like
3

Hm, why would that be impossible to do safely? I think one can store values in the array, and store indexes in the map itself.

What is impossible I think is reusing std::HashMap as the basis for this implementation, because you can't parametrize it over hash function, which seems to be a pretty serious limitation actually...

4

Hm, or perhaps one can do this? Let me try...

5

Yep, it is possible, and this collection is called a HashSet :sweat_smile:

4 Likes