Swap out Vec<>.iter() with Vec<>.iter().rev() in-place?

1

I'm trying to iterate over a vector of things several times, and on every pass i want to reverse the order that I iterate over them.

I think I could do this by mutating the vector on every pass, but I'd like to be able to use Vec.iter().rev() so that I don't have to save the results.

I'm running into a compiler error that says the thing I'm trying to save is of the wrong type, since a Vec.iter().rev() is actually a std::iter::Rev<std::slice::Iter<'_, _>> and not a std::slice::Iter<'_, _> :confused:

Any advice for how I should do this differently?

Playground example demonstrating my error:

Thanks!

Edit, code snippet for people who don't want to click:

fn main() {
    let v: Vec<i32> = vec![1, 2, 3];
    for i in 1..6 {
        let current = if i % 2 == 0 { v.iter() } else { v.iter().rev() };
        for e in current {
            println!("TURN {}: {}", i, e);
        }
    }
}
2

The compiler is right. Iterators are small structures that hold descriptions on how to iterate, and each way to iterate is a different type of struct.

You can work around it by using dynamic dispatch.

Dynamic dispatch works only through Box or references. To have a reference to something, you first have to store it somewhere permanently.

So:

let mut forward;
let mut reverse;
let current: &mut dyn Iterator<Item=_> = if i % 2 == 0 { forward = v.iter(); &mut forward }
 else { reverse = v.iter().rev(); &mut reverse };
2 Likes
3

Or use the either crate: example

You can build a similar enum yourself, but why bother? :slight_smile:

3 Likes
4

Trying to follow how this works... what does the syntax of following an assignment statement with &mut identifier do?

5

This looks... good.

How does this work? What is current now and how can it be easily iterated over where my let current = if ... { v.iter() } else { v.iter().rev() } cannot? I'm missing something fundamental in my understanding of Rust to see how this is suddenly allowed.

6

Here is a version using a custom iterator impl with an enum. The Either enum is a generalization of this, but I'm showing the tailor made one in hopes it cuts through the abstraction a bit.

The type of current in my original example is Either<std::slice::Iter<...>, std::iter::Rev<std::slice::Iter<...>>>, just like the CustomItr I wrote by hand above. So you've unified the two possible types using an enum.

To help you in understanding, let me ask a question: what do you think the type of current would be if your code compiled? Or what did you expect it to be in your mental model of Rust?

1 Like
7

It causes the compiler to create a trait object - "trait object" is a term you can find a lot of info about in the Rust docs/book. Happy to answer more here, but I suspect you'll get a bunch of value by reading up on that first, rather than me describe the same material (in fewer words :slight_smile:).

1 Like
8

Oh -- yeah that makes a lot of sense now. Your example helps me understand the crate itself way better, since they're doing what you are but with a helper macro:

macro_rules! either {
    ($value:expr, $pattern:pat => $result:expr) => (
        match $value {
            Either::Left($pattern) => $result,
            Either::Right($pattern) => $result,
        }
    )
}

...

fn next(&mut self) -> Option<Self::Item> {
    either!(*self, ref mut inner => inner.next())
}
9

Previous version wanted to have a specific iterator type known exactly at compile time. It wanted to store all the bytes of the iterator in the variable.

The dyn version only gives rough promise of something iterator-like hidden behind a reference, and makes code do work at run time to figure out which one is it exactly.

1 Like
10

I had earlier fixed this kind of bug with a .collect() like this:

        let current: Vec<_> = if i % 2 == 0 { 
            v.iter().collect() 
            
        } else { 
            v.iter().rev().collect() 
            
        };

Is this a particularly bad way to solve it? Where should I look to learn the performance differences between the three approaches discussed in this thread, like speed, compiler-time, memory use, runtime concerns? Which of the three feels the most idiomatic to a Rust programmer?

11

If you needed the collect() anyway, that's a great way to solve it -- there's no dynamic dispatch involved inside the iterator operations in that approach.

12

Calling collect() will copy all the data into a new vector, so intuitively i'd say it's slower than using a trait object with dynamic dispatch (unless, as @scottmcm said, you need to do that anyway for some other reason). That said, if this is a performance critical part of your app, you could benchmark the two versions and compare.