Can't flatten, enumerate, and then reverse iterator

help
1

I tried to flatten, enumerate, and reverse a Vec of Vecs and it gave me a compiler error.

What's weirder is that if I remove the enumerate step, OR if I remove the flatten step, it does work. It just doesn't work with both of them. And if I collect right before reversing, it does work.

(By not work, I mean it gives me a compiler error about it not implementing ExactSizeIterator).

It there some reason that this shouldn't work? I might just be missing something obvious.

#[allow(unused)]
fn main() {
    let v = vec![vec!["a", "b", "c"], vec!["d", "e"], vec!["f"]];
    
    
    let not_flattened = v.iter().enumerate().rev();
    let not_enumerated = v.iter().flatten().rev();

    let with_collect = v
        .iter()
        .flatten()
        .enumerate()
        .collect::<Vec<_>>()
        .iter()
        .rev();

    // errors:
    let v = v.iter().flatten().enumerate().rev();
}

(Playground)

Errors:

   Compiling playground v0.0.1 (/playground)
error[E0277]: the trait bound `Flatten<std::slice::Iter<'_, Vec<&str>>>: ExactSizeIterator` is not satisfied
    --> src/main.rs:18:44
     |
18   |     let v = v.iter().flatten().enumerate().rev();
     |                                            ^^^ the trait `ExactSizeIterator` is not implemented for `Flatten<std::slice::Iter<'_, Vec<&str>>>`, which is required by `Enumerate<Flatten<std::slice::Iter<'_, Vec<&str>>>>: DoubleEndedIterator`
     |
     = help: the following other types implement trait `ExactSizeIterator`:
               &mut I
               Args
               ArgsOs
               ArrayChunksMut<'_, T, N>
               ArrayWindows<'_, T, N>
               Box<I, A>
               Chunks<'_, T>
               ChunksExact<'_, T>
             and 124 others
     = note: required for `Enumerate<Flatten<std::slice::Iter<'_, Vec<&str>>>>` to implement `DoubleEndedIterator`
note: required by a bound in `rev`
    --> /playground/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/iter/traits/iterator.rs:3350:23
     |
3348 |     fn rev(self) -> Rev<Self>
     |        --- required by a bound in this associated function
3349 |     where
3350 |         Self: Sized + DoubleEndedIterator,
     |                       ^^^^^^^^^^^^^^^^^^^ required by this bound in `Iterator::rev`

For more information about this error, try `rustc --explain E0277`.
error: could not compile `playground` (bin "playground") due to 1 previous error
2

Yes. enumerate tags items with an index in the order of iteration. If you then want to reverse that iterator, the enumerated iterator needs to be able to count down instead of counting up. That only can work if the length of the iterator (and thus the index for the originally last item) is known in advance, which is why the standard library restricts this impl:

impl<I> DoubleEndedIterator for Enumerate<I>
where
    I: ExactSizeIterator + DoubleEndedIterator,

Note that “DoubleEndedIterator” means as much as “iterator that can be reversed”, and “ExactSizeIterator“ means “iterator whose exact size is always known in advance”.

The trait impl thus says “some_iter.enumerate() can be reversed if some_iter can be reserved and some_iter’s exact size is always known in advance”.

Finally, a flattened iterator can’t have a size that’s known in advance, because the size depends on the concrete lengths of the inner collections (in this case Vec<&str>s), and those aren’t clear from the type.

3 Likes
3

If you try to reverse an iterator, it needs to be able to iterate from the back and get the same results. The enumerate turns the sequence into a tuple of (pos, elem), which means to have Enumerate: DoubleEndedIterator, the inner iterator must be ExactSizeIterator so .enumerate() can determine what position is the end of the iterator to start from there (this impl).

This is fine for a normal Vec iterator, but you also flatten, making the length of the iterator no longer known. How should enumerate determine what index should be at the end of the iterator?

(Collecting fixes this because the intermediate Vec eagerly evaluates the iterator, meaning the length of the flattened iterator is properly known).

You can fix this by precalculating the length of the inner iterator:

let iter = v.iter().flatten();
// This clone just clones the iterator, not all the Vecs
let length = iter.clone().count();
let reversed = iter
    .zip(0..length)
    .rev();
2 Likes
4

Oh I see, so .flatten().rev() works because it can be reversed without knowing the length, and .enumerate().rev() works because it knows the length, but they don't work together because flatten erases the length info that enumerate needs.

Thank you so much!

1 Like
5

I think I still need to collect. The zipping seems to get rid of the ExactSize-ness as well. (playground)

6

You didn’t save your playground, the link is the same as in the OP :wink:

7

You can reverse first, then zip the reversed range:

v.iter()
        .flatten()
        .rev()
        .zip((0..v.iter().map(|v| v.len()).sum::<usize>()).rev())

(playground)

8

The zipping gets rid of the DoubleEnded…-ness (unless both iterators being zipped have ExactSize…). Zip operates left-to-right, stopping as soon as the first of the zipped iterators runs out of items.

So if you want to start iterating it from the end, that doesn’t usually work because you can’t match up the iterator items in the same way from the back (the rule with rev() is that is should yield the same items as forwards iteration, just in reversed order); the only possible exception is if it can pre-compute which iterator is longer and by how much, then it can skip the past-the-end elements of the longer iterator to sort-of bring the two in sync from the back.

1 Like
9

ooh that's a good idea! (and it works :])

thank you!

10

ah, that makes sense