A Vec with alternating element types?

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

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

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.

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.

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

1 Like