CODEWITHSUNDEEP
rust
aas
aas

Reputation: 187

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

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?

Upvotes: 1

Views: 680

Answers (1)

Chayim Friedman
Chayim Friedman

Reputation: 71430

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).

Upvotes: 1

Related Questions