O(1) cdr of Rc<Vec<...>>?

I have a

let x: Rc<Vec<...>>

is it possible in O(1) time to construct a y of type Rc<Vec<_>> that skips the first element, i.e.

y[i] = x[i+1]

If y ends up having a type that is not Rc<Vec<_>>, but supports indexing, that is fine too.

===

My intuition for why this should be possible is: because we have a Rc<Vec<_>>, no one can change the underlying Vec, therefore we should be able to just do some pointer magic & skip the first element.

First off, if you store it in an Rc, it can just as well be Rc<[T]>.

Then one clever solution could be to have your own type wrapping the array, and that has a Deref<Target=[T]> looks kind of like that:

fn deref(&self) -> [T] {
    self.array[1..]
}

I can’t remember the name just now, but there is also a crate that lets you basically make a type that contains the Vec and a slice referring to it. So you’d have Rc<MyType> which both owns the storage and a referring slice.

2 Likes

You could always make a wrapper type that does i + 1 indexing (or i + n where n is supplied at construction)

struct Wrapper<T> {
    vec: Rc<Vec<T>>,
    n: usize
}

impl<T> Index<usize> for Wrapper<T> {
    type Output = T;
    
    fn index(&self, index) -> &T {
        &self.vec[index + self.n]
    }
}

1 Like

Of course that only allows the indexing operation, and not any other [T] methods. So you’d have to reimplement all of them on the wrapper. But maybe this is enough already…

1 Like

Yes, wrapper + indexing suffices. Thanks everyone! Marking question as resolved.

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