A Vec with alternating element types?

help
1

Any ideas for a data structure like a Vec but with two types of elements that alternate? If I knew I would have an even number of elements and that a given element was always first, I could use a Vec of tuples. Does an alternating element data structure already exist? I don't know what it would be called, which hampers searching on crates.io. Of course, I could use a simple linked list, but that seems like a silly approach...

1 Like
2

Is wrapping your 2 types in an enum, and then storing instances of that enum in your Vec an option?

3

That would not enforce the alternating structure, which I'd like to ensure at the type level. It would also message either a bunch of runtime checks that aren't needed or a bunch of calls to unwrap.

4

A couple options I can think of:

  1. A pair of Vecs: struct Alt([Vec<T1>, Vec<T2>]) where the first Vec has either 0 or 1 more items than the second.
  2. If the second type of element has a cheap default value, then you could use tuples as you suggested (Vec<(T1, T2)>), along with a flag indicating whether or not the second tuple element in the last vec value is in the list.
      struct Alt {
    vec: Vec<(T1, T2)>,
    last_tuple_is_complete: bool,
  }
  3. If the second type does not have a cheap default value, then you could still use a vec of tuples and store the last unpaired value as a separate field:
      struct Alt {
    vec: Vec<(T1, T2)>,
    extra: Option<T1>,
  }

You will also want to think about how to provide getters for these. Options:

  1. fn get(index: usize): (T1, Option<T2>)
  2. fn getFirst(index: usize): T1 and
    fn getSecond(index: usize): T2

I these ideas aid further exploration.

5

syn::punctuated::Punctuated is basically this. I'm uncertain what a general provider of this kind of storage would be called.

1 Like