How do I write a custom `IntoIterator` implementation that simply reverses the iteration?

Question

I'm a Rust newbie and I'm trying to implement a custom struct that has Vec. I'd like this custom struct to be iterable and that iterates on the inner Vec in reverse order.

So far what I understood is that I need to implement the IntoIterator trait and eventually a custom Iterator to which the IntoIterator transforms the custom struct. Since I just want to reverse the iteration on the Vec, I was thinking to re-use what the standard lib offers already.

This is my struct:

pub struct BitMap {
    content: Vec<u64>,
}

and this is how I was trying to implement the IntoIterator:

impl<'a> iter::IntoIterator for &'a BitMap {
    type Item = u64;
    type IntoIter = iter::Rev<slice::Iter<'a, Self::Item>>;

    fn into_iter(self) -> Self::IntoIter {
        (&(self.content)).iter().rev()
    }
}

But the compiler complains about:

47  |     type IntoIter = iter::Rev<slice::Iter<'a, Self::Item>>;
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected `u64`, found reference

I'm struggling to understand how I can achieve this simple thing.

UPDATE

Thanks E_net4 says don't copy that for your answer!

Considering that you mentioned that your solution would require copying the elements, I tried to implement a version that tries to avoid it and this is what I came up with:

impl<'a> iter::IntoIterator for &'a BitMap {
    type Item = u64;
    type IntoIter = BitMapIterator<'a>;

    fn into_iter(self) -> Self::IntoIter {
        BitMapIterator::new(&self.content)
    }
}

pub struct BitMapIterator<'a> {
    content: &'a Vec<u64>,
    index: usize,
}

impl<'a> BitMapIterator<'a> {
    fn new(content: &'a Vec<u64>) -> Self {
        BitMapIterator {
            content,
            index: content.len(),
        }
    }
}

impl iter::Iterator for BitMapIterator<'_> {
    type Item = u64;

    fn next(&mut self) -> Option<Self::Item> {
        if self.index == 0 {
            None
        } else {
            self.index -= 1;
            Some(self.content[self.index])
        }
    }
}

But as you can see, this required me to implement also a custom Iterator and make it public. This seems to do what I want and if I'm understanding correctly without copying the elements, but I don't know how idiomatic this solution is and it basically doesn't re-use anything provided by std lib.

Please avoid [building up follow-up questions on the same post](https://meta.stackoverflow.com/a/290747). Nevertheless, you might have misunderstood what the copy adaptor does, so I have edited the answer. It does not eagerly make a copy of the struct, so it does not need to allocate any extra memory. — E_net4, Apr 29 '21 at 07:50
You're right, sorry for the follow-up. Thanks for mentioning what the `copy` does and specifying that it's not eager. On the other hand, am I correct in assuming that the snippet I posted in the update avoids copying at all? Despite being the cost of copying `u64` low, I'm thinking at scenarios where the size of the `Vec` could be huge such as 2^64. — se7entyse7en, Apr 29 '21 at 12:43
There is still a copy from the moment you do `self.content[self.index]`. The syntax will implicitly dereference that position in the vector, which still requires a copy because values cannot be moved out of a borrow. Relevant questions: https://stackoverflow.com/questions/27904864 https://stackoverflow.com/questions/51344641 I would say that your implementation is very unlikely to bring any performance or efficiency improvements. — E_net4, Apr 29 '21 at 13:22

E_net4 · Accepted Answer · 2021-04-29T18:40:30.697

4

Calling .iter() on a vector creates a non-owning iterator of items, which will be behind immutable references. And an iterator of &u64 items does not fulfill the role of an iterator of u64 items.

Considering that u64 is cheap to copy, adapting that iterator with .copied is enough to obtain an iterator returning the actual values. A copied iterator is lazy, leaving that it only copies the items as they are traversed.

use std::{iter, slice};

pub struct BitMap {
    content: Vec<u64>,
}

impl<'a> iter::IntoIterator for &'a BitMap {
    type Item = u64;
    type IntoIter = iter::Copied<iter::Rev<slice::Iter<'a, Self::Item>>>;

    fn into_iter(self) -> Self::IntoIter {
        self.content.iter().rev().copied()
    }
}

Playground

How do I write a custom `IntoIterator` implementation that simply reverses the iteration?

1 Answers1