How to advance Map iterator without calling the function?

Is there a way to skip a mapped iterator without evaluating the function in the map?

I.e.

fn expensive(i: usize) -> usize {
    println!("{i}");
    i
}

fn main() {
    let data = vec![0, 1, 2, 3, 4];

    let a: Vec<usize> = data.into_iter().map(expensive).skip(2).collect();

    println!("{a:?}")
}

is there an API to allow "pushing" the skip across the map? In the example above I would like the resulting stdout to be

2
3
4
[2, 3, 4]

Why not .skip(2).map(…), then?

because what is being skipped may only known after the iterator has been created.

An example is to allow the following iterator adapter:

/// An iterator adapter that converts an iterator over items into an iterator over slices of
/// those N items.
///
/// This iterator is best used with iterators that implement specialized `nth` since skipping items
/// allows this iterator to skip sequences of items without having to call each of them.
struct SliceFilteredIter<I> {
    iter: I,
    selected_rows: VecDeque<(usize, usize)>,
    current_remaining: usize,
    current: usize, // position in the slice
}

(the comment is not correct because nth does not really skip items efficiently).

if I is an (expensive) mapped iterator, there is no benefit in using this adapter / this design.

Sorry I don't follow. If you want to conditionally filter and project, use .filter_map(). That isn't really clear from the application of skip(), though, since it's not what skip does. Can you show your current impl for the above iterator type?

/// An iterator adapter that converts an iterator over items into an iterator over slices of
/// those N items.
///
/// This iterator is best used with iterators that implement `nth` since skipping items
/// allows this iterator to skip sequences of items without having to call each of them.
#[derive(Debug, Clone)]
pub struct SliceFilteredIter<I> {
    iter: I,
    selected_rows: VecDeque<(usize, usize)>,
    current_remaining: usize,
    current: usize, // position in the slice
}

impl<I> SliceFilteredIter<I> {
    /// Return a new [`SliceFilteredIter`]
    pub fn new(iter: I, selected_rows: VecDeque<(usize, usize)>) -> Self {
        Self {
            iter,
            selected_rows,
            current_remaining: 0,
            current: 0,
        }
    }
}

impl<T, I: Iterator<Item = T>> Iterator for SliceFilteredIter<I> {
    type Item = T;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        if self.current_remaining == 0 {
            if let Some((start, length)) = self.selected_rows.pop_front() {
                // skip the hole between the previous start end this start
                // (start + length) - start
                let item = self.iter.nth(start - self.current);  ///////////// <<<<------------ here; I need to skip the iterator by N; if this was a slice, I could have used pointer arithmetic.
                self.current = start + length;
                self.current_remaining = length - 1;
                item
            } else {
                None
            }
        } else {
            self.current_remaining -= 1;
            self.iter.next()
        }
    }
}

If your question boils down to manipulating some arbitrary inner iterator of a Map:

use std::iter::Map;
fn foo<I, F>(maybe_expensive_iterator: Map<I, F>)
where
    I: Iterator,
    F: FnMut(<I as Iterator>::Item) -> MyFavoriteType,
{
    // Can I advance `I` without calling `F`?
}

then no, though it may optimize out in very select cases (when the compiler determines there's no side effects it need preserve).

You could make your own Map-like iterator that has this ability.

If F is a closure you control, you could perhaps build that state into the closure (capture an &AtomicUsize or something).

If the Map is recreateable and you control I, you could map &mut I, use the mapped iterator for awhile, get rid of it, manipulate I (e.g. advance it), then map &mut I again.

3 Likes

The main issue is that Map does not have any special handling in its Iterator impl. The only associated methods defined are next(), size_hint(), try_fold(), and fold(), and the rest just delegate to the generic Iterator definitions. Therefore, since the resulting Map can only be advanced through its next() method, all of the generic nth(), advance_by(), etc. methods are forced to call the function repeatedly. So the best you can hope for is for the compiler to optimize out the function if the result is not used. (Since the function can have side effects, this is not always possible.)

3 Likes

It doesn't look like SliceFilteredIter needs to advance iter to know how many elements to skip, so can't you just wrap it in a Map?

It knows how many elements to skip, but to actually skip them it must call the nth() function, which calls next() repeatedly unless the underlying iterator redefines nth().