Síntese e desafios: dados compostos

O que a unidade alcançou

A unidade propôs-se ensinar a representar coleções de dados e a processá-las com os algoritmos básicos, estimando quanto custam. Conseguiu-o apoiando-se apenas no que a introdução declarou como sabido: os laços com invariante, as funções e os seus modos de passagem, a aritmética dos inteiros. O programa das pontuações, que com cinco variáveis calava os dados excedentes, escreve-se agora com um vetor; e a pergunta pelos empates, que com todos os pares exigia minutos para um milhão de dados, responde-se ordenando e comparando vizinhos.

Arranjos

A aula Arranjos apresentou std::array, a sequência de tamanho fixo, cujos índices contam a partir de zero porque são deslocamentos. Estabeleceu que o índice $i$ é válido se e somente se $0 \leq i < n$, que cada acesso com [] exige demonstrá-lo com o invariante do laço, e que o acesso fora dos limites é comportamento indefinido, que .at() converte numa parada definida; introduziu std::size_t e ensinou a ler os arranjos de C.

Vetores

A aula Vetores apresentou a sequência que cresce com push_back e fixou quando é preciso guardar uma série: se alguma decisão sobre um dado depende de dados posteriores. Estabeleceu os percursos canônicos (acumular, filtrar, transformar) com os seus invariantes e as suas abreviaturas na biblioteca (std::ranges::count, std::ranges::max, std::ranges::fold_left), a regra da passagem de um vetor, e a diferença entre tamanho e capacidade, da qual decorrem o custo constante em média de push_back e a invalidação das referências quando o vetor se muda.

O custo de um algoritmo

A aula O custo de um algoritmo acrescentou a segunda pergunta: contar a operação dominante no pior caso, classificar pela ordem de crescimento, prever o efeito de duplicar $n$ e medir com std::chrono::steady_clock, com otimização, sem detectores, repetindo e tomando a mediana.

Buscar e ordenar

A aula Buscar e ordenar justificou a busca binária com o seu invariante e a sua medida; escreveu a seleção e a inserção, contando as suas comparações; apresentou os algoritmos de ranges com a pré-condição da ordem, que ninguém verifica; e calculou quando convém ordenar antes de buscar.

Tabelas

A aula Tabelas percorreu as tabelas por linhas e por colunas, calculou a transposta e o produto de matrizes, com o seu custo cúbico, contou vizinhos sem sair das bordas e guardou uma tabela num vetor plano com o índice $i \cdot \mathit{columns} + j$.

Registros

A aula Registros substituiu os vetores paralelos pelo struct, com um valor inicial em cada campo; ensinou a passar e devolver registros, a ordená-los e buscá-los por um campo com uma projeção, a ordenar por vários critérios com std::ranges::stable_sort e a modelar um problema com registros que contêm registros e vetores.