Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Indexing vector by a 32-bit integer

Tags:

rust

In Rust, vectors are indexed using usize, so when writing

let my_vec: Vec<String> = vec!["Hello", "world"];
let index: u32 = 0;
println!("{}", my_vec[index]);

you get an error, as index is expected to be of type usize. I'm aware that this can be fixed by explicitly converting index to usize:

my_vec[index as usize]

but this is tedious to write. Ideally I'd simply overload the [] operator by implementing

impl<T> std::ops::Index<u32> for Vec<T> { ... }

but that's impossible as Rust prohibits this (as neither the trait nor struct are local). The only alternative that I can see is to create a wrapper class for Vec, but that would mean having to write lots of function wrappers as well. Is there any more elegant way to address this?

like image 853
Henning Koehler Avatar asked Nov 24 '16 09:11

Henning Koehler


2 Answers

Without a clear use case it is difficult to recommend the best approach.

There are basically two questions here:

  • do you really need indexing?
  • do you really need to use u32 for indices?

When using functional programming style, indexing is generally unnecessary as you operate on iterators instead. In this case, the fact that Vec only implements Index for usize really does not matter.

If your algorithm really needs indexing, then why not use usize? There are many ways to convert from u32 to usize, converting at the last moment possible is one possibility, but there are other sites where you could do the conversion, and if you find a chokepoint (or create it) you can get away with only a handful of conversions.

At least, that's the YAGNI point of view.


Personally, as a type freak, I tend to wrap things around a lot. I just like to add semantic information, because let's face it Vec<i32> just doesn't mean anything.

Rust offers a simple way to create wrapper structures: struct MyType(WrappedType);. That's it.

Once you have your own type, adding indexing is easy. There are several ways to add other operations:

  • if only a few operations make sense, then adding explicitly is best.
  • if many operations are necessary, and you do not mind exposing the fact that underneath is a Vec<X>, then you can expose it:
    • by making it public: struct MyType(pub WrappedType);, users can then call .0 to access it.
    • by implementing AsRef and AsMut, or creating a getter.
    • by implementing Deref and DerefMut (which is implicit, make sure you really want to).

Of course, breaking encapsulation can be annoying later, as it also prevents the maintenance of invariants, so I would consider it a last ditch solution.

like image 84
Matthieu M. Avatar answered Oct 08 '22 03:10

Matthieu M.


I prefer to store "references" to nodes as u32 rather than usize. So when traversing the graph I keep retrieving adjacent vertex "references", which I then use to look up the actual vertex object in the Vec object

So actually you don't want u32, because you will never do calculations on it, and u32 easily allows you to do math. You want an index-type that can just do indexing but whose values are immutable otherwise.

I suggest you implement something along the line of rustc_data_structures::indexed_vec::IndexVec.

This custom IndexVec type is not only generic over the element type, but also over the index type, and thus allows you to use a NodeId newtype wrapper around u32. You'll never accidentally use a non-id u32 to index, and you can use them just as easily as a u32. You don't even have to create any of these indices by calculating them from the vector length, instead the push method returns the index of the location where the element has just been inserted.

like image 20
oli_obk Avatar answered Oct 08 '22 03:10

oli_obk