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

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.

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.

• rust
• vector

Share Improve this question Follow edited Jan 7 at 6:05 cafce25 28.2k55 gold badges4545 silver badges5959 bronze badges asked Jan 7 at 0:35 Ahmet YazıcıAhmet Yazıcı 75677 silver badges2020 bronze badges 0

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 4

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.