Mapping slices, RandomAccessIterator

help
1

I came across a situation recently where I needed function to accept a randomly-accessible collection (so generally a slice), which contains values of some Item type, but the caller had a slice of a containing type.
In pseudo-rust:

fn produce() -> Vec<Entry> {...}
fn consume(slice: &[Item]) {...}
struct Entry { item: Item, ... }

fn main() {
  let entries = produce();
  let items = entries.into_iter().map(|e|e.item).collect::<Vec<_>>();
  consume(&items);
}

The problem with this, as I see it, is that collect. Ideally I'd just pass an iterator rather than using an intermediate collect, but consume needs random access (really, it needs to iterate the slice multiple times), so a plain iterator won't do. So, I had the idea to pass the slice with an extra lens-like parameter, like so:

fn consume<T>(slice: &[T], lens: fn(&T) -> &Item) {...}

fn main() {
  let entries = produce();
  consume(&entries, |e| e.item);
}

The advantage here is that I get the random/repeated access without needing the slice to be the exact type, but the disadvantage is that the signature of consume is more obscure.

I think my ideal would be to abstract the slice and lens behind some trait that exposes a random-access collection, e.g.

fn consume<T>(slice: impl RandomAccessIterator<&Item>) {...}
fn main() {
  let entries = produce();
  let items = entries.random_access().map(|e|e.item);
  consume(&items);
}

I was briefly tricked by google into thinking an unstable RandomAccessIterator existed in std, but it seems this particular documentation is way out of date.

I guess my question is, is there an idiom for expressing something like this today, ideally without needing the extra collect or the extra explicit parameter? Are there any obvious flaws with my approach?

2

If you just want to iterate multiple times in consume you can:

  • take an impl Iterator<Item = &Item> + Clone in consume
  • clone the iterator when you need to iterate
  • pass it entries.iter().map(|e| &e.item) (notice the .iter() instead of .into_iter(), which produces an Iterator that is very cheaply cloneable)
1 Like
3

I can think of two possible solutions, method one is to use AsRef<Item> (or maybe Borrow<Item>, but notice the semantic difference); method two is to use Index<usize, Output=Item>, but you'll need a new type wrapper around Vec<Entry> due to the orphan rule.

fn consume1<Entry>(slice: &[Entry]) where Entry: AsRef<Item> {}
fn consume2<Slice>(slice: &Slice) where Slice: Index<usize, Output=Item> {}
4

If you want to sugar the access a bit you can use this extension trait

trait RandomAccessIterator : Iterator + Clone {
    fn get(&self, idx: usize) -> Option<Self::Item> {
        self.clone().nth(idx)
    }
}

impl<T: Iterator + Clone> RandomAccessIterator for T {}

Use ExactSizeIterator as an additional bound so you can get the number of elements if you need it.

1 Like