I'm trying to implement IterMut for my linked list. but I really can't do it, I'm working on it for 4 hours and I had no progress.
Can someone help me to make this work?
cannot borrow *current as mutable more than once at a time
I understand the error and know why I get this, but I don't know the right way to do it.
I also tried Rc<RefCell<>> but I'm no expert in rust so I couldn't do it in that way either.
You cannot make an iterator of &mut Box<Node<T>>s, because access to one Node entails access to all subsequent nodes, yet iterator items can be used concurrently, e.g. by .collect()ing them into a Vec<&mut Box<Node<T>> which would then contain multiple mutable references giving (mutable) access to the same items.
Try to create an iterator of Item = &'a TItem = &'a mut T instead; the necessary modification is minor/straightforward; if you’re having trouble making it work anyways, feel free to ask for code.
To add to @steffahn 's answer, the thing allows safe mutable iteration is rust's support for separately borrowing from independent fields of a struct (in this case, value, and next). You can't return them both together as part of the iterated value. But you can return value and update the next that the iterator is pointing to. You just have to write the code in a way that makes it obvious to the compiler that you're not doing anything that violates mutable aliasing. It's actually very little code once you know what to write, but I'm expanding it out below to make the thinking process more obvious.
impl<'a, T> Iterator for IterMut<'a, T> {
type Item = &'a mut T;
fn next(&mut self) -> Option<Self::Item> {
// `take()` here moves the option out of the iterator,
// replacing the previous value with `None`, thereby
// disconnecting the iterator from the node we just
// pulled out as `curr`.
let curr = self.current.take(); // Option<&mut Box<Node<T>>>
// You could have inlined `self.current.take()` here.
// I split off the line above to make it more obvious
// that `curr` and `self.current` are now separated,
// which helps explain why you're able to assign back
// to `self.current` below.
match curr {
Some(node) => { // &mut Box<Node<T>>
// Deref `&mut Box<Node<T>>` to `&mut Node<T>`
// so that we have a naked `Node` and we can
// borrow its two fields independently in a
// way that the compiler understands are
// mutable borrows of independent fields.
let node = &mut *node;
// That being said, the above line isn't
// _strictly_ needed but _only_ because the
// compiler treats `Box` specially to allow
// simultaneously mutably borrow different
// fields of `Box<Struct>`. So commenting
// out the above line still works. (This
// special-case handling of `Box` is
// generally considered unfortunate since
// it makes `Box` unnecessarily special.)
// Now we can borrow the two fields (`next`
// and `value`) mutably _independently_ and
// the compiler totally buys it.
self.current = node.next.as_mut();
Some(&mut node.value)
}
None => None
}
}
}
Thanks. it works fine this way. but I wanted to know isn't there any way to iterate over Nodes?
something like Item = &a' Node<T>
Here's the new code if anyone is interested
struct IterMut<'a, T> {
current: Option<&'a mut Box<Node<T>>>,
}
impl<'a, T> Iterator for IterMut<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
if self.current.is_none() {
return None;
}
let current = self.current.take().unwrap();
self.current = current.next.as_mut();
Some(¤t.value)
}
}
To clarify: You can iterate over nodes if you're iterating over shared borrows (&Box<Node<T>>). However, you cannot iterate over &mut Box<Node<T>> since &mut borrow actually means unique borrow, which means that you can't simultaneously have two live mutable borrows to the same content. In other words, you can write your code as originally written, with the &mut replaced with & within the iterator struct and the Item definition.
