Set-anywhere for Vec?

1

Something like the following seems like it would be a common need for working with Vecs... is there a standard crate that supplies this?

Playground

trait VecExt<T: Clone + Default> {
    fn set_index(&mut self, index:usize, value:T);
}

impl <T: Clone + Default> VecExt<T> for Vec<T> {
    fn set_index(&mut self, index:usize, value: T) {
        if self.len() <= index {
            self.resize(index+1, T::default());
        }
        
        unsafe {
            let elem = self.get_unchecked_mut(index);
            *elem = value;
        }
    }
}
2

It does exist, but builtin and not as a separate a crate. There is an IndexMut impl for Vec.

3

Isn't this just Vec's IndexMut implementation? You can already do v[i] = foo;

4

When I try to set it directly like that I get:

thread 'main' panicked at 'index out of bounds: the len is 0 but the index is 0'
5

One of the problems with this kind of method is that most people would want a panic if you did something like vec.set_index(usize::MAX-1, 0), rather than quietly trying to resize a Vec to use all of memory.

1 Like
6

It seems the HashMap<usize, T> is more idiomatic for your use case.

2 Likes
7

Gotcha... okay that's a good enough reason to not have it in a crate but maybe just keep it as a local trait for my use-case

Yeah, I agree as a general point, but if I eventually want a Vec and I know it'll be fully packed but out of order (and I don't want to bother trying to figure out the eventual length), the solution here is a bit more efficient, no?

9

Always make it work, make it correct, and then make it fast. If you want to optimize the hashmap later you can replace it with the VecMap.

1 Like
10

Without knowing more about your problem, I don't think there's any way to know without benchmarking. This Default filling behavior may end up doing much the same work as a HashMap would do, especially if the HashMap ends up with no collisions after it's been fully populated. For now I'd go with whichever data structure makes your code simpler, and then benchmark both if it turns out to be a problem.

It's also worth noting that you can do the filling with a HashMap and then convert to a Vec, or vice versa, and there's tons of other exotic data structures out there, so if performance matters you'll have plenty of options to study.

2 Likes
11

Okay, took y'alls advice to heart and refactoring with HashMap. Though actually needed BTreeMap so it preserves insertion order when getting the final Vec.

Proof of concept Playground here

12

Careful, BTreeMap doesn't preserve insertion order, it stores items in increasing order of keys (i.e. whatever is dictated by the key's Ord impl). If you want to preserve insertion order, try linked-hash-map.

13

Whups, slip-up, meant comparative order of the keys - not insertion order! thanks for the correction

14

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.