How can I write a container that allows removal by "handle"?

[tavianator]

I'm trying to implement a type that supports operations like this:

let mut c = MyContainer::new(...);
let handle = c.find(key);
println!("{}", handle.value);
c.remove(handle);

This is kind of like how C++ containers work, by returning iterators and letting you pass them to erase(). It's important for my use case for a few reasons, mainly because find() can be quite expensive, so I don't want to repeat the search like I would have to for something like c.remove(key).

The issue with this is that the handle has references into the container. So a naive implementation fails with "cannot borrow c as mutable because it is also borrowed as immutable". Here's a complete example:

struct MyContainer(Vec<String>);

struct Handle<'a> {
    value: &'a String,
    index: usize,
}

impl MyContainer {
    fn new(values: Vec<String>) -> Self {
        Self(values)
    }

    fn find(&self, value: &str) -> Option<Handle> {
        for (i, s) in self.0.iter().enumerate() {
            if s == value {
                return Some(Handle {
                    value: s,
                    index: i,
                })
            }
        }

        None
    }

    fn remove(&mut self, handle: &Handle) {
        self.0.remove(handle.index);
    }
}

fn main() {
    let mut c = MyContainer::new(vec!["Hello".to_string(), "world".to_string()]);
    if let Some(handle) = c.find("world") {
        println!("{}", handle.value);
        c.remove(&handle);
    }
}

Is there an established pattern for situations like this? I searched around but couldn't really find anything.

[cuviper]

HashMap::entry is a little like that. The trick is that the Entry holds a full reference back to the map, so you can insert/remove with methods on the entry itself.

I could imagine your handle working this way, although it will need to be made from a mutable reference to let it modify the container.

[Michael-F-Bryan]

I know graph libraries like petgraph return some sort of NodeIndex (which may just be an integer) when you add an item to the collection, then every time you want to access the data you use get() or get_mut().

I guess it depends on how your collection is implemented. You could always use reference counting (Rc) where a "handle" contains an Rc<RefCell> internally and implements Deref for your Handle type. That means you lose a lot of the nice compile-time guarantees that lifetimes give you though because they're now implemented at runtime.

You may also find @jonhoo's stream on implementing the Java ConcurrentHashMap in Rust interesting. They needed to implement the same sort of Handle thing, but also dealt with the intricacies of concurrency and handle invalidation during a resize. It's a long stream because implementing ConcurrentHashMap isn't trivial, but they do a really good job at showing what writing code in the real world actually looks like.