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?

Chayim Friedman · Accepted Answer · 2022-04-11 23:26:14Z

1

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

answered Apr 11, 2022 at 23:26

Chayim Friedman

76.3k5 gold badges97 silver badges140 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

aas Over a year ago

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<Target = T> is not &T. Is there a short explanation why something as limited as that requires something as heavyweight as GATs?

Chayim Friedman Over a year ago

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

Collectives™ on Stack Overflow

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

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related