HashSet e BTreeMap em Rust

Um HashSet é uma coleção de valores únicos (um conjunto). Se você colocar o mesmo valor duas vezes, ele só é guardado uma vez. Pense na lista de convidados na porta de uma festa: o segurança só quer saber se o seu nome está na lista, não quantas vezes ele foi escrito.

Você já conhece o Vec e o HashMap. Esta página apresenta as outras coleções que você vai usar com mais frequência: HashSet, os ordenados BTreeMap e BTreeSet, e VecDeque para filas. No fim, há uma tabela para ajudar você a escolher a certa.

Criando um HashSet

O HashSet fica em std::collections, então você precisa de uma linha use. O método insert devolve um bool: true se o valor era novo, false se ele já estava lá.

use std::collections::HashSet;

fn main() {
    let mut tags = HashSet::new();

    println!("{}", tags.insert("rust"));
    println!("{}", tags.insert("web"));
    println!("{}", tags.insert("rust")); // já está lá

    println!("{} tags únicas", tags.len());
}

Saída:

true
true
false
2 tags únicas

▶ Experimente você mesmo

Esse bool é mais útil do que parece. Ele responde “já vi isso antes?” no mesmo passo em que adiciona o valor, então você não precisa de uma verificação separada.

Verificando e removendo valores

contains diz se um valor está no conjunto. remove tira o valor e, assim como insert, devolve um bool dizendo se alguma coisa foi removida de fato.

use std::collections::HashSet;

fn main() {
    let mut online: HashSet<&str> = HashSet::from(["ana", "ben", "chen"]);

    println!("ben está online? {}", online.contains("ben"));

    println!("ben removido: {}", online.remove("ben"));
    println!("ben removido de novo: {}", online.remove("ben"));

    println!("ben está online? {}", online.contains("ben"));
    println!("{} pessoas online", online.len());
}

Saída:

ben está online? true
ben removido: true
ben removido de novo: false
ben está online? false
2 pessoas online

▶ Experimente você mesmo

Por que usar um conjunto em vez de um Vec aqui? Fazer contains em um Vec olha cada item, um por um. Um HashSet vai direto à resposta, não importa o tamanho dele. Com um milhão de usuários, essa diferença é enorme.

Cuidado

Um HashSet não tem ordem fixa. Se você imprimir com {:?} ou percorrer o conjunto, a ordem pode mudar de uma execução para outra. Quando precisar de uma ordem estável para imprimir, copie os valores para um Vec e ordene, ou use um BTreeSet (explicado mais abaixo).

Removendo duplicados de um Vec

Uma tarefa muito comum: você tem uma lista com repetições e quer cada valor uma vez só. Há dois bons jeitos, dependendo de você se importar ou não com a ordem original.

use std::collections::HashSet;

fn main() {
    let visits = vec![3, 1, 3, 2, 1, 5, 2];

    // Jeito 1: juntar em um conjunto e depois ordenar para ter uma ordem estável
    let unique: HashSet<i32> = visits.iter().copied().collect();
    let mut sorted: Vec<i32> = unique.into_iter().collect();
    sorted.sort();
    println!("sorted unique: {:?}", sorted);

    // Jeito 2: manter a primeira vez que cada valor aparece, na ordem original
    let mut seen = HashSet::new();
    let mut in_order = visits.clone();
    in_order.retain(|x| seen.insert(*x));
    println!("in order:      {:?}", in_order);
}

Saída:

sorted unique: [1, 2, 3, 5]
in order:      [3, 1, 2, 5]

▶ Experimente você mesmo

Os rótulos ficaram em inglês (“sorted unique” = “únicos ordenados”, “in order” = “na ordem original”) porque estão alinhados em colunas com espaços.

O jeito 2 usa o bool de insert. retain só mantém um item quando a closure (função anônima) devolve true, e insert só devolve true na primeira vez que vê um valor.

Operações de conjuntos: união, interseção, diferença

Conjuntos podem ser combinados como os círculos de um diagrama de Venn. Cada método devolve um iterador, então juntamos os resultados em um Vec e ordenamos antes de imprimir, para ter sempre a mesma saída.

use std::collections::HashSet;

fn main() {
    let alice: HashSet<&str> = HashSet::from(["rust", "python", "go"]);
    let bob: HashSet<&str> = HashSet::from(["go", "java", "rust"]);

    let mut both: Vec<_> = alice.intersection(&bob).collect();
    both.sort();
    println!("both know:      {:?}", both);

    let mut either: Vec<_> = alice.union(&bob).collect();
    either.sort();
    println!("either knows:   {:?}", either);

    let mut only_alice: Vec<_> = alice.difference(&bob).collect();
    only_alice.sort();
    println!("only alice:     {:?}", only_alice);

    let mut only_one: Vec<_> = alice.symmetric_difference(&bob).collect();
    only_one.sort();
    println!("only one knows: {:?}", only_one);
}

Saída:

both know:      ["go", "rust"]
either knows:   ["go", "java", "python", "rust"]
only alice:     ["python"]
only one knows: ["java", "python"]

▶ Experimente você mesmo

De novo, os rótulos alinhados ficaram em inglês: “both know” (os dois sabem), “either knows” (pelo menos um sabe), “only alice” (só a Alice) e “only one knows” (só um dos dois sabe).

difference funciona em um sentido só: alice.difference(&bob) é “o que a Alice sabe e o Bob não”. Troque os dois de lugar e você recebe a lista do Bob. symmetric_difference pega os dois lados de uma vez: tudo o que só um deles sabe.

BTreeMap e BTreeSet: sempre ordenados

O BTreeMap funciona igualzinho ao HashMap, e o BTreeSet funciona igualzinho ao HashSet. A diferença: eles mantêm as chaves ordenadas. Quando você percorre um deles, recebe as chaves em ordem, sempre.

use std::collections::{BTreeMap, BTreeSet};

fn main() {
    let text = "the cat sat on the mat the end";

    let mut counts: BTreeMap<&str, u32> = BTreeMap::new();
    for word in text.split_whitespace() {
        *counts.entry(word).or_insert(0) += 1;
    }
    for (word, count) in &counts {
        println!("{word}: {count}");
    }

    let scores: BTreeSet<u32> = BTreeSet::from([72, 95, 58, 88]);
    println!("menor: {:?}", scores.first());
    println!("maior: {:?}", scores.last());
    println!("todas: {:?}", scores);
}

Saída:

cat: 1
end: 1
mat: 1
on: 1
sat: 1
the: 3
menor: Some(58)
maior: Some(95)
todas: {58, 72, 88, 95}

▶ Experimente você mesmo

A frase ficou em inglês (“o gato sentou no tapete, o fim”) porque a saída mostra as palavras em ordem alfabética, e com outras palavras a ordem seria outra. A API entry é a mesma que você viu na página de HashMap. Como o mapa é um BTreeMap, as palavras saem em ordem alfabética, sem nenhum passo extra de ordenação.

Qual escolher?

• Escolha HashMap / HashSet por padrão. As buscas costumam ser mais rápidas.
• Escolha BTreeMap / BTreeSet quando precisar dos dados em ordem: imprimir um relatório ordenado, achar a menor ou a maior chave, ou pegar um intervalo de chaves.

VecDeque: uma fila

Um VecDeque (pronuncia-se “vec deck”) é uma lista em que você pode adicionar e remover itens rapidamente nas duas pontas. Isso faz dele a escolha natural para uma fila: o primeiro que entra é o primeiro que sai, como pessoas esperando na fila do banco.

use std::collections::VecDeque;

fn main() {
    let mut line: VecDeque<&str> = VecDeque::new();
    line.push_back("ana");
    line.push_back("ben");
    line.push_back("chen");

    while let Some(person) = line.pop_front() {
        println!("atendendo {person}, {} ainda esperando", line.len());
    }
}

Saída:

atendendo ana, 2 ainda esperando
atendendo ben, 1 ainda esperando
atendendo chen, 0 ainda esperando

▶ Experimente você mesmo

Você poderia usar Vec::remove(0) para isso, mas ele empurra todos os outros itens uma posição para trás. O pop_front de um VecDeque não faz isso, então continua rápido mesmo com uma fila comprida.

Qual coleção devo usar?

Coleção	Use quando você precisa de…	Exemplo
Vec<T>	Uma lista ordenada, acessada pela posição	Linhas de um arquivo, uma lista de pontuações
HashMap<K, V>	Buscar rápido um valor pela chave	Nome de usuário → perfil do usuário
HashSet<T>	Valores únicos e checagens rápidas de “isto está aqui?”	Páginas visitadas, palavras proibidas
BTreeMap<K, V>	Chave → valor, com as chaves sempre ordenadas	Uma contagem de palavras impressa em ordem alfabética
VecDeque<T>	Adicionar/remover nas duas pontas	Uma fila de tarefas ou mensagens

Na dúvida, comece com um Vec. Troque quando perceber que está buscando nele o tempo todo (use um conjunto ou um mapa) ou removendo muito do começo (use um VecDeque).

Erros comuns

Colocar sua própria struct em um HashSet sem os derives certos. Um HashSet precisa calcular o hash dos valores e comparar se são iguais. Sua struct não faz isso automaticamente:

use std::collections::HashSet;

struct Point {
    x: i32,
    y: i32,
}

fn main() {
    let mut visited = HashSet::new();
    visited.insert(Point { x: 0, y: 0 });
}

error[E0277]: the trait bound `Point: Eq` is not satisfied
  --> src/main.rs:10:13
   |
10 |     visited.insert(Point { x: 0, y: 0 });
   |             ^^^^^^ the trait `Eq` is not implemented for `Point`

error[E0277]: the trait bound `Point: Hash` is not satisfied
  --> src/main.rs:10:13
   |
10 |     visited.insert(Point { x: 0, y: 0 });
   |             ^^^^^^ the trait `Hash` is not implemented for `Point`

O compilador está dizendo que Point não implementa os traits Eq e Hash, que o HashSet exige. A solução é uma linha acima da struct: #[derive(PartialEq, Eq, Hash)]. Para um BTreeSet você também precisaria de PartialOrd e Ord, para ele saber como ordenar. Veja Traits comuns para entender o que cada um significa.

use std::collections::HashSet;

#[derive(PartialEq, Eq, Hash)]
struct Point {
    x: i32,
    y: i32,
}

fn main() {
    let mut visited = HashSet::new();
    visited.insert(Point { x: 0, y: 0 });
    visited.insert(Point { x: 1, y: 0 });
    visited.insert(Point { x: 0, y: 0 }); // repetido, ignorado
    println!("{} casas visitadas", visited.len());
}

Saída:

2 casas visitadas

▶ Experimente você mesmo

Prática

1. A primeira repetição

Dadas as palavras ["vermelho", "azul", "verde", "azul", "vermelho"], imprima a primeira palavra que aparece pela segunda vez. Dica: insert devolve false quando o valor já está no conjunto, e break interrompe o laço.

Ver solução

use std::collections::HashSet;

fn main() {
    let words = ["vermelho", "azul", "verde", "azul", "vermelho"];
    let mut seen = HashSet::new();

    for word in words {
        if !seen.insert(word) {
            println!("Primeira repetição: {word}");
            break;
        }
    }
}

Saída:

Primeira repetição: azul

▶ Experimente você mesmo

!seen.insert(word) se lê como “a inserção falhou”, ou seja, “eu já vi essa antes”. "azul" é a primeira palavra a se repetir. "vermelho" também se repete, mas depois.

2. Letras em ordem

Conte quantas vezes cada letra aparece em "mississippi" e imprima as contagens em ordem alfabética. Dica: use um BTreeMap com o mesmo truque entry(...).or_insert(0) da seção sobre BTreeMap, e percorra word.chars().

Ver solução

use std::collections::BTreeMap;

fn main() {
    let word = "mississippi";
    let mut counts = BTreeMap::new();

    for letter in word.chars() {
        *counts.entry(letter).or_insert(0) += 1;
    }

    for (letter, count) in &counts {
        println!("{letter}: {count}");
    }
}

Saída:

i: 4
m: 1
p: 2
s: 4

▶ Experimente você mesmo

Com um HashMap, essas quatro linhas poderiam sair em qualquer ordem. O BTreeMap mantém as chaves ordenadas, então i, m, p, s saem em ordem alfabética todas as vezes.

Resumo

• HashSet guarda valores únicos. insert e remove devolvem um bool dizendo se algo mudou.
• contains em um conjunto é rápido, mesmo com conjuntos enormes. Em um Vec, ele confere item por item.
• union, intersection, difference e symmetric_difference fazem operações de conjuntos. Ordene os resultados antes de imprimir.
• BTreeMap e BTreeSet mantêm as chaves ordenadas; use-os quando a ordem importa.
• VecDeque é a fila padrão: push_back para entrar, pop_front para sair.

Teste o que aprendeu

Teste o que aprendeu

1. O que set.insert(x) devolve se x já está no conjunto?

true Um erro false O valor antigo

2. Você quer uma contagem de palavras impressa em ordem alfabética sem ter que ordenar por conta própria. Qual mapa serve melhor?

HashMap BTreeMap Vec VecDeque

3. Por que imprimir um HashSet com {:?} pode dar saídas diferentes em execuções diferentes?

Um HashSet não tem ordem fixa {:?} é aleatório Conjuntos perdem valores com o tempo Isso só acontece no modo debug

4. Qual coleção é a melhor para uma fila em que o primeiro a entrar é o primeiro a sair?

HashSet BTreeSet HashMap VecDeque

Pontuação: 0 / 4

Para saber mais

• Visão geral de std::collections — documentação da std (em inglês): um guia mais longo para escolher uma coleção, com a velocidade de cada operação.
• HashSet — Rust by Example (em inglês): um exemplo executável de union, intersection e difference.
• HashSet — documentação da std (em inglês): todos os métodos de conjunto, inclusive is_subset e retain.
• BTreeMap — documentação da std (em inglês): mapas ordenados, inclusive range para pegar uma faixa de chaves.
• VecDeque — documentação da std (em inglês): todos os métodos de fila, como push_front, pop_back e front.