# How to implement a safe mutable iterator for Vec\<T\>?

**URL:** <https://users.rust-lang.org/t/how-to-implement-a-safe-mutable-iterator-for-vec-t/33297>\
**Category:** help\
**Created:** [October 5, 2019, 12:27pm UTC](https://users.rust-lang.org/t/how-to-implement-a-safe-mutable-iterator-for-vec-t/33297 "2019-10-05T12:27:14Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![thomas001](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/thomas001/32/12807_2.png) [@thomas001](https://users.rust-lang.org/u/thomas001)\
**Post date:** [October 5, 2019, 12:27pm UTC](https://users.rust-lang.org/t/how-to-implement-a-safe-mutable-iterator-for-vec-t/33297/1 "2019-10-05T12:27:14Z")

</div>

Hi,

I was trying to implement a custom iterator for Vec, that has a alternative iteration scheme, but I lost to the borrow checker while doing so. I tried to debug the issue and turns out, I don't even know how to implement a normal iterator for Vec. So the task is basically to re-implement `Vec<T>::iter_mut()` using safe code. I tried a very naive approach, keeping a mutable reference to the vector and an index, but that fails. I don't know exactly why and how to fix this. The code is on [rust playground](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=adc18bb9997225854f8ec41936971d4e) and also here:

```rust
use std::ops::IndexMut;

struct CustomIter<'a, T> {
    i: usize,
    v: &'a mut Vec<T>,
}

impl<'a, T> Iterator for CustomIter<'a, T> {
    type Item = &'a mut T;
    
    fn next(&mut self) -> Option<&'a mut T> {
        if self.i == self.v.len() {
            None
        } else {
            self.i += 1;
            Some(self.v.index_mut(self.i - 1))
        }
    }
}

```

I am getting the following error:

```rust
error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements
  --> src/lib.rs:16:25
   |
16 | Some(self.v.index_mut(self.i - 1))
   | ^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 11:5...
  --> src/lib.rs:11:5
   |
11 | / fn next(&mut self) -> Option<&'a mut T> {
12 | | if self.i == self.v.len() {
13 | | None
14 | | } else {
... |
17 | | }
18 | | }
   | | _____ ^
note: ...so that reference does not outlive borrowed content
  --> src/lib.rs:16:18
   |
16 | Some(self.v.index_mut(self.i - 1))
   | ^^^^^^
note: but, the lifetime must be valid for the lifetime 'a as defined on the impl at 8:6...
  --> src/lib.rs:8:6
   |
8 | impl<'a, T> Iterator for CustomIter<'a, T> {
   | ^^
   = note: ...so that the expression is assignable:
           expected std::option::Option<&'a mut T>
              found std::option::Option<&mut T>

```

Can someone enlighten me, what is going on and also how to fix `CustomIter` to make it work?

Thanks a lot! 🙂

---

<div class="post-metadata">

**Author:** ![DevinR528](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/devinr528/32/11650_2.png) [@DevinR528](https://users.rust-lang.org/u/DevinR528)\
**Post date:** [October 5, 2019, 12:40pm UTC](https://users.rust-lang.org/t/how-to-implement-a-safe-mutable-iterator-for-vec-t/33297/2 "2019-10-05T12:40:28Z")

</div>

The way I usually do this is like so

```rust
struct Thing(Vec<String>);
impl Thing {
    fn iter_mut(&mut self) -> impl Iterator<Item=&mut String> {
        self.0.iter_mut()
    }
}

```

so if your struct is just a wrapper just pass the functionality up. If you can't do this I found [IterMut](https://rust-unofficial.github.io/too-many-lists/second-iter-mut.html) really helpful

---

<div class="post-metadata">

**Author:** ![schr3da](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/schr3da/32/17940_2.png) [@schr3da](https://users.rust-lang.org/u/schr3da)\
**Post date:** [October 5, 2019, 1:13pm UTC](https://users.rust-lang.org/t/how-to-implement-a-safe-mutable-iterator-for-vec-t/33297/3 "2019-10-05T13:13:10Z")

</div>

A combination of Rc and RefCell might help out. Just did a quick example

> **[Rust Playground](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=006d286cfb10a91260b7a9ad2ec00a9c)**
>
> A browser interface to the Rust compiler to experiment with the language

You can than use the it as ref and borrow it as mutable in your e.g. closure...

Hope it helps

---

<div class="post-metadata">

**Author:** ![Yandros](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/yandros/32/8136_2.png) [@Yandros](https://users.rust-lang.org/u/Yandros)\
**Post date:** [October 5, 2019, 1:45pm UTC](https://users.rust-lang.org/t/how-to-implement-a-safe-mutable-iterator-for-vec-t/33297/4 "2019-10-05T13:45:36Z")

</div>

If you wanna do this as an exercise, do not do `iter_mut()` but just plain old `.iter()`. The semantics of shared references (`& _`) and unique references (`&mut _`), combined with the fact that the items an `Iterator` yields can coexist, lead to `iter_mut` iterators having to prove that despite the different values coexisting their "uniqueness" (non-aliasing) guarantee is not broken. This is almost never expressible with non-`unsafe` Rust, so that's why these `.iter_mut()` variants are _unsafe_. So the trick to avoid using `unsafe` is to rely on these "primitive" constructions already present in the standard library, as @DevinR528 showed. Which sadly does not lead to learning much 😅.

So go and try a non-`unsafe` `.iter()` first.

* * *

To better see how implementing an `.iter_mut()` would go, it would be something like this (note that `.iter_mut()` does not work on a vector but on the slice of heap-allocated elements it points to):

```rust
fn my_slice_iter_mut<'iterator, T : 'iterator> (
    slice: &'iterator mut [T]
) -> impl Iterator<Item = &'iterator mut T> + 'iterator
{
    MySliceIterMut(slice)
}

struct MySliceIterMut<'iterator, T : 'iterator> /* = */ (
    &'iterator mut [T],
);

impl<'iterator, T : 'iterator> Iterator
    for MySliceIterMut<'iterator, T>
{
    type Item = &'iterator mut T;
    
    fn next (self: &'_ mut MySliceIterMut<'iterator, T>)
      -> Option<Self::Item>
    {Some({
        // reborrow for lifetime '_ < 'iterator => Error
        let (head, tail) = self.0.split_first_mut()?;
        self.0 = tail;
        head
    })}
}

```

- [Playground](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=919ad1d07189eeb723de812e11cf3fca)

So, as you can see, there is a `&'_ mut &'iterator mut ...` double reference from the `.next()` function API, and this can only be always collapsed in the `mut` case as `&'_mut ...`, since it would otherwise be possible to break the unicity guarantee which would be unsound.

- In this particular case it would be sound, so it would be a valid use of `unsafe` (to extend the lifetime).

In the non-`mut` case however, that is, a `&'_ mut &'iterator ...` as input; since `&'iterator ...` is `Copy`, _the inner reference can be "copied"_, leading to the double reference being allowed to "collapse" into `&'iterator ...` (resulting in `'_` being extended to `'iterator`, by dropping the `mut`), as needed.

So there is a big difference between `&'iterator mut ...` and `&'iterator ...`.

---

<div class="post-metadata">

**Author:** ![thomas001](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/thomas001/32/12807_2.png) [@thomas001](https://users.rust-lang.org/u/thomas001)\
**Post date:** [October 5, 2019, 2:05pm UTC](https://users.rust-lang.org/t/how-to-implement-a-safe-mutable-iterator-for-vec-t/33297/5 "2019-10-05T14:05:50Z")

</div>

Thanks for all the replies! 🙂

Honestly I don't like `RefCell`, it's safe but runtime checks, isn't it? that feels like tricking the compiler for something me or the compile should be able to do better 😉

What seems to work is combining @Yandros's code with @DevinR528's link. Wrapping a mutable splice reference in an `Option` and using `take` to prevent to keep two mutable references seems to produce safe code:

```rust
fn my_slice_iter_mut<'iterator, T : 'iterator> (
    slice: &'iterator mut [T]
) -> impl Iterator<Item = &'iterator mut T> + 'iterator
{
    MySliceIterMut(Some(slice))
}

struct MySliceIterMut<'iterator, T : 'iterator> /* = */ (
    Option<&'iterator mut [T]>,
);

impl<'iterator, T : 'iterator> Iterator
    for MySliceIterMut<'iterator, T>
{
    type Item = &'iterator mut T;
    
    fn next (self: &'_ mut MySliceIterMut<'iterator, T>)
      -> Option<Self::Item>
    {
        self.0.take().and_then(|v| {
            let (head, tail) = v.split_first_mut()?;
            self.0 = Some(tail);
            Some(head)
        })
    }
}  

```

This completely depends on the ability to do a safe split of a slice, which again is just unsafe code, just one layer deeper. Though I have to admin I don't understand the difference to @Yandros's solution completely 😕

---

<div class="post-metadata">

**Author:** ![Yandros](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/yandros/32/8136_2.png) [@Yandros](https://users.rust-lang.org/u/Yandros)\
**Post date:** [October 5, 2019, 2:20pm UTC](https://users.rust-lang.org/t/how-to-implement-a-safe-mutable-iterator-for-vec-t/33297/6 "2019-10-05T14:20:45Z")

</div>

Using `.take()` is a great trick to go from `&'_ mut Option<&'iterator mut ...>` to `&'iterator mut`, nice idea!

Yes, you end up relying on `.split_[first]_mut()`, which uses `unsafe` in its implementation since it cannot otherwise prove the returned references are disjoint, but it is such an abviously safe and sound function that it is fine 🙂

---

<div class="post-metadata">

**Author:** ![matklad](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/matklad/32/41370_2.png) [@matklad](https://users.rust-lang.org/u/matklad)\
**Post date:** [October 5, 2019, 2:20pm UTC](https://users.rust-lang.org/t/how-to-implement-a-safe-mutable-iterator-for-vec-t/33297/7 "2019-10-05T14:20:57Z")

</div>

Heh, I discuss how to go from slices to safe iterators in [this lecture](https://github.com/matklad/rust-course/blob/master/lectures/11-unsafe/slides.pdf), starting from slide 19. The text is unfortunately in Russian, but the code examples might be helpful.

---

<div class="post-metadata">

**Author:** ![cuviper](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/cuviper/32/3156_2.png) [@cuviper](https://users.rust-lang.org/u/cuviper)\
**Post date:** [October 5, 2019, 4:06pm UTC](https://users.rust-lang.org/t/how-to-implement-a-safe-mutable-iterator-for-vec-t/33297/8 "2019-10-05T16:06:30Z")

</div>

Instead of adding `Option` and `take()`, you can also just replace it with an empty slice temporarily:

[playground](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=e55b595a737b228e1e88faf13d79d7a0)

```rust
impl<'iterator, T: 'iterator> Iterator for MySliceIterMut<'iterator, T> {
    type Item = &'iterator mut T;

    fn next(self: &'_ mut Self) -> Option<Self::Item> {
        let slice = std::mem::replace(&mut self.0, &mut []);
        let (head, tail) = slice.split_first_mut()?;
        self.0 = tail;
        Some(head)
    }
}

```

---

<div class="post-metadata">

**Author:** ![system](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/system/32/51372_2.png) [@system](https://users.rust-lang.org/u/system)\
**Post date:** [January 3, 2020, 4:06pm UTC](https://users.rust-lang.org/t/how-to-implement-a-safe-mutable-iterator-for-vec-t/33297/9 "2020-01-03T16:06:39Z")

</div>

Closed on January 3, 2020, 4:06pm UTC

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.
