Most efficient way to fill a vector from back to front

Question

I am trying to populate a vector with a sequence of values. In order to calculate the first value I need to calculate the second value, which depends on the third value etc etc.

let mut bxs = Vec::with_capacity(n);

for x in info {
    let b = match bxs.last() {
        Some(bx) => union(&bx, &x.bbox),
        None => x.bbox.clone(),
    };
    bxs.push(b);
}
bxs.reverse();

Currently I just fill the vector front to back using v.push(x) and then reverse the vector using v.reverse(). Is there a way to do this in a single pass?

Answer 1

Is there a way to do this in a single pass?

If you don't mind adapting the vector, it's relatively easy.

struct RevVec<T> {
    data: Vec<T>,
}

impl<T> RevVec<T> {
    fn push_front(&mut self, t: T) { self.data.push(t); }
}

impl<T> Index<usize> for RevVec<T> {
    type Output = T;
    fn index(&self, index: usize) -> &T {
        &self.data[self.len() - index - 1]
    }
}

impl<T> IndexMut<usize> for RevVec<T> {
    fn index_mut(&mut self, index: usize) -> &mut T {
        let len = self.len();
        &mut self.data[len - index - 1]
    }
}