Get ref to just-inserted HashSet element?


#1

Is there a way to get the &T to a T that I just added to a HashSet<T>?

Oddly, it seems like even HashMap’s entry API can’t give me a &K to the inserted item, only the &mut V. (The only &K it returns is from the Entry, which can’t be kept across the insertion.)

Shortened example of where I wanted it; alternative approaches welcome as well.
https://play.rust-lang.org/?gist=393dc116c78b32dd40d935b2cf05b032&version=stable

struct Node<T> {
    in_edges: HashSet<T>,
    out_edges: HashSet<T>,
}

struct Graph<T> {
    nodes: HashMap<T, Node<T>>,
}

impl<T:Eq+Hash> Graph<T> {
    fn add_edge(&mut self, source: T, target: T) {
        self.nodes.get_mut(&source).unwrap().out_edges.insert(target);
        self.nodes.get_mut(&target).unwrap().in_edges.insert(source);
        //                 ^ obviously I can't use this here
        // but there's a perfectly good ref that I just inserted,
        // if only I could get it...
    }
}

#2

It’s possible to use unsafe to do so.

impl<T: Eq + Hash> Graph<T> {
    fn add_edge(&mut self, source: T, target: T) {
        let out_edges: *mut _ = &mut self.nodes.get_mut(&source).unwrap().out_edges;
        self.nodes.get_mut(&target).unwrap().in_edges.insert(source);
        unsafe {
            (*out_edges).insert(target);
        }
    }
}

Not entirely sure if it can be done without unsafe however.


#3

The problem is that you don’t have the target anymore, because it was moved into the set, so you cannot use neither the get() fn of the set.
The two solutions that pops out of my mind are to use some smart pointer like Rc (or Arc if you need parallelism) or to use indexes and use some indexed hash map to store the nodes (like the OrderMap of the ordermap crate.


#4

This is probably as good a use of unsafe as one can see in a small and self-contained example.


#5

The issue your code has is related to ownership. After a call to add_edge, the source node owns the target node and the target node owns the source node. The borrow checker rightly keeps you from doing that.

I am with @garro on this. Alternatively, if you know that this graph will only handle primitive types (like u32), you can add the bound T: Copy and completely side-step any ownership issues.


#6

Ordermap has some useful features – the key-value pairs are in a compact usize-indexable range, and it also has methods that give you mutable references to the keys. (With caution; version 0.3/current master will use an opt-in trait instead of having this in the regular interface.)

I think its interface could be expanded and made more consistent a bit, and it could give you all of index, ref mut key, ref mut value from its entry methods.


#7

Thanks, all! I’d been doing something like what @xfix suggested, so good to get confirmation that it’s not a terrible plan :laughing:

I suppose that my original question was wrong too; even if I had the ref from the container, it’d be borrowing self.nodes (as far as borrowck knows) so I wouldn’t be able to pass it to get_mut anyway.