Two-way removal of the elements from HashMap and vector

I have HashMap<usize, usize> and Vec<usize>. I created vector because I want to get random element from the HashMap (which means that vector with element 2 is connected to HashMap element with key 2). Now, this works okay, I generate a random number in a range between 1 and length of the vector and then delete that element of the vector as well as corresponding element in the HashMap.

However, problem arises for the other way around. Sometimes I want to delete element of the HashMap directly and as a result delete corresponding element in the vector. At first I thought to store reference to corresponding vector element in each value of the HashMap element but as I can see it’s not possible to remove vector by passing reference to it.

Is there a way to solve this problem without creating third structure?

Edit: I realized that problem could be solved with retain() method since I have unique elements. It would be interesting to see an answer for non-unique elements though.

I don’t think there’s any good solution for this apart from either:

  1. Encapsulating this in a struct that owns both the map and the vec.
  2. Adding some smart ptr type thing that has a Rc<RefCell<...>> reference back to the other container, and does the removal in its (custom) Drop impl.

I’ve run into this as well. If anyone has something nicer, I’d be interested as well.