Generic lifetime parameter of the iterator creeping into the struct type

Question

I am trying to create a data structure (let's call it Outer) that wraps another data structure (let's call it Inner). However, rather than fixing an implementation for Inner, I want to use a trait so that I can easily swap the implementation of this underlying data structure.

A simplified version would look somewhat like this:

pub struct Outer<K, V, I>
where
    I: Inner<K, V>
{
    inner: I,
    // some phantom data fields
}

pub trait Inner<K, V>
{
    ...
}

Now, I want to add an iterator to Outer which should also wrap an iterator provided by the inner data structure, and here comes the problem.

In the Inner trait, I cannot write:

fn iter(&self) -> impl Iterator<Item = (&'_ K, &'_ V)>;

as impl Trait syntax is not allowed here, and I also cannot introduce an associated type like:

type Iterator<'a>: Iterator<Item = (&'a K, &'a V)>;

since generic associated types are not there yet.

What I came up with so far is to have a separate trait for an iterator:

pub trait InnerIterator<'a, K: 'a, V: 'a>: Iterator<Item = (&'a K, &'a V)> {
    type Inner: Inner<K, V>;

    fn new(inner: &'a Self::Inner) -> Self;
}

Then Outer receives a new generic type parameter InnerIt:

pub struct Outer<K, V, I, InnerIt>
where
    I: Inner<K, V>
{
    inner: I,
    // some phantom data fields
}

impl<K, V, I, InnerIt> Outer<K, V, I, InnerIt> {
    pub fn iter<'a>(&'a self) -> InnerIt
    where
        I: Inner<K, V>,
        InnerIt: InnerIterator<'a, K, V, Inner = I>,
        K: 'a,
        V: 'a,
    {
        InnerIt::new(&self.inner)
    }
}

And now, when I want to pick some specific Inner implementation, I have something like:

pub type SomeOuter<'a, K, V> = Outer<K, V, SomeInner<K, V>, SomeInnerIterator<'a, K, V>>;

and here the lifetime parameter 'a becomes a part of my type definition.

Other than the problem that I would have to add at least two more parameters for enabling iter_mut and into_iter, my question is what would be the consequences of having this 'a parameter there, would it continue to propagate further when using this type, would the user of this type be surprised by this lifetime parameter, and is there a way to implement iterators without introducing generic iterator types and their lifetimes for Outer?

Emoun Emoun · Accepted Answer · 2021-04-06T07:50:12

would it continue to propagate further when using this type

Any type that wants to embed your type would need to also have a lifetime parameter. However, some places lifetime elision will take over (e.g. in function arguments):

struct Struct1<'a>(std::marker::PhantomData<&'a ()>);
struct Struct2<'a>(Struct1<'a>); // lifetime propagates to Struct2

fn func(_: Struct1){
    println!("lifetime not needed. It is 'elided'");
}

would the user of this type be surprised by this lifetime parameter

They shouldn't be. In rust, lifetime are everywhere. For example, iterating over a slice is done using a struct with a lifetime parameter.

is there a way to implement iterators without introducing generic iterator types and their lifetimes for Outer?

The reason why you have a lifetime parameter is that you have an iterator that returns a reference. If your iterator would return a direct object no lifetime would be needed. For example, if you turn a vector into an iterator (which thus returns all the elements in the vector) it won't need a lifetime parameter

Generic lifetime parameter of the iterator creeping into the struct type

1 Answers