04 · Colecciones e iteración#

Objetivo#

Al terminar esta lección podrás seleccionar la estructura de datos óptima en memoria (Vec<T> o HashMap<K, V>) según la frecuencia de acceso, la conservación de orden y los patrones de búsqueda de tu dominio. Dominarás los tres modos fundamentales de iteración (iter(), iter_mut(), into_iter()), comprenderás la mecánica de evaluación perezosa (lazy evaluation) de las cadenas de iteradores, entenderás por qué son abstracciones de coste cero (zero-cost abstractions), y sabrás cuándo una búsqueda lineal contigua en un vector supera en rendimiento real a una tabla hash debido a la arquitectura de la memoria caché de la CPU.

Antes de empezar#

Esta lección asume que dominas ownership, referencias compartidas y exclusivas (02 · Ownership y préstamos), así como el manejo idiomático de Option y pruebas automatizadas (03 · Modelar errores y escribir pruebas). Utilizaremos exclusivamente colecciones de la biblioteca estándar de Rust (std::vec::Vec, std::collections::HashMap y slices &[T]), sin dependencias externas:

• Para compilar y ejecutar pruebas: rustc --test archivo.rs

Ten presente que las colecciones en memoria almacenan estado efímero que se destruye al terminar el proceso. Si requieres repasar conceptos base, consulta el glosario técnico.

Diccionario de conceptos de la lección (Glosario desde cero)#

Para consolidar una comprensión sólida de la gestión de múltiples elementos en Rust, analizamos cada término bajo cuatro dimensiones: intuición cotidiana, definición técnica formal, ejemplo concreto en código y concepción errónea frecuente.

1. Vector dinámico (Vec<T>)#

• Intuición cotidiana: Una libreta de renglones numerados en orden: puedes añadir una nueva línea al final rápidamente, leer cualquier renglón si conoces su número de línea exacto y el orden en que escribiste las líneas se conserva intacto.
• Definición técnica precisa: Arreglo dinámico redimensionable que almacena una secuencia contigua de elementos homogéneos de tipo T en el montículo (heap). En la pila (stack), un Vec<T> se representa mediante un descriptor de 3 palabras de máquina ($24$ bytes en 64 bits): un puntero al búfer (ptr), la capacidad total de almacenamiento reservada (cap) y el número actual de elementos válidos (len).
• Ejemplo en código:

  let mut numbers: Vec<i32> = Vec::new();
  numbers.push(10);
  numbers.push(20);

• Concepción errónea: Pensar que Vec<T> es una lista enlazada (linked list). Un Vec no dispersa nodos por la memoria con punteros individuales; garantiza que todos sus elementos residan físicamente uno inmediatamente al lado del otro en un único bloque contiguo de memoria RAM.

2. Tabla Hash (HashMap<K, V>) y Conjunto (HashSet<T>)#

• Intuición cotidiana: Un fichero de oficina con pestañas alfabéticas: si buscas la carpeta de "García", vas directamente a la pestaña "G" en un solo paso, sin tener que revisar una por una todas las carpetas de la "A" a la "F".
• Definición técnica precisa:
• HashMap<K, V>: Estructura de datos asociativa que almacena pares clave-valor. Utiliza una función hash para transformar la clave K en un índice entero que determina en qué cubeta (bucket) de memoria se ubica el valor V, permitiendo inserciones, búsquedas y eliminaciones en tiempo promedio O(1).
• HashSet<T>: Implementación envolvente sobre HashMap<T, ()> que almacena valores únicos sin claves asociadas, garantizando ausencia de duplicados.
• Ejemplo en código:

  use std::collections::HashMap;

  let mut scores = HashMap::new();
  scores.insert(String::from("Alice"), 50);

• Concepción errónea: Asumir que un HashMap conserva el orden en que insertaste los datos. Las claves se distribuyen según el algoritmo de dispersión (hashing), por lo que el orden de iteración es impredecible y no debe utilizarse para lógicas que dependan de secuencia temporal.

3. Función Hash, Buckets y traits Eq + Hash#

• Intuición cotidiana: Un empleado clasificador en correos que lee el código postal de una carta y la arroja instantáneamente a la cesta que corresponde a esa zona de la ciudad.
• Definición técnica precisa:
• Función Hash: Algoritmo determinista que toma un dato de longitud arbitraria (como una cadena o estructura) y calcula un entero fijo de 64 bits (hash code). En Rust estándar, se utiliza por defecto el algoritmo SipHash 1-3, diseñado específicamente para prevenir ataques de denegación de servicio por colisiones hash (HashDoS).
• Hash trait: Trait que define cómo alimentar el estado de un hasher con los bytes del tipo.
• Eq trait: Trait que certifica una relación de equivalencia reflexiva, simétrica y transitiva. Es indispensable para que la tabla hash confirme que dos claves con el mismo código hash son verdaderamente idénticas en caso de colisión.
• Ejemplo en código:

  #[derive(Hash, PartialEq, Eq)]
  struct UserId(u64);

• Concepción errónea: Creer que un tipo en punto flotante (f32, f64) puede usarse como clave en un HashMap. No implementan Eq ni Hash porque NaN (Not a Number) no es igual a sí mismo (NaN != NaN), violando la invariante fundamental de una tabla hash.

4. Indexación directa (vec[i]) vs Acceso seguro (.get(i) -> Option<&T>)#

• Intuición cotidiana:
• Indexación directa: Caminar con los ojos vendados y dar 10 pasos exactos confiando en que el piso continúa; si se acabó el suelo, caes al vacío.
• Acceso seguro: Tocar con un bastón guía antes de dar el paso: si el piso está ahí, avanzas seguro (Some); si hay un abismo, te detienes de inmediato sin peligro (None).
• Definición técnica precisa:
• vec[i] implementa el trait Index. Si el índice i ≥ len, la comprobación de límites (bounds check) de Rust falla e invoca inmediatamente un panic!, deteniendo el hilo de ejecución.
• .get(i) es un método seguro que compara i < len. Si es válido, retorna Some(&T). Si el índice está fuera de rango, retorna None pacíficamente sin abortar la ejecución.
• Ejemplo en código:

  let items = vec![100, 200];
  // let danger = items[5]; // ¡PANIC! runtime abort
  let safe = items.get(5); // Retorna None de forma segura

• Concepción errónea: Pensar que la indexación directa es "más rápida" y por eso debe usarse en todas partes. En código de producción que maneja datos de usuarios externos, la indexación directa sin validar la longitud introduce vulnerabilidades severas de denegación de servicio (DoS).

5. Trait Iterator y método .next()#

• Intuición cotidiana: Un dispensador giratorio de dulces: cada vez que giras la manivela una posición, cae exactamente un dulce en tu mano. Cuando se vacía el depósito, girar la manivela no entrega nada.
• Definición técnica precisa: Trait fundamental de la biblioteca estándar de Rust que modela secuencias de valores que pueden recorrerse paso a paso. Requiere implementar un único método obligatorio:

  fn next(&mut self) -> Option<Self::Item>;

Cada invocación sucesiva a .next() avanza el estado interno del iterador y produce Some(item). Cuando la secuencia se agota, retorna None.

• Ejemplo en código:

  let mut iter = vec![1, 2].into_iter();
  assert_eq!(iter.next(), Some(1));
  assert_eq!(iter.next(), Some(2));
  assert_eq!(iter.next(), None);

• Concepción errónea: Pensar que un iterador almacena una copia completa de todos los elementos. Un iterador es simplemente un pequeño puntero o cursor con estado que sabe cómo calcular o apuntar al siguiente elemento de la secuencia.

6. Tres modos de iteración (iter(), iter_mut(), into_iter())#

• Intuición cotidiana:
• iter(): Mirar las obras de arte en un museo a través de una vitrina (solo lectura prestada).
• iter_mut(): Un restaurador de arte autorizado que limpia o retoca cada cuadro en su caballete (modificación en sitio).
• into_iter(): Comprar todos los cuadros del museo, cargarlos en tu camión y llevártelos a tu casa privada (consumo total de propiedad).
• Definición técnica precisa:
• .iter(): Crea un iterador que produce referencias compartidas &T. No consume la colección ni transfiere ownership.
• .iter_mut(): Crea un iterador que produce referencias exclusivas mutables &mut T. Permite modificar los elementos dentro de la colección existente.
• .into_iter(): Implementa el trait IntoIterator. Consume la colección original por valor (move), entregando ownership de cada elemento T. Tras invocarlo, la colección original deja de existir en el stack.
• Ejemplo en código:

  let mut v = vec![1, 2, 3];
  for item in v.iter() { /* item es &i32 */ }
  for item in v.iter_mut() { *item += 1; /* item es &mut i32 */ }
  for item in v.into_iter() { /* item es i32; 'v' se destruye aquí */ }

• Concepción errónea: Creer que un bucle for x in v siempre presta. En Rust, for x in v invoca implícitamente v.into_iter(), consumiendo el vector v a menos que escribas explícitamente for x in &v (que invoca (&v).into_iter(), equivalente a v.iter()).

7. Evaluación perezosa (Lazy Evaluation) vs Consumidor terminal#

• Intuición cotidiana: Escribir una lista de tareas en un papel durante la mañana (planificar): la lista en sí no hace el trabajo. El trabajo físico solo ocurre por la tarde cuando decides ejecutar la lista tarea por tarea hasta el final.
• Definición técnica precisa:
• *Adaptadores de iterador (Iterator Adapters): Métodos como .map(), .filter(), .take(), .zip(). Son estrictamente perezosos (lazy)*: no procesan ningún elemento ni consumen ciclos de cálculo al ser invocados; solo configuran una máquina de estados que sabe qué hacer.
• *Consumidores terminales (Consumers):* Métodos como .collect(), .count(), .sum(), .any(), .position(), .for_each(). Son métodos activos que llaman a .next() repetidamente en un bucle cerrado hasta agotar el iterador o satisfacer una condición, materializando el resultado final.
• Ejemplo en código:

  let numbers = vec![1, 2, 3];
  // No se realiza ninguna multiplicación en este punto:
  let doubled = numbers.iter().map(|x| x * 2);
  // Aquí se ejecuta el cómputo y se reserva memoria para el nuevo vector:
  let result: Vec<i32> = doubled.collect();

• Concepción errónea: Pensar que encadenar cinco métodos adaptadores crea cinco arreglos intermedios temporales en memoria. Rust compone todos los adaptadores en una única pasada combinada en un solo bucle a nivel de máquina sin ningún arreglo intermedio.

8. Clausura (Closure |x| ...)#

• Intuición cotidiana: Una pequeña receta de cocina portátil o función anónima que anotas en una tarjeta adhesiva y pasas a un asistente para que la aplique cuando sea el momento oportuno.
• Definición técnica precisa: Función anónima delimitada por barras verticales |arg1, arg2| expr capaz de capturar variables de su entorno léxico contenedor. Según cómo interactúe con el entorno, el compilador infiere automáticamente si implementa Fn (captura por referencia compartida), FnMut (captura por referencia mutable), o FnOnce (captura por valor/movimiento).
• Ejemplo en código:

  let threshold = 10;
  let is_above = |val: &i32| *val > threshold; // Captura 'threshold' por referencia

• Concepción errónea: Confundir clausuras de Rust con clausuras de JavaScript o Python. En lenguajes interpretados, las clausuras requieren asignar un objeto de contexto en el heap. En Rust, las clausuras son estructuras puras en el stack cuyo tamaño depende exactamente de las variables capturadas, compilándose como llamadas directas en línea (inlined).

9. Desreferenciación (*)#

• Intuición cotidiana: Seguir la flecha de un cartel indicador hasta llegar al edificio físico real donde se encuentra la persona.
• Definición técnica precisa: Operador unario de prefijo (*ptr o *reference) que instruye al procesador a acceder al valor almacenado en la dirección de memoria apuntada por la referencia. Si el tipo subyacente implementa Copy, *ref copia el valor; si no, permite leer sus campos en sitio o mutarlo si la referencia es &mut.
• Ejemplo en código:

  let value: i32 = 42;
  let reference: &i32 = &value;
  let copied_value: i32 = *reference; // Lee los 4 bytes de memoria física apuntados

• Concepción errónea: Creer que puedes desreferenciar cualquier tipo para moverlo. Si T no implementa Copy (como String), escribir let s = *ref_s; es ilegal porque intentaría mover la propiedad de un valor que no te pertenece.

10. Complejidad algorítmica O(N × M) vs O(N + M)#

• Intuición cotidiana:
• O(N × M): Buscar si 100 personas de una lista están invitadas a una fiesta revisando manualmente de arriba a abajo una lista de papel de 1000 invitados para cada una de las 100 personas (100 × 1000 = 100{,}000 lecturas).
• O(N + M): Cargar la lista de 1000 invitados en una aplicación en tu teléfono en un paso ($1000$ lecturas) y luego consultar directamente a cada una de las 100 personas en la app ($100$ consultas directas: 1000 + 100 = 1{,}100 operaciones).
• Definición técnica precisa: Medida asintótica del crecimiento del tiempo de ejecución en función del tamaño de dos colecciones N y M:
• Algoritmo cuadrático anidado: Escanear linealmente una colección M para cada elemento de N requiere N × M operaciones elementales de comparación.
• Algoritmo lineal optimizado: Precomputar un conjunto hash HashSet con los elementos de M (costo O(M) de inserción) y realizar consultas O(1) para cada elemento de N reduce el costo total a O(N + M).
• Ejemplo en código:

  // Enfoque O(N * M):
  // labels.iter().filter(|l| blocked.iter().any(|b| b == *l))

  // Enfoque O(N + M):
  // let blocked_set: HashSet<_> = blocked.iter().collect();
  // labels.iter().filter(|l| !blocked_set.contains(*l))

• Concepción errónea: Pensar que O(N + M) siempre es más rápido que O(N × M) para cualquier valor de N y M. Para tamaños diminutos (como N = 3 y M = 2), el costo de calcular funciones hash y reservar memoria en el heap para una tabla hash es mucho mayor que 6 comparaciones secuenciales directas en la memoria caché del procesador.

Modelo mental y desempacado paso a paso#

1. ¿Por qué .filter() pasa una referencia doble &&T al iterar con .iter()?#

Uno de los tropiezos más desconcertantes para los ingenieros que aprenden Rust ocurre al intentar filtrar elementos de una colección prestada:

let items = vec![String::from("rust"), String::from("code")];
let found = items.iter().filter(|item| item.len() > 3);

Si inspeccionas el tipo exacto de item dentro de la clausura, descubrirás que no es String, ni tampoco &String, sino:

Desempacado formal del porqué:#

1. Analicemos la firma del método .iter(): ``rust fn iter(&self) -> Iter<'_, T> ` El tipo asociado Item producido por este iterador es una referencia compartida al elemento: type Item = &T. En nuestro caso, Self::Item es &String`.
2. Analicemos la firma del adaptador .filter() en el trait Iterator: ``rust fn filter<P>(self, predicate: P) -> Filter<Self, P> where P: FnMut(&Self::Item) -> bool, ` Observa atentamente el parámetro del predicado: &Self::Item`.
3. Al sustituir Self::Item (que ya es &String), la firma resultante es:
   &(&String) ⟹ &&String

¿Por qué el diseñador de la biblioteca estándar hizo que .filter() tome &Self::Item en vez de Self::Item por valor?#

El propósito de un filtro es únicamente inspeccionar el elemento para decidir si lo deja pasar o lo descarta. Un filtro no debe consumir ownership ni destruir los datos. Si .filter() recibiera el elemento por valor, tendría que adueñarse de cada elemento; si el elemento resulta rechazado por el filtro, ¿quién devolvería la propiedad al llamador? Sería imposible. Por ello, .filter() pide prestado el item que el iterador está produciendo. Como el iterador ya producía una referencia (&T), pedir prestada esa referencia genera una referencia a una referencia (&&T).

Cómo manejar la referencia doble de forma idiomática:#

1. Patrón de desestructuración en los argumentos de la clausura: ``rust items.iter().filter(|&item| item.starts_with("r")) // 'item' pasa a ser &String ``
2. Desreferenciación explícita con el operador *: ``rust items.iter().filter(|item| (*item).starts_with("r")) ``
3. Coerción automática al invocar métodos: Dado que Rust aplica desreferenciación automática al invocar métodos (item.starts_with(...)), muchas veces el compilador resuelve la doble referencia de forma transparente sin que tengas que intervenir.

2. Abstracciones de coste cero (Zero-Cost Abstractions) en iteradores#

Bjarne Stroustrup definió el principio de las abstracciones de coste cero: "Lo que no usas, no lo pagas. Lo que usas, no podrías haberlo escrito a mano mejor". Rust adopta este principio al 100% en su arquitectura de iteradores:

Cuando escribes:

let sum: u32 = numbers
    .iter()
    .filter(|&&x| x > 10)
    .map(|&&x| x * 2)
    .sum();

Un programador proveniente de lenguajes interpretados podría temer que esto asigne múltiples objetos iteradores intermedios, realice llamadas a funciones virtuales dinámicas por cada número y degrade la memoria.

En Rust ocurre exactamente lo contrario:

1. *Monomorfización (Monomorphization):* El compilador genera código binario especializado para la cadena de tipos exacta de la clausura e iterador.
2. Inlining total: El backend del compilador (LLVM) expande el cuerpo de .map() y .filter() directamente dentro del bucle de consumo.
3. *Eliminación de comprobaciones de límites (Bounds Checks Elimination):* Si escribes un bucle indexado tradicional for i in 0..len { sum += numbers[i]; }, el compilador debe emitir instrucciones condicionales en ensamblador para verificar que i < numbers.len() en cada iteración (a menos que el optimizador pueda demostrarlo). Pero un iterador en Rust se implementa internamente como dos punteros de máquina: un puntero de inicio ptr y un puntero final end. El bucle avanza simplemente incrementando el puntero hasta que ptr == end. No hay ninguna comprobación de límites por índice, alcanzando velocidad pura de ensamblador nativo.
4. Vectorización SIMD: LLVM puede desenrollar el bucle resultante y utilizar instrucciones vectoriales del procesador (AVX2, AVX-512 o ARM Neon), procesando 4, 8 o 16 números simultáneamente en un único ciclo de reloj.

3. La física del hardware: Localidad de caché vs Complejidad asintótica#

En la teoría académica de estructuras de datos:

• Buscar en un Vec<T> de longitud N es O(N) (búsqueda lineal).
• Buscar en un HashSet<T> de longitud N es O(1) (tiempo constante promedio).

A partir de esta afirmación, muchos desarrolladores cometen el error de sustituir cualquier vector pequeño por un HashSet. En la práctica de sistemas reales de alto rendimiento, esto suele degradar la velocidad en colecciones pequeñas (N ≤ 20-30):

¿Por qué?#

1. *Líneas de caché L1 (Cache Lines): La CPU no lee datos de la memoria RAM byte por byte; transfiere bloques enteros de 64 bytes contiguos llamados líneas de caché*.
2. Contigüidad del vector: En un Vec<u32>, cada entero ocupa 4 bytes. En una sola línea de caché de 64 bytes caben exactamente 16 enteros contiguos. Cuando el procesador lee el primer elemento numbers[0], el controlador de memoria de la CPU precarga automáticamente los siguientes 15 elementos en la memoria caché L1 (que tiene una latencia de ~1 nanosegundo). El recorrido lineal por tanto se ejecuta íntegramente en caché ultrarrápida.
3. El costo oculto de HashSet: - Debe calcular el código hash de 64 bits de la clave mediante SipHash. - Debe aplicar máscara de bits para encontrar la cubeta. - Debe desreferenciar punteros hacia la tabla de cubetas, provocando con frecuencia fallos de caché (cache misses), obligando a la CPU a esperar cientos de ciclos de reloj a que los datos viajen desde la memoria RAM principal.
4. Conclusión ingenieril: Para listas cortas de filtrado (por ejemplo, verificar si una etiqueta pertenece a una lista de 5 etiquetas prohibidas), un escaneo lineal sobre un slice con blocked.iter().any(...) es sustancialmente más rápido, no requiere asignaciones en el heap y consume menos memoria que construir un HashSet. Solo cuando las colecciones escalan a cientos o miles de registros se justifica la transición a una tabla hash.

Diagrama#

flowchart LR
    A[Vec de entradas] --> B[iter presta cada elemento]
    B --> C[filter conserva coincidencias]
    C --> D[collect materializa resultados]
    A --> E[get índice]
    E -->|Some| F[referencia al elemento]
    E -->|None| G[índice fuera de rango]

Cada operación conserva el mismo tipo de colección salvo que el tipo de elemento o el consumidor final cambie.

Ejemplo razonado#

El siguiente bloque es un programa completo y ejecutable con pruebas. Demuestra cómo filtrar una colección de cadenas prestando las entradas y construyendo un resultado independiente que preserva el orden original:

// Contract: Filters a slice of labels, removing any label that exists in the blocked list.
// Preserves the original order and retains duplicates if they are not blocked.
// Borrows inputs via slices; allocates and returns a new owned Vec<String>.
fn active_labels(labels: &[String], blocked: &[String]) -> Vec<String> {
    labels
        .iter()
        .filter(|label| !blocked.iter().any(|item| item == *label))
        .cloned()
        .collect()
}

#[cfg(test)]
mod tests {
    use super::active_labels;

    #[test]
    fn removes_blocked_labels_and_keeps_the_order() {
        let labels = vec![
            String::from("rust"),
            String::from("web"),
            String::from("rust"),
        ];
        let blocked = vec![String::from("web")];

        // Should eliminate "web" and preserve both instances of "rust" in order
        assert_eq!(
            active_labels(&labels, &blocked),
            vec![String::from("rust"), String::from("rust")]
        );
    }

    #[test]
    fn handles_empty_lists_and_no_matches() {
        let empty_labels: Vec<String> = vec![];
        let blocked = vec![String::from("spam")];
        assert_eq!(active_labels(&empty_labels, &blocked), Vec::<String>::new());

        let labels = vec![String::from("clean")];
        let empty_blocked: Vec<String> = vec![];
        assert_eq!(active_labels(&labels, &empty_blocked), vec![String::from("clean")]);
    }
}

Comentario línea por línea y análisis técnico:#

• Línea 4: fn active_labels(labels: &[String], blocked: &[String]) -> Vec<String>
• La firma expresa un contrato de préstamo limpio: recibe vistas inmutables &[String]. Quien invoca la función conserva la propiedad de sus vectores originales sin clonarlos para la llamada.
• El retorno Vec<String> comunica que la función entregará un contenedor poseído nuevo e independiente cuyos datos sobrevivirán a la llamada.
• Línea 5: labels.iter()
• Produce un iterador que rinde referencias prestadas &String.
• Línea 6: .filter(|label| !blocked.iter().any(|item| item == *label))
• label tiene tipo &String dentro de la clausura (tras desreferenciación implícita de &&String).
• blocked.iter().any(...) recorre la lista de bloqueados. .any() es un consumidor terminal de cortocircuito: en cuanto encuentra la primera coincidencia, detiene la iteración y devuelve true de inmediato.
• item == *label compara el contenido de las dos cadenas de texto.
• El prefijo ! invierte la lógica: solo se conservan las etiquetas que no están bloqueadas.
• Línea 7: .cloned()
• Dado que los elementos que pasaron el filtro son referencias &String, necesitamos convertirlos en cadenas poseídas String para poder ensamblar el nuevo vector. .cloned() invoca .clone() sobre cada elemento que superó el filtro.
• Línea 8: .collect()
• Consumidor terminal que recopila todos los elementos en un nuevo contenedor Vec<String> en el heap y lo devuelve.

Práctica independiente#

Ejercicio propuesto: Búsqueda segura de primera posición y acceso acotado#

Debes implementar dos funciones fundamentales de inspección sobre colecciones:

Función 1: Localización del primer índice coincidente#

pub fn find_first_occurrence(items: &[u32], target: u32) -> Option<usize>

Especificación y reglas de dominio:#

1. La función debe recorrer el slice items y retornar Some(index) correspondiente al índice en base cero de la primera aparición del valor target.
2. Si target no se encuentra presente en la colección, debe retornar None.
3. Si la colección de entrada está vacía (items.is_empty()), debe retornar None.
4. Invariante de duplicados: Si el elemento buscado aparece múltiples veces (por ejemplo, en [4, 7, 7, 9] buscando el número 7), la función debe devolver estrictamente la primera posición (Some(1)), nunca la segunda (Some(2)).

Función 2: Acceso seguro a elementos mediante índice#

pub fn safe_get_element(items: &[u32], index: usize) -> Option<u32>

Especificación:#

1. Utiliza el método .get(index) de la biblioteca estándar para leer el elemento en la posición solicitada.
2. Si el índice es válido, devuelve Some(valor).
3. Si el índice excede el tamaño del slice, devuelve None de forma segura, garantizando que el sistema no colapse bajo ninguna circunstancia.

Matriz de casos de prueba obligatorios (RED arrow GREEN arrow REFACTOR):#

Pasos guiados para el desarrollo:#

1. Fase RED: Crea search.rs con las firmas retornando todo!(). Escribe la suite de pruebas con los 8 casos de la matriz anterior. Comprueba el fallo con rustc --test search.rs.
2. Fase GREEN: Implementa find_first_occurrence utilizando el método .position() de iteradores (o un bucle manual for (idx, &item) in items.iter().enumerate()). Implementa safe_get_element utilizando .get(index).copied(). Verifica que las pruebas pasen al 100%.
3. Fase REFACTOR: Compara la legibilidad del código. ¿Es la solución idiomática, concisa y libre de advertencias de compilación?

Preguntas de comprensión profunda y diagnóstico socrático#

Reflexiona críticamente sobre estas cinco preguntas avanzadas sobre memoria y rendimiento:

Pregunta 1: La referencia doble en la firma de .filter()#

Examina esta línea de código:

let values = vec![10, 20, 30];
let count = values.iter().filter(|x| **x > 15).count();

• Explica minuciosamente por qué se requieren dos asteriscos de desreferenciación (**x) para comparar el valor con el escalar 15.
• ¿Cuál es el tipo de x en la firma de la clausura si iteramos con values.into_iter().filter(...)? ¿Por qué cambia de &&i32 a &i32?

Pregunta 2: Los tres modos de iteración y el estado del contenedor#

Supón que tienes una variable let mut names = vec![String::from("Alpha")];.

• Si ejecutas un bucle for name in names.iter() { ... }, ¿puedes volver a usar names debajo del bucle? ¿Por qué?
• Si ejecutas un bucle for name in names.into_iter() { ... }, ¿puedes volver a usar names debajo del bucle? Explica qué ocurrió con el descriptor de 24 bytes de names en la pila.
• Si necesitas modificar cada elemento en sitio (por ejemplo, convertir cada cadena a mayúsculas sin crear un nuevo vector), ¿cuál de los tres modos debes elegir y cuál es el tipo exacto que recibe el cuerpo del bucle?

Pregunta 3: Evaluación perezosa y fusión de iteradores#

Considera este fragmento:

let data = vec![1, 2, 3, 4, 5];
let pipeline = data.iter().map(|x| {
    println!("Mapping {x}");
    x * 2
}).take(2);

• Si ejecutas ese código exactamente como está escrito, ¿cuántos mensajes se imprimen en la consola del sistema? (Justifica tu respuesta explicando el concepto de lazy evaluation).
• Si a la línea anterior le añades .collect::<Vec<_>>(), ¿cuántas veces se ejecuta la clausura del map? ¿Se ejecuta para los 5 elementos o solo para los primeros 2?

Pregunta 4: Peligros de indexación directa v[i] en arquitecturas web#

Imagina un endpoint HTTP en un servidor backend que recibe una lista de compras y un parámetro de consulta selected_index: usize:

// Endpoint vulnerable
let item = cart.items[selected_index];

• ¿Qué sucede a nivel de proceso si un atacante envía deliberadamente selected_index = 999999 cuando el carrito solo tiene 2 artículos?
• ¿Por qué el uso de cart.items.get(selected_index) mitiga completamente este riesgo arquitectónico?
• ¿Cómo se traduce esto a una respuesta HTTP controlada (como 400 Bad Request o 422 Unprocessable Entity) en lugar de una caída abrupta del proceso con código de salida no cero?

Pregunta 5: La paradoja de hardware: ¿Cuándo O(N) vence a O(1)?#

Supón un servicio web de procesamiento de texto que analiza 50,000 comentarios de usuarios por segundo. Cada comentario se contrasta contra una lista negra de 6 palabras prohibidas (["spam", "bot", "ad", ...]).

• Un ingeniero propone construir un HashSet<String> con las 6 palabras para lograr búsquedas O(1) en cada palabra de cada comentario.
• Otro ingeniero argumenta que mantener un simple arreglo [&str; 6] y hacer una búsqueda lineal secuencial es sustancialmente más rápido en tiempo real de CPU y consume menos memoria.
• ¿Quién tiene la razón desde la física del hardware moderno? Explica el papel de las líneas de caché L1 (64 bytes), los fallos de caché (cache misses) y el sobrecoste de cálculo de la función hash SipHash.

Code smell#

Síntoma: Búsqueda lineal anidada cuadrática O(N × M) en colecciones masivas#

Observa la función de ejemplo razonado:

labels
    .iter()
    .filter(|label| !blocked.iter().any(|item| item == *label))
    .cloned()
    .collect()

• Evidencia observable: Para cada elemento del vector labels (N elementos), se recorre secuencialmente el vector blocked (M elementos) de principio a fin. El número total de comparaciones de cadenas es en el peor caso de N × M.
• Hipótesis del problema: Si labels contiene 10,000 registros y blocked contiene 5,000 registros, el sistema realizará hasta 50,000,000 de comparaciones de texto en cada invocación, bloqueando el hilo de ejecución por cientos de milisegundos.
• Consecuencia concreta: Caída abrupta del rendimiento y aumento de la latencia en el servidor backend al procesar lotes grandes de información.
• Tratamiento mínimo justificado: Si el tamaño de las colecciones es grande, construir previamente un HashSet con la lista de bloqueados:

  use std::collections::HashSet;

  fn active_labels_scalable(labels: &[String], blocked: &[String]) -> Vec<String> {
      let blocked_set: HashSet<&str> = blocked.iter().map(|s| s.as_str()).collect();
      labels
          .iter()
          .filter(|label| !blocked_set.contains(label.as_str()))
          .cloned()
          .collect()
  }

Esto reduce la complejidad de O(N × M) a O(N + M) lineal.

• Cuándo NO refactorizar: Si blocked es una lista estática de 2 o 3 elementos (como ignorar etiquetas vacías o estados reservadas), no utilices HashSet. El costo de asignar nodos en el heap y calcular hashes para 3 palabras es mayor que realizar 3 comparaciones directas en la caché L1 del procesador. Diseña según la escala real de los datos, no por dogmas prematuros de optimización.

Criterio de salida#

Puedes considerar superada esta lección con maestría cuando:

• Puedes explicar con precisión técnica por qué .filter() rinde una referencia doble &&T sobre .iter() y cómo desestructurarla o desreferenciarla idiomáticamente.
• Tu batería de pruebas para find_first_occurrence y safe_get_element pasa limpiamente con rustc --test, cubriendo casos de ausencia, elementos duplicados y accesos fuera de rango.
• Distingues con solidez cuándo utilizar Vec<T> frente a HashMap<K, V> según la necesidad de conservar orden de inserción y la escala de volumen de datos.
• Puedes justificar desde la física del hardware por qué una búsqueda lineal sobre una lista contigua pequeña supera en velocidad a una tabla hash.

Lecturas oficiales#

• Rust Book, Vectores: Creación, lectura e indexación segura en secuencias contiguas.
• Rust Book, Tablas Hash: Mapeo clave-valor, inserción con entrada condicional y propiedad.
• Rust Book, Iteradores y Closures: Adaptadores perezosos, consumidores y abstracciones de costo cero.
• Glosario técnico del curso: Consulta definiciones canónicas sobre traits de colección y complejidad algorítmica.

Siguiente paso#

¡Felicidades por completar las bases sólidas de Rust! Continúa con el módulo de backend en 05 · Contratos HTTP y deserialización, donde aplicarás estos conocimientos de tipado estricto, ownership y colecciones en el diseño de APIs seguras y de alto rendimiento en la frontera de red entre cliente y servidor.