How to create a heterogenous collection without heap allocation

Hi, just for testing I would like to use a heterogeneous collection in Rust

trait T : std::fmt::Display {}

impl T for i32 {}
impl T for f32 {}

fn main(){
    let mut v = Vec::<Box<dyn T>>::new();
    v.push(Box::new(1));
    v.push(Box::new(3.25));
    
    for i in v.iter() {
        println!("{}", i);
    }
}

This works but there's a heap allocation and I want to prevent it. Traits are ?Sized by default. How can I go around this?

see frunk and enums

Your Vec inherently has a heap allocation if it has any capacity, but to avoid Box you could make it a Vec<&dyn T> if the actual items can be stored as their known types on the stack or as static data.

When avoiding heap allocations, the data needs to live on the stack. There’s two possible approaches I can think of here:

  • If the collection still needs to own its elements, it’s getting tricky; you’d need to have some kind of capacity limit N, then the data could probably be stored internally in something like a [MaybeUninit<u8>; N] as long as it fits. This is a bit complicated; perhaps there are crates out there implementing a safe abstraction for something like this.
  • Since the data needs to live on the stack, maybe you can live with it just being borrowed. In this case you dan store &dyn T or &mut dyn T references in a collection. If using a Vec, of course the Vec itself would still live on the heap (but there are of course stack-based alternatives, and also it’s already fewer allocations just avoiding the Box). Something like:
    trait T : std::fmt::Display {}
      
    impl T for i32 {}
    impl T for f32 {}
    impl T for String {}
    
    fn main(){
        let mut v = Vec::<&dyn T>::new();
        v.push(&1);
        v.push(&3.25);
        // and some non-literal for good measure
        let s = String::from("hello");
        v.push(&s);
        
        
        for i in v.iter() {
            println!("{}", i);
        }
    }
    
    (playground)
2 Likes

Another possibility, especially "just for testing", is to create an enum of the known possible types, then implement the required traits on that enum by forwarding to each variant.

2 Likes

Theere is also the option of using one of the small vec crates. They provide similar types like Vec but with a limited size and store there contents on the stack.