When to use Box<Vec<..>> or Vec<Box<..>>?

Question

When would it make sense to design a data structure that is nesting a Box and a Vec (or vice versa)?

It seems like in most situations where you want to store multiple fixed-size things on the heap, the Box is redundant, since it's only (?) role is to heap-allocate a ~single value, and a normal Vec is already heap allocating it's storage.

Context: I am still wrapping my head around the roles of the various Rust types for building up data structures.

Answer 1

There are really only a few times you need to use Box:

• Recursive data structures: not relevant for the outermost element, so no need for Vec<Box<T>>.

• Owned trait object, which must be Box<Trait> because the size of the object is dynamic;

• Things that are sensitive to particular memory addresses, in order that the contained object will keep the same memory location (practically never the case and definitely not the case in any stable public API; some of the handle stuff to do with std::sync::mpsc::Select is the only case that I am aware of; this unsafety and care required is a part of why select! exists. This sort of a thing (Handle.add) is unsafe stuff.

If none of these situations apply, you should not use Box. And Box<Vec<T>> is one such case; the boxing is completely superfluous, adding an additional level of indirection to no benefit whatsoever.

So the simple version is:

• Box<Vec<T>>: never.
• Vec<Box<T>>: only if T is a trait, i.e. you’re working with trait objects.