rustvector

Mapping Vec<T> to Vec<K> without new heap allocation where size(T) >= size(K)


I have two structs T and K, and the size of T is greater than or equal to K. Assume following:

struct T {
    k: K,
    t_val: u32,
}

struct K {
    k_val: u64,
}

I want to map Vec to Vec without any new heap allocation. This should optimally be possible since mapped Vec will definitely require less memory than Vec as T is 12-bytes and K is 8-bytes, and the types are just there to calculate the offset. Here is how I imagine it would look:

*ptr -> [12(T) | 12(T) | 12(T)]
        |
      iter_k
      iter_t

*ptr -> [8(K) | 4(garbage) | 12(T) | 12(T)]
              |            |
            iter_k       iter_t

*ptr -> [8(K) | 8(K) | 8(garbage) | 12(T)]
                     |            |
                   iter_k       iter_t

*ptr -> [8(K) | 8(K) | 8(K) | 12(garbage)]
                            |            |
                          iter_k       iter_t

And the last 12-bytes garbage is irrelevant since size is 3 and can remain as extra capacity for the new Vec.


Solution

  • The code to do that is surprisingly simple:

    pub fn map(v: Vec<T>) -> Vec<K> {
        v.into_iter().map(|v| K { k_val: v.k.k_val }).collect()
    }
    

    Yes, that's it. If you look on godbolt, you will see this doesn't allocate.

    Of course, there is *magic* involved. The Rust standard library provides specialization for Vec-to-Vec iterators that do not allocate whenever possible. Of course, this is not guaranteed.

    You can guarantee that by using unsafe code, but you really shouldn't have a reason to.

    Note that this is only possible when the alignment of K is the same as the alignment for T, and the size is a multiplication, because it needs to match for deallocation.