Implementing Index/overloading the [] operator for a sparse vector

Question

This is literally the same question as this C++ question, but in Rust.

Suppose I have a "sparse vector" type that stores filled entries in a map of some kind. Unfilled entries are some kind of default value, like 0.

use std::ops::{Index, IndexMut};
use std::collections::BTreeMap;
use num_traits::Float;

struct SparseVector<T: Float, const N: usize>(BTreeMap<usize, T>);

// Returning a ref is easy when a value is present.
impl<T: Float, const N: usize> IndexMut<usize> for SparseVector<T, N> {
    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
        self.0.entry(index).or_insert(T::zero())
    }
}

// What to return when we hit the default?
impl<T: Float, const N: usize> Index<usize> for SparseVector<T, N> {
    type Output = T;
    fn index(&self, index: usize) -> &T {
        match self.0.get(&index) {
            Some(value) => t,
            None => ???
        }
    }
}

To implement Index on this type, I need to return a &T. For filled entries, that's just a reference to the value. How do I return a ref to the default?

I obviously can't return a &0 for lifetime reasons.

I can't necessarily store the default in a const field of the struct impl. It might not come from a const function.

I'm trying to avoid storing the default value on every instance of the type. It's literally the same value, why must it be allocated on every instance, etc.

The C++ answer is to return an instance of a wrapper type that dereferences to a &T. But in Rust, a Deref<Target = &T> cannot be substituted for &T, as far as I know.

How can I implement Index (override the [] operator) on this type?

score 1 · Accepted Answer · answered Apr 11 '22 at 23:26

You cannot.

There were some discussions around extending the Index and Deref traits to support situations similar to that (https://github.com/rust-lang/rfcs/issues/997), but today you cannot.

This particular case is even more problematic because it requires GAT: the trait will have to be defined like:

pub trait IndexGat<I> {
    type Output<'a>: Deref
    where
        Self: 'a;

    fn index(&self, index: I) -> Self::Output<'_>;
}

impl<I, T: Index> IndexGat<I> for T {
    type Output<'a> = &'a <Self as Index>::Output
    where
        Self: 'a;

    fn index(&self, index: I) -> Self::Output<'_> { <Self as Index>::index(self, index) }
}

So you can implement it:

impl<T, const N: usize> IndexGat<usize> for SparseVector<T, N> {
    type Output<'a> = Wrapper<'a, T>;
    where
        Self: 'a;

    fn index(&self, index: usize) -> Self::Output<'_> { ... }
}

pub enum Wrapper<'a, T> {
    Default(T),
    Ref(&'a T),
}
impl<T> Deref for Wrapper<'_, T> {
    type Target = T;
    fn deref(&self) -> &Self::Target {
        match self {
            Self::Default(v) => v,
            Self::Ref(v) => *v,
        }
    }
}

So it cannot be done until GATs are stabilized.

The best thing you can do is just to use a regular method get() (or at(), or whatever).

Well, I can also "materialize" the default and store a copy of it on every instance. In this simple example, it's an ugly workaround, but at least it exists as an option. I had written the `Wrapper` type above in one attempt, before realizing that `Deref` is not `&T`. Is there a short explanation why something as limited as that requires something as heavyweight as GATs? — aas, Apr 11 '22 at 23:44
@aas I gave an example in the answer; basically, `Wrapper` needs to reference the lifetime of `&self`, so the associated type should have some way to reference that lifetime, i.e. to be generic over a lifetime, i.e. generic associated type. — Chayim Friedman, Apr 11 '22 at 23:48

Implementing Index/overloading the [] operator for a sparse vector

1 Answers1

Linked