Vector of tuples with different size

Question

I am currenly implementing marching cubes algorithm using Rust and I faced a problem. This algorithm requires using triangulation table which I copied from GitHub. But which data structure in Rust allow us to store such a data?

Those tuples mean which edges of cubes have to be connected, so they all are different size.

pub fn tri_table()-> Vec<???>
{
   return vec![
      (),
      (0, 8, 3),
      (0, 1, 9),
      (1, 8, 3, 9, 8, 1),
      (1, 2, 10),
      (0, 8, 3, 1, 2, 10),
      (9, 2, 10, 0, 2, 9),
      (2, 8, 3, 2, 10, 8, 10, 9, 8),
      (3, 11, 2),
      (0, 11, 2, 8, 11, 0),
      (1, 9, 0, 2, 3, 11),
      (1, 11, 2, 1, 9, 11, 9, 8, 11),
      (3, 10, 1, 11, 10, 3),
      (0, 10, 1, 0, 8, 10, 8, 11, 10),
      (3, 9, 0, 3, 11, 9, 11, 10, 9),
      (9, 8, 10, 10, 8, 11),
      (4, 7, 8),
      ...
   ];
}

Answer 1

It sounds like your triangulation table is known at compile time. In that case, use static slices. That's the solution with the lowest cost, it has almost zero overhead. For the price that you can't modify it anymore afterwards.

Like this:

pub fn tri_table() -> &'static [&'static [i32]] {
    &[
        &[],
        &[0, 8, 3],
        &[0, 1, 9],
        &[1, 8, 3, 9, 8, 1],
        &[1, 2, 10],
        &[0, 8, 3, 1, 2, 10],
        &[9, 2, 10, 0, 2, 9],
        &[2, 8, 3, 2, 10, 8, 10, 9, 8],
        &[3, 11, 2],
        // ...
    ]
}

By doing this the data will be baked directly into the data segment of your executable, and calling tri_table() only returns a pointer to it, no allocation will happen and no heap memory will be used. Calling tri_table() multiple times will always return a reference to the same address, so also no overhead if you call it multiple times.

Answer 2

Finomnis has already suggested an efficient solution to your problem. But for those who find this question from a search for a way to put different tuples in a vector, the number and type of tuples in that vector might not be known at compile time. That's usually the case with vectors.

So if you really need a vector, the two main approaches in Rust is to use a vector of trait objects or a vector of enums with values. Both approaches have their pros and cons. Enums will probably use more memory (depends on the size of the enum variant with the largest value), but a trait object requires an extra (fat) pointer (as explained here).