Vec a fondo: longitud, capacidad y crecimiento amortizado

Vec<T> es la colección de Rust: un arreglo dinámico, contiguo y con propiedad, sobre el que se apoya casi todo lo demás. Por fuera parece una lista que crece sola; por dentro es un manejador de tres palabras en la pila —puntero, longitud y capacidad— que gobierna un buffer en el heap. Comprender la diferencia entre cuántos elementos hay y cuánto sitio hay reservado es la llave que abre su rendimiento: explica por qué push es barato casi siempre, por qué a veces la dirección de tus datos cambia de golpe, y por qué with_capacity puede ser la línea que más acelera tu programa.

Longitud frente a capacidad

Un Vec guarda dos números que la gente novata confunde y que nunca son lo mismo. La longitud (len) es cuántos elementos hay inicializados y válidos. La capacidad (capacity) es cuántos caben en el buffer reservado antes de tener que pedir más memoria. Siempre se cumple len <= cap, y el hueco entre ambos es memoria reservada pero aún sin construir.

fn main() {
    let mut v: Vec<i32> = Vec::new();   // len 0, cap 0: no reserva nada
    v.push(10);                          // len 1, cap 4 (primera reserva)
    v.push(20);                          // len 2, cap 4
    println!("len {} cap {}", v.len(), v.capacity()); // len 2 cap 4
}

Un Vec::new() vacío no toca el heap: nace con capacidad cero y un puntero dangling alineado, sin pedir memoria al asignador. La primera insercion es la que reserva. Mientras len < cap, cada push solo escribe en un hueco ya reservado e incrementa len: es una operacion de coste constante y sin sorpresas. La tensión aparece justo cuando len == cap y pides meter uno más: ahí no queda sitio, y el Vec debe reasignar.

Cómo crece: reasignación amortizada

Cuando len == cap y llega otro push, el Vec pide al asignador un buffer más grande, copia byte a byte todos los elementos al nuevo sitio, libera el viejo y actualiza su puntero. La pregunta de diseño es: ¿cuánto más grande? La respuesta de Rust —y de casi todas las bibliotecas serias— es duplicar: el nuevo buffer tiene el doble de capacidad que el anterior.

Esa elección no es arbitraria, es la que garantiza que push sea amortizado O(1). El razonamiento es el corazón teórico de esta lección. Para insertar n elementos partiendo de capacidad pequeña y duplicando, las reasignaciones ocurren en capacidades 1, 2, 4, 8, …, hasta n, y cada una copia esa cantidad de elementos. El total de copias es la suma de esa serie geométrica:

1 + 2 + 4 + 8 + ... + n  =  2n - 1  <  2n

Es decir, insertar n elementos cuesta en total menos de 2n movimientos: coste lineal repartido entre n inserciones, o sea O(1) por inserción de media. Algunos push sueltos son caros —los que caen justo en la reasignación—, pero el promedio sobre toda la vida del Vec es constante. Si en cambio creciera de forma aditiva (sumar un hueco fijo cada vez), reasignaría cada pocos elementos y el total de copias sería del orden de n²/2: O(n) por inserción, cuadrático en conjunto. Duplicar convierte lo cuadrático en lineal.

flowchart LR
p1[push con len igual a cap] --> r[Reserva buffer del doble]
r --> c[Copia todos los elementos al nuevo sitio]
c --> f[Libera el buffer viejo]
f --> u[Actualiza puntero y capacidad]
style r fill:#fab387,color:#11111b
style c fill:#f38ba8,color:#11111b
style u fill:#a6e3a1,color:#11111b

El detalle exacto —que la primera reserva salte a 4 y no a 1, por ejemplo— es un detalle de implementación de la biblioteca estándar, no una promesa del lenguaje. Lo único que std garantiza es que push sea amortizado O(1). No escribas código que dependa de valores concretos de capacity; sí puedes confiar en el comportamiento asintótico.

Reservar de antemano: with_capacity

Si sabes cuántos elementos vas a meter, díselo al Vec de entrada con with_capacity. Reserva el buffer una sola vez, len arranca en 0 y cap en lo que pediste, y todos los push siguientes caen en hueco ya reservado: cero reasignaciones, cero copias intermedias.

fn main() {
    let mut v = Vec::with_capacity(1_000);  // una reserva, len 0 cap 1000
    for i in 0..1_000 {
        v.push(i);                           // ningun push reasigna
    }
    assert_eq!(v.len(), 1_000);
    assert!(v.capacity() >= 1_000);

    v.reserve(500);        // asegura sitio para 500 mas (puede sobre-reservar)
    v.shrink_to_fit();     // devuelve la capacidad sobrante al asignador
}

reserve(n) garantiza sitio para n elementos adicionales sobre la longitud actual, y por dentro puede sobre-reservar siguiendo la política de duplicado; reserve_exact(n) pide justo lo pedido, útil cuando sabes que no crecerás más. shrink_to_fit hace lo contrario: encoge la capacidad hasta la longitud, cediendo la memoria sobrante. La ganancia de with_capacity no es teórica: en un bucle que construye un vector grande, evitar la decena de reasignaciones y las copias que arrastran suele traducirse en una mejora medible, y a veces sustancial, sin cambiar ni una línea de lógica.

El layout en memoria

Aquí está el modelo mental que lo unifica todo. Un Vec<T> es exactamente tres palabras en la pila: un puntero al buffer, la longitud y la capacidad. Esas tres palabras son todo lo que se mueve cuando pasas un Vec por valor. Los elementos viven aparte, en un bloque contiguo del heap del tamaño cap * size_of::<T>().

flowchart LR
subgraph Pila
  ptr[ptr]
  len[len igual a 3]
  cap[cap igual a 4]
end
ptr --> h0
subgraph Heap buffer contiguo de 4 huecos
  h0[10] --- h1[20] --- h2[30] --- h3[hueco sin usar]
end
style ptr fill:#89b4fa,color:#11111b
style len fill:#a6e3a1,color:#11111b
style cap fill:#fab387,color:#11111b
style h3 fill:#45475a,color:#cdd6f4

Esa contigüidad es la razón de que Vec sea la colección por defecto y la más rápida de recorrer: los elementos están pegados, el índice v[i] es una simple aritmética de puntero ptr + i, y el procesador puede prever los accesos —volveremos a ello en la lección 19.5—. El manejador en la pila es de tamaño fijo aunque el buffer sea gigante, lo que hace baratísimo moverlo. Un caso límite elegante: si T es un tipo de tamaño cero (como ()), no hay nada que almacenar, así que el Vec no reserva heap jamás y su capacidad es, conceptualmente, infinita; solo lleva la cuenta de len.