CODEWITHSUNDEEP
rusthashmap
aclow
aclow

Reputation: 449

In-place modification, insertion or removal in the same function for hash maps in Rust

Say I have a hash map m: HashMap<K, V>, a key k: K and a value v: V, and would like to do the following:

Is there a way to do this "in-place", without calling functions that access, modify or remove the value at k multiple times?

I would also like to avoid copying data, so ideally one shouldn't need to clone v to feed the clones into insert and combine separately.

I could rewrite combine to use (mutable) references (or inline it), but the wish of not copying data still remains.

Upvotes: 2

Views: 1418

Answers (2)

aclow
aclow

Reputation: 449

Digging deeper into the Entry documentation, I noticed that the variants of the Entry enum offer functions to modify, remove or insert entries in-place.

After taking std::collections::hash_map::Entry into scope, one could do the following:

match m.entry(k) {
    Entry::Occupied(mut oe) => {
        let w = oe.get_mut();
        match combine(v, w) {
            Some(u) => { *w = u; },
            None    => { oe.remove_entry(); },
        }
    },
    Entry::Vacant(ve) => { ve.insert(v); },
}

(Here is a PoC in the Rust playground.)

This, however, requires combine to take a (mutable) reference as its second argument (which is fine in my case).

Upvotes: 3

felix91gr
felix91gr

Reputation: 103

I managed to do it in one access, one write and one key-deletion in total in the worst case. The last key-deletion should not be necessary, but I'm not certain it can be done. I gave it my best so far. I hope this helps!

Okay, so I think we want to use the Entry API.

The full method list for Entry is here.

I think we'd do it in the following order:

  • If m contains a value w at index k: (two more steps)
  • Or insert v at index k.

This can be done by using .and_modify and then .or_insert. Something like this:

let map = // ... Initialize the map

// Do stuff to it
// ...

// Our important bit:

let mut delete_entry = false;

map.entry(k)
   .and_modify(|w| { // If the entry exists, we modify it

     let u = combine(v, w);

     match u {

       Some(y) => *w = y;

       None => delete_entry = true;
       }
     }
   )
   .or_insert(v); // If it doesn't, we insert v

if delete_entry {
  map.remove(k);
}

I don't think there's a way to do all three things without that last map.remove access, so this is my best attempt for now.

Upvotes: 1

Related Questions