Vector which grows when accessing out of bounds index

Hi all, thanks for taking the time to read my post! I have a vector which optionally holds some data and I want to implement a function to access the data by index. However I want the vector to grow with Nones if the index greater than the current length of the vector. I've summarised my first attempt at the code as follows:

struct A<T>(Vec<Option<T>>);

impl<T> A<T>
where
    T: Default + Clone,
{
    pub fn get(&mut self, index: usize) -> &T {
        match self.0.get(index) {
            Some(Some(value)) => value,
            Some(None) => {
                // vector contains index but is unoccupied.
                self.0[index] = Some(T::default());
                self.0[index].as_ref().unwrap()
            }
            None => {
                // index is bigger than the length of vector
                self.0.append(&mut vec![None; index + 1 - self.0.len()]);
                self.0[index] = Some(T::default());
                self.0[index].as_ref().unwrap()
            }
        }
    }
}

The code (rightly) doesn't compile because Vec::get() requires an immutable reference and then in some of the match arms the same vector is mutated. I then tried changing to match self.0.get_mut(index) but now we end up creating two mutable references which is obviously bad.

Is there a good way to express this logic without using some if/else statements? (Also there's many ways to grow a vector and I wasn't sure of the most efficient in this case so any suggestions would be great!)

Is there a reason why you have Vec<Option<T>> rather than Vec<T> other than your idea of extending the vector upon indexing? Do you ever insert a None into your vector? Either way, I don't think a solution with if/else statements looks too bad honestly:

struct A<T>(Vec<Option<T>>);

impl<T> A<T>
where
    T: Default + Clone,
{
    pub fn get(&mut self, index: usize) -> &T {
        if self.0.len() <= index {
            self.0.append(&mut vec![None; index + 1 - self.0.len()]);
            self.0[index] = Some(T::default());
        } else if self.0[index].is_none() {
            self.0[index] = Some(T::default());
        }
        
        self.0[index].as_ref().unwrap()
    }
}
1 Like

The implementation can be as simple as: Playground

impl<T: Default> GrowVec<T> {
    fn get(&mut self, index: usize) -> &mut T {
        if self.buf.len() <= index {
            self.buf.resize_with(index + 1, T::default);
        }
        
        &mut self.buf[index]
    }
}
2 Likes

I'm essentially trying to make a HashMap<usize, T> but without the overhead of hashing However I can't rely on the user giving the data in a contiguous fashion, they could do an insert(1, T::default()) before doing insert(0, T::default()). Maybe the wrong way to approach this and happy to have alternative suggestions but I didn't want this to become an XY problem.

Thanks for the suggestion with if/elses - it doesn't look too bad at all!

Unfortunately the resize_with will fill all values with default rather than None - maybe the above explanation clarifies my use case a little better. I could combine the answers though and use resize(index + 1, None) instead of append.

What's the difference? Default for Option is None:
Option in std::option - Rust

1 Like

Sorry, not really. You are never using the Options in your own code for anything but redundant checks, because you will end up inserting a Some and then doing an unwrap() in any case. Your signature reinforces this, too – the return type is &T, not Option<&T>. The options are entirely unnecessary.

However, with my implementation, you can still insert None if you want to (Option unconditionally implements Default and the default value is None).

3 Likes

The suggestion was to use T::default rather than Option::default. In this case however I would expect just calling resize would be optimal since it avoids extra function calls.

This is a simplified example that I'm using, in other parts of the code I use the options. The reason for the option is that T::default is a valid entry in the list, without the option how would I be able to tell the slots in the vector which are occupied and slots which are unoccupied? I.E. something like:

let a: Vec<Option<u32>> = [Some(0), None, None, Some(3)];

has indices 1 and 2 unoccupied. If instead this was written as (I think) you're suggesting:

let a: Vec<u32> = [0, 0, 0, 3];

This could be interpreted in two ways;

  • All indices are occupied with respective values
  • Indices 0, 1, 2 are unoccupied and index 3 is occupied with value 3.

I have the former case (except the inner type is not u32) which is why I rely on the Options to distinguish between occupied and unoccupied.

Adapting @H2CO3's code to use Vec<Option<T>> and handling the None case with Option::get_or_insert_with:

fn get(&mut self, index: usize) -> &mut T {
    if self.0.len() <= index {
        self.0.resize_with(index + 1, || None);
    }
    self.0[index].get_or_insert_with(T::default)
}

Rust Playground

4 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.