Use integers representing indices into a vector instead of references pattern

help
1

Hello, can you share some tutorials/articles/materials about a pattern of using integers representing indices into a vector instead of references?

2

I'm not sure if I can follow. Do you mean an access pattern where we store indices in a vector we then use to index another vector? Like this:

fn main() {
    let indices: Vec<usize> = vec![1, 3, 4];
    let values: Vec<u8> = vec![5, 4, 3, 2, 1, 0];
    
    assert_eq!(values[indices[0]], 4);
    assert_eq!(values[indices[1]], 2);
    assert_eq!(values[indices[2]], 1);
}

Playground.

Or am I misunderstanding your question?

3

this is a short introduction:

4 Likes
4

Generally yes, but I don't mean anything in particular, more about the general pattern. It's just that I hear quite often that it helps with the borrow checker and it can be convenient to work with, but I'm not too experienced and haven't seen anything like that in real life. For example, slab, slotmap, handy.

5

The main problem with these designs is that they become implementing an allocator in disguise in general. Otherwise it's just an optimization of a map from IDs to the values, which is good enough for most uses.

3 Likes
6

No but I had a nice discussion about doing exactly that for linked lists and graphs in this forum a while back: When is a linked list not a linked list?

That is is easy to do for simple cases, as in that discussion. But it seems to me that by doing that one has thrown away the benefits of Rust's references, lifetimes, the borrow checker. When your nodes are in an array and accessed by indices you can recreate all the fun of referring to uninitialised or dead nodes, using uninitialised indices (like using null pointers) and so on, but now the compiler cannot help you. You may also need to start implementing what is effectively memory management/garbage collection as you will have to grow the array if you need more space, you will have to keep track of which elements in the array are used or not.

7

Yes, I do agree with you, but this is still a useful tool and I wanted to learn more about it