O conjunto: só importa se tem, e sem repetir

A lista de convidados

A lista, o dicionário e agora o conjunto formam o trio de estruturas do intermediário, e cada uma responde a uma pergunta diferente. A lista responde qual é a ordem e o que está na posição tal. O dicionário responde qual o valor da etiqueta tal. O conjunto responde a mais simples de todas: este item está no grupo? Pense numa lista de convidados de uma festa. Não importa a ordem em que os nomes foram anotados, e não faz sentido a mesma pessoa aparecer duas vezes: ou ela está convidada, ou não está. Esse é o espírito do conjunto. Ele ignora ordem e ignora repetição, porque para o problema que ele resolve nenhuma das duas coisas importa.

A unicidade é a marca registrada do conjunto, e ela é automática. Se você tenta adicionar um nome que já está na lista de convidados, nada acontece: a pessoa continua convidada uma vez só. Essa propriedade, que numa lista você teria que garantir na mão (checando se o item já existe antes de adicionar), o conjunto entrega de graça. Por isso, sempre que você tem uma coleção em que duplicados não fazem sentido, os alunos que entregaram a tarefa, os e-mails únicos de uma campanha, as tags de um artigo, o conjunto costuma ser a estrutura mais limpa e menos sujeita a erro.

Sem ordem e sem posição

A segunda diferença do conjunto para a lista é a ausência de ordem. Numa lista, o primeiro item é o primeiro, e você pode pedir a posição 0. Num conjunto, não existe primeiro nem último: os itens estão dentro do grupo, e ponto. Por isso você não acessa um elemento do conjunto por posição, como faria numa lista; não faz sentido perguntar qual é o terceiro item de um conjunto. O que você pergunta é se um item específico pertence. Essa é uma mudança de mentalidade: a lista é uma fila organizada, o conjunto é um saco de itens únicos. Se o seu problema depende de ordem (um ranking, um histórico), o conjunto é a estrutura errada; se depende só de pertencimento e unicidade, ele é perfeito.

convidados <- conjunto vazio
adicione("Ana", convidados)
adicione("Beto", convidados)
adicione("Ana", convidados)   // Ana já está: ignorado
escreva(tamanho(convidados))   // 2, não 3
// o conjunto tem { "Ana", "Beto" }, sem ordem garantida

Adicionar Ana duas vezes não cria duplicado. O tamanho é 2 porque o conjunto só guarda itens únicos.

tags <- conjunto vazio
adicione("promo", tags)
adicione("novo", tags)
adicione("promo", tags)
adicione("oferta", tags)
adicione("novo", tags)
escreva(tamanho(tags))

Quando o conjunto vence

O conjunto brilha em duas situações. A primeira é quando você quer garantir que não há repetidos sem trabalho extra: em vez de checar antes de cada inserção, você joga tudo num conjunto e a unicidade acontece sozinha. A segunda é quando a operação principal é perguntar pertence?, e você quer essa resposta rápida. Assim como o dicionário busca pela chave quase instantaneamente, o conjunto responde ao pertence sem varrer os itens, o que faz muita diferença em grupos grandes. Um sistema que precisa checar milhares de vezes se um usuário já votou, se um e-mail já está cadastrado, se uma palavra está na lista de proibidas, usa conjunto justamente por essa resposta veloz, tema da próxima aula.