Caixa de Ferramentas II: Vetores, Matrizes, Vistas e Algoritmos

O Artigo 4 cuidou dos valores: o tipo de um literal, as constantes calculadas pelo compilador, as funções genéricas e as lambdas. Este artigo cuida de onde os valores moram e de como são percorridos. A pergunta que atravessa todas as seções é a mesma que o Artigo 2 fez sobre a memória: quem é dono destes bytes, onde eles estão e em que ordem o programa vai visitá-los? Um vetor é dono. Uma vista não é. Uma matriz pode ser um bloco contíguo ou uma coleção de blocos espalhados. Um algoritmo da biblioteca padrão consome uma sequência sem se importar com quem a guarda.

A maior parte das soluções de competição usa três ou quatro contêineres e uma dúzia de algoritmos. Conhecer o custo exato desses poucos instrumentos rende mais do que conhecer superficialmente todos os outros. Por isso, cada ferramenta deste artigo vem acompanhada de uma conta e de uma medição. A conta diz o que deveria acontecer. A medição diz o que aconteceu no MSVC do Visual Studio 18.10.3, compilado com /std:c++latest /O2 /W4 /permissive-, em um Intel Core i7-10750H. Quando as duas discordam, é a conta que precisa ser revista.

1. Vetores: posse, tamanho e capacidade

std::vector<T> é um arranjo contíguo de tamanho variável. A palavra que define o vetor é posse: ele aloca a memória, constrói os elementos nela, destrói os elementos e libera a memória quando deixa de existir. Uma função que recebe std::vector<T> por valor recebe um vetor seu, copiado. Uma função que recebe std::vector<T>& recebe acesso ao vetor de quem chamou. Uma função que recebe std::span<T>, assunto da Seção 3, recebe apenas uma vista sobre memória contígua que pertence a outro objeto.

Um vetor guarda três informações: onde começa o bloco alocado, quantos elementos estão vivos e quantos elementos o bloco comporta. As duas últimas têm nomes. size() é o tamanho, o número de elementos vivos. capacity() é a capacidade, o número de elementos que o bloco atual comporta sem uma nova alocação. A diferença entre as duas é uma reserva de memória que o vetor mantém para que o próximo push_back seja barato.

1.1 Crescimento geométrico e custo amortizado

Quando o tamanho alcança a capacidade, o próximo push_back não cabe. O vetor então aloca um bloco maior, move os elementos antigos para ele, libera o bloco anterior e só então insere o novo elemento. Essa operação custa $O(n)$, porque move todos os elementos vivos. A pergunta é com que frequência ela acontece.

A resposta depende da regra de crescimento, que a norma não fixa. A norma exige apenas que push_back tenha custo amortizado constante, isto é, que o custo total de $n$ inserções seja $O(n)$, ainda que uma inserção isolada custe caro. As bibliotecas cumprem essa exigência multiplicando a capacidade por um fator a cada troca de bloco. A biblioteca do MSVC usa $g=1,5$: a nova capacidade será dada por

$$\text{nova}=\text{antiga}+\lfloor \frac{\text{antiga}}{2}\rfloor ,$$