collect() Reuses Your Allocation: Rust's In-Place Collection

TL;DR: vec.into_iter().map(f).collect::<Vec<_>>() can run entirely inside the original allocation. Rust implements this with a specialisation trait (InPlaceCollect) that checks the size and alignment relationship between the source and destination element types, then reads and writes through two cursors into the same buffer.

The idea

Collecting an iterator normally means: allocate a new buffer, write every element into it, free the old one. But if the iterator is already walking a Vec, and the element types are compatible, you can just write the transformed elements back over the source.

The catch is that the source and destination element types may have different sizes. If the destination is bigger, writing in place would overwrite elements that have not been read yet. The solution is to shrink the allocation first, or to bail out to the normal path.

The layout contract

The source documents the rules precisely:

rust
// library/alloc/src/vec/in_place_collect.rs:40-61

// Ultimately each step of the iterator must free up enough *bytes* in the source to make room
// for the next output item.
// If `T` and `U` have the same size no fixup is needed.
// If `T`'s size is a multiple of `U` we can compensate by multiplying the capacity accordingly.
// Otherwise the input capacity (and thus layout) in bytes may not be representable by the output
// `Vec<U>`. In that case `alloc.shrink()` is used to update the allocation's layout.
//
// Alignments of `T` must be the same or larger than `U`. ...

So:

same size → trivial;
source size is a multiple of destination size → the destination capacity is scaled up, and the byte budget works out;
otherwise → the allocation is shrunk to fit the new layout, which is allowed for Vec but is a real cost.

The implementation

rust
// library/alloc/src/vec/in_place_collect.rs:249-337

fn from_iter_in_place<I, T>(mut iterator: I) -> Vec<T>
where
    I: Iterator<Item = T> + InPlaceCollect,
    <I as SourceIter>::Source: AsVecIntoIter,
{
    unsafe {
        let inner = iterator.as_inner().as_into_iter();
        (
            inner.buf,
            inner.ptr,
            inner.cap,
            inner.buf.cast::<T>(),
            inner.end as *const T,
            // SAFETY: the multiplication can not overflow, since `inner.cap * size_of::<I::SRC>()` is the size of the allocation.
            inner.cap.unchecked_mul(size_of::<I::Src>()) / size_of::<T>(),
        )
    };

    let len = unsafe {
        SpecInPlaceCollect::collect_in_place(&mut iterator, dst_buf.as_ptr() as *mut T, dst_end)
    };
    ...
    if needs_realloc::<I::Src, T>(src_cap, dst_cap) {
        ...
        let result = alloc.shrink(dst_buf.cast(), old_layout, new_layout);
        let Ok(reallocated) = result else { handle_alloc_error(new_layout) };
        dst_buf = reallocated.cast::<T>();
    }
    ...
    unsafe { Vec::from_parts(dst_buf, len, dst_cap) }
}

The key line is inner.cap * size_of::<I::Src>() / size_of::<T>(): the destination capacity is computed in bytes and then converted, which is what makes the “source is a multiple of destination” case work.

And the result is documented in the source, which is unusual and lovely:

rust

// library/alloc/src/vec/in_place_collect.rs:118-126

Does not allocate, free or panic. On optlevel>=2 it does not loop.

So on optimized builds, vec.into_iter().map(|u| u as isize).collect::<Vec<isize>>() compiles to a counted loop that LLVM can even eliminate.

The specialisation hierarchy

The InPlaceCollect trait is implemented for the iterators that can support it:

rust

// library/alloc/src/vec/in_place_collect.rs:389-413

with the TrustedRandomAccessNoCoerce specialisation being the one that allows the “does not loop” claim.

Even when in-place collection does not apply, collect can avoid the allocation:

rust
// library/alloc/src/vec/spec_from_iter.rs:37-64

impl<T> SpecFromIter<T, IntoIter<T>> for Vec<T> {
    fn from_iter(iterator: IntoIter<T>) -> Self {
        // A common case is passing a vector into a function which immediately
        // re-collects into a vector. We can short circuit this if the IntoIter
        // has not been advanced at all.
        // When it has been advanced We can also reuse the memory and move the data to the front.
        // But we only do so when the resulting Vec wouldn't have more unused capacity
        // than creating it through the generic FromIterator implementation would. ...
        let has_advanced = iterator.buf != iterator.ptr;
        if !has_advanced || iterator.len() >= iterator.cap / 2 {
            let it = ManuallyDrop::new(iterator);
            unsafe {
                if has_advanced {
                    ptr::copy(it.ptr.as_ptr(), it.buf.as_ptr(), it.len());
                }
                return Vec::from_parts(it.buf, it.len(), it.cap);
            }
        }
        let mut vec = Vec::new();
        vec.spec_extend(iterator);
        vec
    }
}

let v2: Vec<_> = v1.into_iter().collect(); is zero allocations and zero copies when the iterator has not been advanced — and at most one memmove otherwise. The iterator.len() >= iterator.cap / 2 guard prevents keeping a mostly-empty allocation alive.

The `SpecExtend` chain

rust
// library/alloc/src/vec/spec_extend.rs:13-59

impl<T, I, A: Allocator> SpecExtend<T, I> for Vec<T, A>
where
    I: Iterator<Item = T>,
{
    default fn spec_extend(&mut self, iter: I) {
        self.extend_desugared(iter)
    }
}

impl<T, I, A: Allocator> SpecExtend<T, I> for Vec<T, A>
where
    I: TrustedLen<Item = T>,
{
    default fn spec_extend(&mut self, iterator: I) {
        self.extend_trusted(iterator)
    }
}

impl<T, A1: Allocator, A2: Allocator> SpecExtend<T, IntoIter<T, A2>> for Vec<T, A1> {
    fn spec_extend(&mut self, iterator: IntoIter<T, A2>) {
        unsafe {
            self.append_elements(iterator.as_slice() as _);
        }
        iterator.forget_remaining_elements_and_dealloc();
    }
}

Three tiers:

TrustedLen → reserve exactly once, then write without per-element capacity checks;
IntoIter → a single memcpy plus “forget the rest of the source”;
slice::Iter with a trivially-clonable T → also a single memcpy.

The TrustedLen path is the interesting one:

rust
// library/alloc/src/vec/mod.rs:4231-4264

fn extend_trusted(&mut self, iterator: impl iter::TrustedLen<Item = T>) {
    let (low, high) = iterator.size_hint();
    if let Some(additional) = high {
        debug_assert_eq!(low, additional, "TrustedLen iterator's size hint is not exact: {:?}", (low, high));
        self.reserve(additional);
        let ptr = self.as_mut_ptr();
        let mut local_len = SetLenOnDrop::new(&mut self.len);
        unsafe {
            iterator.for_each(move |element| {
                ptr::write(ptr.add(local_len.current_len()), element);
                // Since the loop executes user code which can panic we have to update
                // the length every step to correctly drop what we've written.
                local_len.increment_len(1);
            });
        }
    } else {
        panic!("capacity overflow");
    }
}

One reserve, then a tight loop with no capacity check. SetLenOnDrop keeps self.len accurate even if the iterator body panics, so partially written elements are dropped correctly.

Where it lives

library/alloc/src/vec/in_place_collect.rs — the in-place machinery.
library/alloc/src/vec/spec_from_iter.rs — allocation stealing.
library/alloc/src/vec/spec_extend.rs — the specialisation chain.
library/alloc/src/vec/mod.rs — extend_trusted, extend_desugared.

Takeaway

collect() is usually thought of as “allocate and fill”. But the common patterns are: extend a Vec with another Vec, or map over a Vec. Both can be done without touching the allocator at all, and Rust implements them with the same trick — specialise on the iterator type, then check the layout relationship between source and destination. The result is a collect() that, in the common case, is a loop.