How can I create a list of owned trait objects without allocating each item on the heap separately?

Question

I want an owned list of Rust trait objects. I could implement it as Vec<Box<dyn Trait>> but that allocates space on the heap for every trait object. What I’d prefer is a CompactList<dyn Trait> type with a memory representation that looks like:

[vtable1, size1, data1, vtable2, size2, data2, vtable3, size3, data3]

size* is the size in bytes of the corresponding data*.

With this, I could create an Iterator<Item = &dyn Trait>. The only operations I need on CompactList<T> are push() and iter().

Answer 1

The dynstack crate does what you want. It relies on the representation of fat pointers, which is what trait objects are, and that representation could theoretically change some day.

While it solves the problem of avoiding heap allocations for each object, its in-memory representation is different: Instead of a flat list, there are basically two lists:

• [data1, data2, ...]
• [(vtable1, size1), (vtable2, size2), ...]

Since the data structs can have different sizes, your representation doesn't support O(1) random access, while this one does. See this blog post for details.

Example, adapted from the documentation:

use dynstack::{dyn_push, DynStack};
use std::fmt::Debug;

let mut stack = DynStack::<dyn Debug>::new();
dyn_push!(stack, "hello, world!");
dyn_push!(stack, 0usize);
dyn_push!(stack, [1, 2, 3, 4, 5, 6]);

for item in stack.iter() {
    println!("{:?}", item);
}