Entry API for Vec?

1

I need to compute N elements, and cache them in a Vec. However, I the Vec that may already have x <= N elements in cached in it.

In C I'd do something like:

    for i in 0..10 {
        let val = vec.get(i);
        
        if val.is_none() {
            vec.push(compute(i));
        }
        
        let val = vec[i];
    }

But with lifetimes involved I'm struggling to find non-awkward solution: Rust Playground

Is there a nice way to achieve this?

2

I've realised I've simplified my code too much for this question, since here you could replace vec.get(i) with vec.len() <= i, but in my reall, messy code I actually iterate two vecs in parallel, because I want to peek the other vec's value if it exists. So assume vec.get(i) at the top is mandatory :slight_smile:

3

Can you elaborate how a second vector changes the picture?
In the example you don't ever use the Some variant of val, so why do you need the get call?

4 
pub fn next(&mut self, ranges_a: &mut Vec, ranges_b: &mut Vec) -> Result<(), io::Error> {
    let (a_none, b_none, size) = {
        let a = ranges_a.get(self.index);
        let b = ranges_b.get(self.index);

        let size = a.map(|a|a.size).or(b.map(|b|b.size)).unwrap_or(self.last_size * 4);
        (a.is_none(), b.is_none(), size)
    };

    if a_none {
        ranges_a.push(compute(…, size));
    }
    if b_none {
        ranges_b.push(compute(…, size));
    }

    compare(ranges_a[self.index], ranges_b[self.index]);
}
5

I don't get it. That doesn't compile, does it?
Is that what you want to write but doesn't compile or what you have to write but you don't like?

6

I'm not 100% sure what you're trying to do, but in the future with non-lexical lifetimes, at least pattern-matching equivalents should work - i.e. this won't be a lifetime error:

let last = if let Some(x) = vec.get(i) {
    x
} else {
    vec.push(whatever);
    vec.last().unwrap()
};

(But I don't think unwrap_or would work.)

The else part of that is awkward, but with another future feature, placement-new, I think it could be fully replaced with the expression vec <- whatever, which would append whatever to the vector and return a reference to it.

For now, I think you have to do it the ugly way. Your use case seems somewhat similar to that of VecMap, but that's a wrapper around Vec<Option<T>>, not Vec<T>. That is, indices may be omitted (but the map is densely populated enough that it makes sense to just represent it with a Vec rather than a proper hash map).

7

Two things that I don't like in the current solution:

  • I have to create another inner scope to peek the values.
  • I have to re-read elements from the vecs, since the initial get couldn't safely outlive the push.

HashMap has exactly the same problem, but solves it with the Entry API. I didn't see any such solution for Vec, so I was wondering if I missed some obvious alternative solution.

8

Well, you could just use a HashMap. :wink:

An entry API for Vec is not really straight forward. You cannot just insert a new element at an arbitrary index that is larger than the size.
You could always implement your own entry API that just returns an Option<Entry> or panics if the index is greater than the size, but I'm not sure if that's more elegant.

9

Yup. Thanks.