Create an Iterator in Rust that yields pairs of mutable references to elements of the slice, along with an iterator over the remaining elements

Question

I can achieve the desired behaviour without a custom Iterator by using a free function and an fn pointer:

use std::slice::Iter;
use std::iter::Chain;

///Apply the function f to each element of the slice and the iterator of the remaining elements
pub fn cross<T>(slice: &mut [T], f: fn (&mut T,  Chain<Iter<'_,T>, Iter<'_,T>>)) {
    for i in 0..slice.len() {
        let (preceding, subsequent) = slice.split_at_mut(i);
        let (current_entity, subsequent) = subsequent.split_first_mut().unwrap();
        let iter = preceding.iter().chain(subsequent.iter());
        f(current_entity, iter);
    }
}

This can be used like so:

let mut testvec = vec![1,2,3,4,5];

cross(&mut testvec, |elem, rest| {
    println!("{} {:?}", elem, rest.collect::<Vec<_>>());
});

Which prints:

1 [2, 3, 4, 5]
2 [1, 3, 4, 5]
3 [1, 2, 4, 5]
4 [1, 2, 3, 5]
5 [1, 2, 3, 4]

However when I tried to make this into a custom Iterator struct, I get a lifetime error:

use std::slice::Iter;
use std::iter::Chain;

/// yield pairs of mutable references to elements of the slice, along with an iterator over the remaining elements
pub struct CrossIter<'a, T> {
    slice: &'a mut [T],
    index: usize,
}

impl<'a, T> CrossIter<'a, T> {
    pub fn new(slice: &'a mut [T]) -> Self {
        CrossIter {
            slice,
            index: 0,
        }
    }
}

/// yield pairs of mutable references to elements of the slice, along with an iterator over the remaining elements
impl<'a, T> Iterator for CrossIter<'a, T> {
    type Item = (&'a mut T, Chain<Iter<'a, T>, Iter<'a, T>>);

    fn next(&mut self) -> Option<Self::Item> {
        if self.index < self.slice.len() {
            let (preceding, subsequent) = self.slice.split_at_mut(self.index);
            let (current_entity, subsequent) = subsequent.split_first_mut().unwrap();
            let iter = preceding.iter().chain(subsequent.iter());
            self.index += 1;
            Some((current_entity, iter))
        } else {
            None
        }
    }
}

fn main() {
    let mut textvec = vec![1, 2, 3, 4, 5];
    let iter = CrossIter::new(&mut textvec);

    for (elem, rest) in iter {
        println!("{} {:?}", elem, rest.collect::<Vec<_>>());
    }
}

The error is:

error: lifetime may not live long enough
  --> src\iterator.rs:27:13
   |
18 | impl<'a, T> Iterator for CrossIter<'a, T>  where Self: 'a {
   |      -- lifetime `'a` defined here
...
21 |     fn next(&mut self) -> Option<Self::Item> {
   |             - let's call the lifetime of this reference `'1`
...
27 |             Some((current_entity, iter))
   |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ method was supposed to return data with lifetime `'a` but it is returning data with lifetime `'1`
   |
   = note: requirement occurs because of a mutable reference to `T`
   = note: mutable references are invariant over their type parameter
   = help: see <https://doc.rust-lang.org/nomicon/subtyping.html> for more information about variance

I think I understand the error. The signature of next for Iterator expects that the yielded values have the generic lifetime 'a. 'a is the lifetime of the slice inside CrossIter. However, instead it yields something with the same lifetime as self (i.e '1) where self is a reference to the instance of the CrossIter struct.

I think I need to tell it that the slice that the CrossIter borrows will live at least as long as the CrossIter itself.

How can I fix this?

Answer 1

Following on from Chayim's answer, I have written a Lending Iterator that achieves this.

use std::slice::Iter;
use std::iter::Chain;

/// yield pairs of mutable references to elements of the slice, along with an iterator over the remaining elements
pub struct CrossIter<'slice, T> {
    slice: &'slice mut [T],
    index: usize,
}

impl<'slice, T> CrossIter<'slice, T> {
    pub fn new(slice: &'slice mut [T]) -> Self {
        CrossIter {
            slice,
            index: 0,
        }
    }
}

pub trait LendingIterator {
    type Item<'a> where Self: 'a;
    fn next<'a>(&'a mut self) -> Option<Self::Item<'a>>;
}

/// yield pairs of mutable references to elements of the slice, along with an iterator over the remaining elements
impl<'slice, T> LendingIterator for CrossIter<'slice, T> {
    type Item<'a> = (&'a mut T, Chain<Iter<'a, T>, Iter<'a, T>>) where Self: 'a;

    fn next<'a>(&'a mut self) -> Option<Self::Item<'a>> {
        if self.index < self.slice.len() {
            let (preceding, subsequent) = self.slice.split_at_mut(self.index);
            let (current_value, subsequent) = subsequent.split_first_mut().unwrap();
            let chain_of_rest = preceding.iter().chain(subsequent.iter());
            self.index += 1;
            Some((current_value, chain_of_rest))
        } else {
            None
        }
    }
}

pub trait IntoCrossIter<'a, T> {
    fn cross(self) -> CrossIter<'a, T>;
}

impl<'a, T> IntoCrossIter<'a, T> for &'a mut [T] {
    fn cross(self) -> CrossIter<'a, T> {
        CrossIter::new(self)
    }
}

This can be used like so:

fn main() {
    let mut testvec = vec![1, 2, 3, 4, 5];
    let mut iter = testvec.cross();
    while let Some((elem, rest)) = iter.next() {
        println!("{} {:?}", elem, rest.collect::<Vec<_>>());
    }
}

Which outputs:

1 [2, 3, 4, 5]
2 [1, 3, 4, 5]
3 [1, 2, 4, 5]
4 [1, 2, 3, 5]
5 [1, 2, 3, 4]

Answer 2

Unfortunately, this cannot be done.

The reason is that iterators, as defined, allow you to keep elements yielded in different times together. This is necessary for e.g. collect() to work, as it puts all elements together in a collection.

But this property is fundamentally incompatible with your iterator: for example, in the first iteration you yield an iterator that contains element two, and in the next iteration you yield a mutable reference to it. If you keep both alive, you can obtain a reference to element two from the iterator, and have a mutable and immutable references to it coexisting, which is disallowed with Rust.

The reason it worked with your function is because it does not allow you to keep two elements alive at the same time: it only allows you to iterate over them one-by-one.

There is some desire for so-called lending iterators, or streaming iterators, that will have the same property as your function: not allowing items yielded in different iterations to coexist. With GAT (Generic Associated Types) available, it is possible to write such trait (LendingIterator), but it is not defined in the standard library (yet) and there is no syntax sugar for it (like for loops).