Tipos abstratos e escolha da representação

Uma pilha que recebe 4, 7 e 2 tem de retirar 2 primeiro. Este comportamento LIFO, último a entrar, primeiro a sair, é o mesmo se os valores estiverem num vetor ou em nós ligados. A representação muda os custos e as regras de memória, sem mudar a ordem das saídas.

Um tipo abstrato de dados, TAD, especifica os valores e as operações observáveis. O cliente usa esse contrato sem depender dos campos que a implementação guarda. As lições anteriores fixaram contratos e contagens; esta página usa-os para escolher a representação.

Interface, contrato e representação

Para uma lista de valores, oferece size, empty, consulta por posição, inserção e remoção. Cada operação precisa de condições, ou seja, de um contrato. Consultar a posição i exige 0<=i<size. Retirar o primeiro elemento exige uma lista não vazia, ou uma interface que devolva explicitamente uma ausência.

O invariante da representação liga os campos privados ao valor abstrato. Numa lista simplesmente ligada com primeiro e tamanho:

• primeiro é nulo exatamente quando o tamanho é zero.
• A cadeia termina num apontador nulo, não tem ciclos e contém exatamente tamanho nós.
• Cada nó pertence à lista; não o libertes enquanto continuar ligado.

O construtor estabelece o invariante. Cada método público assume-o à entrada e repõe-o à saída. O destrutor liberta os recursos possuídos. Se os campos fossem públicos, o utilizador criaria uma cadeia cíclica ou um tamanho falso sem passar pelos métodos.

Distingue o valor abstrato de um detalhe interno: uma fila vazia não precisa de ter um índice interno igual a zero, e um cliente que só usa size, empty, consulta por posição, inserção e remoção não distingue se por baixo está um vetor ou nós ligados.

Com um milhão de consultas por índice e poucas inserções no fim, o vetor calcula o endereço em tempo constante e a lista percorre i+1 nós por consulta, por isso a escolha segue a operação dominante, não o nome da estrutura. Uma representação só pode substituir a outra se ambas respeitarem os mesmos resultados e pré-condições.

Vetor ou nós ligados

Operação	Vetor contíguo	Lista simplesmente ligada
acesso à posição i	$O(1)$	$O(i+1)$
inserir/remover à frente	$O(n)$	$O(1)$
acrescentar no fim	$O(1)$ amortizado com crescimento	$O(1)$ com apontador para último; $O(n)$ sem ele
remover o último	$O(1)$	$O(n)$ para encontrar o anterior
inserir depois de um nó conhecido	deslocações $O(n)$ no caso geral	$O(1)$
memória por elemento	valor e eventual capacidade livre	valor e um ou mais apontadores

«Inserir numa lista é constante» só vale se já tens a ligação ou o nó necessário, porque encontrar a posição pode dominar o custo. Num vetor, a memória contígua favorece acessos sequenciais. A lista evita algumas deslocações, mas paga alocações e segue apontadores.

Uma lista duplamente ligada conhece o anterior de cada nó, por isso retira um nó conhecido em $O(1)$. Mas continua sem acesso direto por índice, ou seja, não faz pesquisa binária eficiente por sucessivos meios. Um vetor ordenado consulta em binário depressa, mas inserir mantendo a ordem exige deslocações.

Memória, cópia e iteradores

Uma estrutura que possui nós dinâmicos precisa de uma política de cópia: copiar profundamente, transferir posse ou impedir a cópia. Copiar só o apontador inicial cria dois proprietários dos mesmos nós. Os exemplos de nós desta cadeira impedem a cópia e libertam os nós no destrutor. Os containers da biblioteca tratam essa posse por ti.

Um iterador identifica uma posição segundo as regras do container. Num vector, realocar invalida todos os iteradores, referências e apontadores para elementos, e mesmo sem realocação uma inserção pode invalidar os que apontam para a posição de inserção ou depois dela.

Num list, inserir preserva iteradores existentes e apagar invalida só os do elemento apagado, por isso consulta a garantia da operação concreta antes de guardares um iterador entre alterações.

Os templates exprimem uma estrutura para tipos diferentes. Mas generalizar o nome do tipo não prova as propriedades usadas: ordenar exige comparação válida, copiar exige que o tipo suporte essa cópia e acumular exige operações aritméticas adequadas.

Biblioteca e composição de custos

vector, list, deque, stack, queue, set, map, unordered_set, unordered_map e priority_queue oferecem interfaces diferentes. stack e queue são adaptadores, ou seja, limitam as operações de um container subjacente. Uma fila de prioridade escolhe por prioridade, não por ordem de chegada.

Ao analisar um algoritmo, substitui cada chamada pelo seu custo real. Fazer n inserções num set custa $O(n\log n)$; percorrê-lo inteiro custa $O(n)$. Fazer n consultas esperadas constantes numa tabela hash dá custo esperado linear sob as hipóteses de hashing, sem garantia linear de pior caso.

Copiar uma estrutura por valor ao chamar uma função pode custar mais que a função em si, por isso usa referência constante se só precisas de ler.

Implementar e testar um contrato

Antes de programares, escreve a entrada, a saída, os limites e a política de casos especiais. Se usas índices em [0,n), conserva essa convenção em todas as funções. Se os enunciados usam [1,n], converte uma vez na fronteira de entrada.

Para cada operação, testa vazio, um elemento, repetidos, alteração da frente e do fim, ausência de uma chave e várias operações seguidas. Depois de cada alteração, confere o invariante, não só uma impressão final, porque uma lista com tamanho correto e um ciclo continua inválida.

Compara o teu algoritmo com uma solução simples e independente em entradas pequenas: pesquisa com um percurso linear, ordenação com a biblioteca, caminhos de grafos com uma matriz de alcançabilidade. A referência pode ser lenta, porque o seu papel é detetar erros.

Compila em C++17 com avisos, por exemplo g++ -std=c++17 -Wall -Wextra -Wpedantic programa.cpp -o programa. Separa interface e implementação para documentares as pré-condições de cada método. Em submissões automáticas, lê exatamente o formato pedido e imprime apenas a saída exigida, porque uma mensagem de depuração invalida uma resposta correta. Verifica overflow, limites de memória e profundidade da recursão antes de aumentares a dimensão dos testes.