Vec of Generics of Different Concrete Types

Question

I have a trait Foo, and concrete types A and B are both bounded by the trait Foo. I want to return a Vec<Foo>, where Foo could be either concrete type A or B, like shown below:

trait Foo { }

pub struct A {}
pub struct B {}

impl Foo for A {}
impl Foo for B {}


fn test() -> Vec<Foo> {
    let generic_vec: Vec<Foo> = Vec::new();
    generic_vec.push(A {});
    generic_vec.push(B {});
    return generic_vec;
}

The compiler at the moment is throwing the error that the sized trait is not implemented for Foo. I could wrap Foo in a Box, but I don't want to return a Vec of trait objects because of the runtime overhead that they impose.

I was wondering if there was some Rust Generics feature that would allow me to return a Vec of generic types without having to use trait objects.

The best way accomplish this is to either implement your types within an `enum`, or to create a newtype enum like `enum D { E(A), F(B) }` — PitaJ, Nov 08 '18 at 21:52
"…because of the runtime overhead that they impose." – Whatever technique you use, you will always have to dynamically dispatch to the methods of your trait, since what method to call on a particular element can only be decided at runtime. — Sven Marnach, Nov 08 '18 at 22:00

Sven Marnach · Answer 1 · 2018-11-08T21:55:54.640

A vector is a densely packed array in memory, and it requires that all its element occupy the same amount of space. The size of the elements needs to be known at compile time. Trait objects don't have a known size, so you can't store them in a Vec.

If you want to store a vector of elements that are either A or B, your best option is to use an enum:

pub struct A;
pub struct B;

enum Either {
    A(A),
    B(B),
}

fn main() {
    let mut v = vec![];
    v.push(Either::A(A));
    v.push(Either::B(B));
}

The enum Either has a size equal to the maximum of the sizes of A and B, possibly plus space for a discriminant that indicates what the current variant is. This size is known at compile time, so Either can be used in a vector.

If A and B implement a common trait, and you want to be able to call methods of this trait on the elements of the vector, you can implement the trait on Either as well, by forwarding all method calls to the correct variant.

score 5 · Answer 2 · answered Nov 08 '18 at 21:53

The issue here is that there is no guarantee that just because both A and B implement Foo they will have the same size. Since Rust's Vec is homogeneous we need to statically guarantee that all elements in it are sized.

The solution, then, is to Box the types binding them to the trait.

trait Foo { }

pub struct A {}
pub struct B {}

impl Foo for A {}
impl Foo for B {}

type FooT = Box<dyn Foo>;

fn test() -> Vec<FooT> {
    let mut generic_vec: Vec<FooT> = Vec::new();
    generic_vec.push(Box::new(A {}));
    generic_vec.push(Box::new(B {}));
    return generic_vec;
}

Now the types may not have the same size, but the pointer (Box) will, so we avoid the issue altogether, although at some cost since we must dereference to access the elements.

Note that here I defined the type alias FooT just for readability, but you could've, of course, just used Box<dyn Foo> instead.

Vec of Generics of Different Concrete Types

2 Answers2