Síntesis y desafíos: datos compuestos

Lo logrado en la unidad

La unidad se propuso enseñar a representar colecciones de datos y a procesarlas con los algoritmos básicos, estimando cuánto cuestan. Lo ha logrado apoyándose solo en lo que la introducción declaró por sabido: los bucles con invariante, las funciones y sus modos de paso, la aritmética de los enteros. El programa de los puntajes, que con cinco variables callaba los datos sobrantes, se escribe ahora con un vector; y la pregunta por los empates, que con todos los pares exigía minutos para un millón de datos, se responde ordenando y comparando vecinos.

Arreglos

La clase Arreglos presentó std::array, la secuencia de tamaño fijo, cuyos índices cuentan desde cero porque son desplazamientos. Estableció que el índice $i$ es válido si y solo si $0 \leq i < n$, que cada acceso con [] exige demostrarlo con el invariante del bucle, y que el acceso fuera de los límites es comportamiento indefinido, que .at() convierte en una detención definida; introdujo std::size_t y enseñó a leer los arreglos de C.

Vectores

La clase Vectores presentó la secuencia que crece con push_back y fijó cuándo hace falta guardar una serie: si alguna decisión sobre un dato depende de datos posteriores. Estableció los recorridos canónicos (acumular, filtrar, transformar) con sus invariantes, la regla del paso de un vector, y la diferencia entre tamaño y capacidad, de la que se siguen el costo constante en promedio de push_back y la invalidación de las referencias cuando el vector se muda.

El costo de un algoritmo

La clase El costo de un algoritmo añadió la segunda pregunta: contar la operación dominante en el peor caso, clasificar por el orden de crecimiento, predecir el efecto de duplicar $n$ y medir con std::chrono::steady_clock, con optimización, sin detectores, repitiendo y tomando la mediana.

Buscar y ordenar

La clase Buscar y ordenar justificó la búsqueda binaria con su invariante y su medida; escribió la selección y la inserción, contando sus comparaciones; presentó los algoritmos de rangos con la precondición del orden, que nadie comprueba; y calculó cuándo conviene ordenar antes de buscar.

Tablas

La clase Tablas recorrió las tablas por filas y por columnas, calculó la traspuesta y el producto de matrices, con su costo cúbico, contó vecinos sin salir de los bordes y guardó una tabla en un vector plano con el índice $i \cdot \mathit{columns} + j$.

Registros

La clase Registros reemplazó los vectores paralelos por el struct, con un valor inicial en cada campo; enseñó a pasar y devolver registros, a ordenarlos y buscarlos por un campo con una proyección, a ordenar por varios criterios con std::ranges::stable_sort y a modelar un problema con registros que contienen registros y vectores.