Why does HashMap have iter_mut() but HashSet doesn't?

Question

What is the design rationale for supplying an iter_mut function for HashMap but not HashSet in Rust?

Would it be a faux pas to roll one's own (assuming that can even be done)?

Having one could alleviate situations that give rise to

previous borrow of X occurs here; the immutable borrow prevents subsequent moves or mutable borrows of X until the borrow ends

Example

An extremely convoluted example (Gist) that does not show-case why the parameter passing is the way that it is. Has a short comment explaining the pain-point:

use std::collections::HashSet;

fn derp(v: i32, unprocessed: &mut HashSet<i32>) {
    if unprocessed.contains(&v) {

        // Pretend that v has been processed
        unprocessed.remove(&v);
    }   
}

fn herp(v: i32) {
    let mut unprocessed: HashSet<i32> = HashSet::new();
    unprocessed.insert(v);

    // I need to iterate over the unprocessed values
    while let Some(u) = unprocessed.iter().next() {

        // And them pass them mutably to another function
        // as I will process the values inside derp and
        // remove them from the set.
        //
        // This is an extremely convoluted example but
        // I need for derp to be a separate function
        // as I will employ recursion there, as it is
        // much more succinct than an iterative version.
        derp(*u, &mut unprocessed);
    }   
}

fn main() {
    println!("Hello, world!");
    herp(10);
}

The statement

while let Some(u) = unprocessed.iter().next() {

is an immutable borrow, hence

derp(*u, &mut unprocessed);

is impossible as unprocessed cannot be borrowed mutably. The immutable borrow does not end until the end of the while-loop.

I have tried to use this as reference and essentially ended up with trying to fool the borrow checker through various permutations of assignments, enclosing braces, but due to the coupling of the intended expressions the problem remains.

Answer 1

You have to think about what HashSet actually is. The IterMut that you get from HashMap::iter_mut() is only mutable on the value part: (&key, &mut val), ((&'a K, &'a mut V))

HashSet is basically a HashMap<T, ()>, so the actual values are the keys, and if you would modify the keys the hash of them would have to be updated or you get an invalid HashMap.

Answer 2

If your HashSet contains a Copy type, such as i32, you can work on a copy of the value to release the borrow on the HashSet early. To do this, you need to eliminate all borrows from the bindings in the while let expression. In your original code, u is of type &i32, and it keeps borrowing from unprocessed until the end of the loop. If we change the pattern to Some(&u), then u is of type i32, which doesn't borrow from anything, so we're free to use unprocessed as we like.

fn herp(v: i32) {
    let mut unprocessed: HashSet<i32> = HashSet::new();
    unprocessed.insert(v);

    while let Some(&u) = unprocessed.iter().next() {
        derp(u, &mut unprocessed);
    }   
}

If the type is not Copy or is too expensive to copy/clone, you can wrap them in Rc or Arc, and clone them as you iterate on them using cloned() (cloning an Rc or Arc doesn't clone the underlying value, it just clones the Rc pointer and increments the reference counter).

use std::collections::HashSet;
use std::rc::Rc;

fn derp(v: &i32, unprocessed: &mut HashSet<Rc<i32>>) {
    if unprocessed.contains(v) {
        unprocessed.remove(v);
    }   
}

fn herp(v: Rc<i32>) {
    let mut unprocessed: HashSet<Rc<i32>> = HashSet::new();
    unprocessed.insert(v);

    while let Some(u) = unprocessed.iter().cloned().next() {
        // If you don't use u afterwards,
        // you could also pass if by value to derp.
        derp(&u, &mut unprocessed);
    }   
}

fn main() {
    println!("Hello, world!");
    herp(Rc::new(10));
}