How to iterate over generic member collection (without cloning it)?

help
1

Hi everyone,

I want to implement a struct which uses a generic collection (e.g. Vec, HashSet,...) to store seen values.

So I wrote it like this:

struct mydata <T> { //where T is the generic collection
    collection: T,
}

Now the problem:
How do I iterate over this collection (without cloning it)?

I tried it with the IntoIterator trait:

impl <T: IntoIterator<Item=u8> [...] > mydata<T> {
    fn dosomething(&self){
        for x in self.collection.into_iter().filter(|x| *x==5) {
            println!("{:?}",x);
        }
    }
}

But, of course, that gives me E0507: cannot move out of borrowed content.

Normally I would use the iter(&self) instead of into_iter(self), but afaik there is not trait for it.

Any idea?

3

No GATs are required here, although we need to obtain a borrowing iterator from the inner collection. Luckily, collections implement IntoIterator for references to those collections, yielding references to those items.

Playground

Also note that the usual naming convention for struct names is UpperCamelCase, and snake_case for functions: we'd recommend renaming to struct MyData and do_something.

3 Likes
4

seems to be working just as intended.
Thank you very much.

5

Taking @Enet4's example,

struct MyData<Collection> {
    collection: Collection,
}

impl<Collection> MyData<Collection>
where
    for</*all*/ 'iter> &'iter Collection: IntoIterator<Item = &'iter u8>,
{
    fn do_something (self: &'_ Self)
    {
        self.collection
            .into_iter()
            .filter(|&&x| x == 5)
            .for_each(|x| {
                println!("{:?}", x);
            });
    }
}

It is best if the bound is written on the function requiring it (allows adding to the same impl block other methods / functions that do not require such bounds):

impl<Collection> MyData<Collection>
{
    fn do_something (self: &'_ Self)
    where
        for</*all*/ 'iter> &'iter Collection: IntoIterator<Item = &'iter u8>,
    {
        self.collection
            .into_iter()
            .filter(|&&x| x == 5)
            .for_each(|x| {
                println!("{:?}", x);
            });
    }
}

which, with lifetime elision, becomes:

impl<Collection> MyData<Collection>
{
    fn do_something<'call_site> (self: &'call_site Self)
    where
        for</*all*/ 'iter> &'iter Collection: IntoIterator<Item = &'iter u8>,
    {
        self.collection
            .into_iter()
            .filter(|&&x| x == 5)
            .for_each(|x| {
                println!("{:?}", x);
            });
    }
}

  • (I have named the anonymous lifetime 'call_site, since that is whence Rust picks it).

  • Note: we always have Self : 'call_site, i.e., all the borrows contained in Self (if any) outlive (live at least as long as) 'call_site, or in other words: the 'call_site borrow of Self cannot be longer than any borrow contained within Self.

This is interesting, because in our example Self is generic over Collection, and Collection may be borrowing data:

// This can be our Collection
struct BorrowedBytes<'bytes> {
    borrowed_bytes: &'bytes [u8],
}

impl<'bytes, 'iter> IntoIterator
    for &'iter BorrowedBytes<'bytes>
where
    'bytes : 'iter, // the borrowed bytes must live at least as long as the into_iter() borrow
{
    type IntoIter = ::std::slice::Iter<'iter, u8>;
    type Item = &'iter u8;
    
    fn into_iter (
        self: &'iter BorrowedBytes<'bytes>,
    ) -> Self::IntoIter
    {
        self.borrowed_bytes.into_iter()
    }
}

The issue here is that @Enet4's HRTB:

    fn do_something<'call_site> (self: &'call_site Self)
    where
        for</*all*/ 'iter> &'iter Collection: IntoIterator<Item = &'iter u8>,

requires that &'iter Collection be defined for all (unbounded) lifetimes 'iter:

  • since &'a T is only (well-)defined when T : 'a, we get that:

    for</*all*/ 'iter> Collection : 'iter

    i.e.,

    Collection : 'static

    i.e.,

    Collection cannot borrow a local (variable).

And indeed if we combine @Enet4's HRTB having an explicit for<'iter> Collection : 'iter with my BorrowedBytes struct, we get a compilation error:

error[E0716]: temporary value dropped while borrowed
  --> src/main.rs:44:54
   |
43 | /     MyData {
44 | |         collection: BorrowedBytes { borrowed_bytes: &vec![1, 2, 5] },
   | |                                                      ^^^^^^^^^^^^^ creates a temporary which is freed while still in use
45 | |     }
46 | |     .do_something()
   | |___________________- argument requires that borrow lasts for `'static`
47 |   }
   |   - temporary value is freed at the end of this statement

This is quite saddening, given that we never use that Collection : 'static (we never really needed it; the bound just came from the overly strong semantics of HRTB (unbounded universal lifetime parameters)).

Solution

Instead of using HRTB's unbounded universal ("for all") lifetime parameters, we can just use our classic bounded lifetime parameters:

impl<Collection> MyData<Collection>
{
    fn do_something<'iter, 'call_site : 'iter> (self: &'call_site Self)
    where
        &'iter Collection: IntoIterator<Item = &'iter u8>,
    {

And if we think about it, we can even choose 'iter = 'call_site:

impl<Collection> MyData<Collection>
{
    fn do_something<'call_site> (self: &'call_site Self)
    where
        &'call_site Collection: IntoIterator<Item = &'call_site u8>,
    {
2 Likes
6

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