How do I implement a container with support for a mutable iterator? [duplicate]

Question

I want to design a toy container class with support for mutable iterators, but I'm having trouble sorting out the lifetimes of the iterator and its reference to the container.

I've tried to create a minimal non-compiling example:

struct Payload { value: i32, } struct Container { val: Payload, } struct IterMut<'a> { cont: &'a mut Container, cnt: i32, } impl<'a> Container { fn new() -> Container { Container { val: Payload { value: 42 } } } fn iter_mut(&'a mut self) -> IterMut<'a> { IterMut { cont: self, cnt: 10, } } } impl<'a> Iterator for IterMut<'a> { type Item = &'a mut Payload; fn next<'b>(&'b mut self) -> Option<Self::Item> { self.cnt -= 1; if self.cnt < 0 { return None; } else { Some(&mut self.cont.val) } } } fn main() { let mut cont = Container::new(); let mut it = cont.iter_mut(); it.next(); }

The above is intended to implement a real stupid container that returns the same item 10 times when iterated over using iter_mut().

I can't figure out how to implement Iterator::next.

I did manage to write a regular function that implements the same semantics as what I want for next:

fn manual_next<'a, 'b>(i: &'a mut IterMut<'b>) -> Option<&'a mut Payload> { i.cnt -= 1; if i.cnt < 0 { return None; } else { Some(&mut i.cont.val) } }

This doesn't help, because I can't manage to adapt it to implement Iterator::next, and without implementing Iterator, my container can't be iterated over in for-loops, which I want.

Shepmaster · Accepted Answer · 2017-02-15 14:06:53Z

It's not possible to implement the iterator as is, because it would allow you to get more than one mutable reference to the same item, breaking Rust's aliasing/borrowing rules. Good thing the borrow checker caught the error! :-)

For example, extending your main example:

fn main() { let mut cont = Container::new(); let mut it = cont.iter_mut(); let alias_1 = it.next(); let alias_2 = it.next(); // alias_1 and alias_2 both would have mutable references to cont.val! }

Other iter_mut iterators (for example the one one on vectors/slices) return references to different items on each step, so don't have this problem.

If you really need to iterate over something logically mutable, you may be able to iterate immutably but use interior mutability via RefCell or Cell.

The reason the manual_next function compiles is that you're not constrained to the Iterator::next signature, and it is in fact perfectly safe to call once (or more if you don't keep the result). However if you try to save the result, it keeps the IterMut borrowed mutably and you couldn't call it again:

let mut cont = Container::new(); let mut it = cont.iter_mut(); let x = manual_next(&mut it); manual_next(&mut it); // Error: `it` is still borrowed mutably

Playground

In contrast, Iterator::next has a type which makes things like collecting into a vector possible.

Aha, of course! So when I attempted to create a really simple example, I accidentally created an invalid example.
So the reason why my "manual" next-method works, is because it's signature doesn't allow more than one return value from next to be alive at the same time? Whereas the signature for the Iterator-trait's next-method does? Put in another way - the Iterator trait promises that next() will not return the same mutable reference twice. But my implementation was trying to do just that.
Yes, that's right - I've added a bit to my answer to try to cover that.

Collectives™ on Stack Overflow

How do I implement a container with support for a mutable iterator? [duplicate]

1 Answer 1

3 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Linked

Related