Implementing Iterator for Vec

#[derive(Debug)]
struct VecIter<'a, T> {
    vec: &'a mut [T],
    current_index: usize,
}

impl<'a, T> VecIter<'a, T> {
    fn new(vec: &'a mut [T]) -> VecIter<'a, T> {
        VecIter {
            vec,
            current_index: 0,
        }
    }
}

impl<'a, T> Iterator for VecIter<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<&'a mut T> {
        if self.current_index == self.vec.len() - 1 {
            None
        } else {
            self.current_index = self.current_index + 1;
            Some(&mut self.vec[self.current_index])
        }
    }
}

fn main() {
    let mut v = vec![1, 2, 3, 4];
    let vec_iter = VecIter::new(&mut v);
}

I am trying to implement iterator for vector. The error I am getting is
cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements

note: ...so that reference does not outlive borrowed content
note: expected std::option::Option<&'a mut T>
found std::option::Option<&mut T>rustc(E0495)

which is coming on line Some(&mut self.vec[self.current_index]). According to the message I am understanding that as next method have &mut self which will allocate a different lifetime than 'a there can be a conflict with references we get using self.vec. I saw the std library implementation and they also seem to do it this way only.
I am new to rust so my understanding of the whole problem can be limited.

1 Like

Generally it's not possible to implement mutable iterators in safe Rust.

The iterator must never ever return the same element twice, and the borrow checker is unable to understand value-dependent code logic to prove that is the case. So in practice you either have to piggy back on an existing function that uses unsafe (e.g. split_at_mut), or use unsafe and transmute lifetimes yourself.

4 Likes

Thanks @kornel for the response. I got the point. Just wanted to ask whether I interpreted the error message correctly or not. The error is because lifetime of &mut self can be different from 'a right ?

I'm not 100% sure on how exactly this ends up being incorrect, but I think it's because exclusive loans are invariant, meaning they can't be made any shorter or longer by the compiler (unlike shared loans, which are more flexible and the compiler can implicitly adjust (subclass) to be shorter if needed). So when you borrow something from an existing exclusive loan, this is called reborrow in Rust, and creates a new temporary loan with a different lifetime. Hence, the new loan in next doesn't match, and can't be made to match, the other loan marked by 'a.

This is different from functions like split_first_mut, which will explicitly return you two new loans with the same existing lifetime, instead of starting a new loan (and this is only possible by transmuting lifetimes when ensuring the returned references don't overlap).

1 Like

Understood perfectly. Thanks for the explanation :slightly_smiling_face: I will try to explore more on this on unsafe side.

It is possible in safe Rust, by utilizing split_mut or split_first_mut or the like. I feel it's an illustrative example, too.

First, when I look at your current example, you're holding onto the entire &mut [T] while handing out mutable references to its contents. You should know that even if you never use both of them, having two &mut to the same memory is instant undefined behavior (UB). You're going to need to "give up" your &mut access to the parts of the slice you return somehow.

One way would be to use *mut and some unsafe when returning values. But split_mut and friends give you a way to do it in safe code, still using &mut (by soundly encapsulating the unsafe parts in a safe API themselves). The main idea is that your &mut[T] will need to shrink as you hand out pieces of it.

split_first_mut seems ideal for next, so let's see what happens when we try to use it:

    fn next(&mut self) -> Option<&'a mut T> {
        let (first, rest) = self.vec.split_first_mut()?;
        self.vec = rest;
        Some(first)
    }

Playground. It doesn't work -- for the same reasons as your original code! You're calling split_first_mut on self.vec by going through the mutable reference on the parameter. More explicitly:

    // `Self` = `VecIter<'a, T>`.  `'next` may be much smaller than `'a`
    fn next(&'next mut self) -> Option<&'a mut T> {

So you can't get a long enough lifetime to return by going through &'next mut self.

This is where the really illustrative parts comes in. You cannot move non-Copy values (like your &mut [T]) out from beneath an outer &mut reference, as that could leave the underlying struct in an invalid state. So in order for this to work in safe code, you'll have to first get the &mut [T] out from behind your &mut self.

And fortunately, there is a safe way to do so:

    fn next(&mut self) -> Option<&'a mut T> {
        // Temporarily remove the slice from behind &mut self
        let slice = std::mem::take(&mut self.vec);
        // Now we can get a long enough lifetime to return
        let (first, rest) = slice.split_first_mut()?;
        // And put the `rest` back where we found it
        self.vec = rest;
        // 🎉
        Some(first)
    }

Playground. There you go, an iterator over mutable references without using any unsafe yourself.


So, how does it work? The key line is

        let slice = std::mem::take(&mut self.vec);

Which could have also been written as

        let slice = std::mem::replace(&mut self.vec, &mut []);

And it's possible because this is a special case that Rust is aware of: a &mut to no memory at all (such as a &mut[T] of zero length) is completely safe, so you can conjure one out of thin air (like I did with replace), and &mut[T] implements Default to produce an empty slice as well (which is why std::mem::take also works).

You can read more about this "swap out, modify, replace" pattern in Niko's post, moving from borrowed data and the sentinel pattern.

12 Likes

I'll add that one can also use slice patterns for this, if you want to do it more "directly". (It's not better to do that, but since this whole thing is an exercise in avoiding existing standard library stuff, it can be illustrative.)

pub fn my_split_first_mut<T>(x: &mut [T]) -> Option<(&mut T, &mut [T])> {
    if let [a, b @ ..] = x {
        Some((a, b))
    } else {
        None
    }
}
9 Likes

Oh, that's great! Slice patterns making even more possible in safe code.

1 Like

Slice patterns can result in a pretty elegant solution

struct Iter<'a, T>(&'a mut [T]);

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a mut T;

    fn next(&mut self) -> Option<&'a mut T> {
        match self.0 {
            [item, rest @ ..] => {
                self.0 = rest;
                Some(item)
            }
            [] => None,
        }
    }
}

(playground)

Although annoyingly, it looks like matching on a mutable slice will borrow it from self and give you a bunch of lifetime errors. The only way I could make it work was to match on std::mem::take(&mut self.0) so we move the slice instead.

I'd love if someone can think of a way to avoid the std::mem::take() or can explain how slice patterns get desugared in more detail.

1 Like

It looks like the problem is the lack of the take, actually. The split_first_mut doesn't work without it either -- and this isn't something that polonius fixes: https://rust.godbolt.org/z/P3MsrrWs8

But the error messages makes no sense to me:

error[E0623]: lifetime mismatch
  --> <source>:28:13
   |
24 | pub fn next_with_split<'short, 'a, T>(it: &'short mut Iter<'a, T>) -> Option<&'a mut T> {
   |                                           -----------------------     -----------------
   |                                           |
   |                                           this parameter and the return type are declared with different lifetimes...
...
28 |             Some(item)
   |             ^^^^^^^^^^ ...but data from `it` is returned here

It seems like maybe there's something about take that lets it actually use the inner lifetime, whereas everything else ends up restricting it to the outer one?

It's basically what is talked about in Niko's article; the compilier can't be sure that there's no intermediate panic where an invalid or UB state [1] can be observed. You can read the SAFETY comments to see the consideration to some extent. There's no magic, it uses unsafe and pointers.

Arguably the compiler could grow smarter about seeing or knowing what can panic or not, and getting rid of the memory-safety-preserving semantics about not getting 'long lifetimes through a &'short mut by special casing some types of matchings... short regions of local code... "known good" functions from the standard library. But I'm not convinced that's a good idea. I prefer concise, easier-to-reason-about rules than contextual magic.

I do agree that std::mem::{replace, swap, take} should be much better known and promoted in introductory materials. I think they should be embraced in scenarios where they make sense, and not considered something to avoid.


  1. e.g. two mutable borrows of the same data ↩ī¸Ž

1 Like

That doesn't make sense to me as an explanation in this particular case, though. We're not moving out any fields in the slice pattern example. It's just a re-borrow, so it could panic at any point in the method and still be sound.

Absolutely agreed on this, though.

I don't see how it could work as a reborrow. If you don't assign back and then return something, that's two &mut to the same place; we can certainly agree that won't work. But if you assign back to the original slice (which can only be done within the outer lifetime window), the reborrow is dead at that point, so you can't return anything. Arguably still useful for changing a slice's length or the like, but even more niche.

Maybe it could work as something like a two-phase borrow where the phases can be arbitrarily far apart (between the match and the reassignment)? Like, you get a short outer lifetime at the point of binding as per usual. If the reborrow ends with an assignment back to the original location by the subslice, at the point of assignment, all borrows enter phase two with the longer inner lifetime. (The subslice needs the longer lifetime for assignment to succeed, and the elements need it under the premise that you want to return them.)

I find that an interesting concept to think about, and just spent a long time doing so [1]. But I don't really think it's a simple thing once, e.g., nesting or multiple subslices are considered (though perhaps I just failed to find right mental model). I think it could work in very simple cases (but am still not sure it's worth it).

(Your reply was about a comment of mine regarding panics, which I didn't even think about at all in this reply; sorry about that.)


  1. and now wish for the nth time I could split my drafts ↩ī¸Ž

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.