Além das coleções mais comuns como Vec, HashMap e String, a biblioteca padrão do Rust oferece outras estruturas de dados que atendem a necessidades específicas de desempenho e ordenação. Nesta aula, exploraremos VecDeque, BTreeMap e HashSet, entendendo suas particularidades, vantagens e cenários ideais de uso.

Dominar essas coleções permite escrever código mais eficiente e expressivo, escolhendo a ferramenta certa para cada problema. Vamos mergulhar em cada uma delas com exemplos práticos.

VecDeque

VecDeque é uma fila dupla (double-ended queue) que permite inserções e remoções eficientes tanto no início quanto no final. Diferente de Vec, que só é eficiente para operações no final, VecDeque oferece desempenho O(1) para operações em ambas as extremidades.

Internamente, VecDeque usa um buffer circular, o que evita realocações frequentes quando se adiciona ou remove elementos no início. É ideal para implementar filas (FIFO) ou pilhas (LIFO) quando ambas as extremidades são acessadas.

use std::collections::VecDeque;

fn main() {
    let mut fila = VecDeque::new();
    fila.push_back(1);
    fila.push_back(2);
    fila.push_front(0);
    println!("{:?}", fila); // [0, 1, 2]

    if let Some(primeiro) = fila.pop_front() {
        println!("Removido do início: {}", primeiro); // 0
    }
    if let Some(ultimo) = fila.pop_back() {
        println!("Removido do final: {}", ultimo); // 2
    }
}

O método push_front insere no início, push_back no final. pop_front e pop_back removem e retornam o elemento correspondente. Também é possível acessar por índice (fila[1]), mas lembre-se que isso é uma operação O(1) apenas para acesso, não para inserção no meio.

BTreeMap

BTreeMap é um mapa ordenado baseado em uma árvore B. Assim como HashMap, ele mapeia chaves a valores, mas mantém as chaves ordenadas (de acordo com a trait Ord). Isso permite iteração em ordem crescente, além de operações de intervalo (range) eficientes.

Enquanto HashMap oferece operações O(1) em média, BTreeMap tem complexidade O(log n) para inserção, remoção e busca. A escolha entre eles depende da necessidade de ordenação: se você precisa iterar as chaves em ordem ou fazer consultas por faixa, BTreeMap é a escolha certa.

use std::collections::BTreeMap;

fn main() {
    let mut mapa = BTreeMap::new();
    mapa.insert(3, "três");
    mapa.insert(1, "um");
    mapa.insert(2, "dois");

    // Iteração em ordem crescente das chaves
    for (chave, valor) in &mapa {
        println!("{}: {}", chave, valor);
    }
    // Saída:
    // 1: um
    // 2: dois
    // 3: três

    // Consulta de intervalo: chaves entre 1 e 2 (inclusive)
    for (chave, valor) in mapa.range(1..=2) {
        println!("Intervalo: {}: {}", chave, valor);
    }
}

O método range aceita um intervalo do tipo RangeBounds, permitindo consultas parciais. Isso é útil para, por exemplo, obter todos os registros com chave entre dois valores.

HashSet

HashSet é um conjunto (set) baseado em hash, similar ao HashSet de outras linguagens. Ele armazena valores únicos e oferece operações eficientes de inserção, remoção e verificação de pertinência (O(1) em média).

É ideal quando você precisa garantir que não haja duplicatas ou realizar operações de conjunto como união, interseção e diferença. HashSet não garante ordem de iteração; para conjuntos ordenados, existe BTreeSet (similar ao BTreeMap mas só com chaves).

use std::collections::HashSet;

fn main() {
    let mut conjunto = HashSet::new();
    conjunto.insert(1);
    conjunto.insert(2);
    conjunto.insert(3);
    conjunto.insert(2); // ignorado, pois 2 já existe

    println!("Tamanho: {}", conjunto.len()); // 3
    println!("Contém 2? {}", conjunto.contains(&2)); // true

    // Operações de conjunto
    let outros: HashSet = [2, 3, 4].iter().cloned().collect();
    let uniao: HashSet<_> = conjunto.union(&outros).cloned().collect();
    let intersecao: HashSet<_> = conjunto.intersection(&outros).cloned().collect();
    let diferenca: HashSet<_> = conjunto.difference(&outros).cloned().collect();

    println!("União: {:?}", uniao); // {1, 2, 3, 4}
    println!("Interseção: {:?}", intersecao); // {2, 3}
    println!("Diferença: {:?}", diferenca); // {1}
}

Os métodos union, intersection, difference e symmetric_difference retornam iteradores, que podem ser coletados em um novo HashSet ou usados diretamente.

Quando usar cada uma

A escolha da coleção correta depende dos requisitos de desempenho e funcionalidade:

  • VecDeque: Use quando precisar de uma fila ou pilha com operações eficientes em ambas as extremidades. Exemplos: fila de tarefas, buffer circular, histórico de navegação (últimas páginas).
  • BTreeMap: Use quando precisar de um mapa ordenado ou consultas por intervalo. Exemplos: índice de banco de dados em memória, agenda com datas ordenadas, dicionário com prefixos.
  • HashSet: Use quando precisar armazenar valores únicos sem ordem específica e realizar operações de conjunto rapidamente. Exemplos: verificar duplicatas, permissões de acesso, conjunto de IDs processados.

Em geral, se a ordenação não é necessária, HashMap e HashSet são mais rápidos. Se a ordenação é importante, BTreeMap e BTreeSet são as opções. VecDeque é especializado para acesso nas pontas.

Visão geral

Além das coleções vistas, Rust oferece outras como LinkedList (lista duplamente encadeada), BinaryHeap (fila de prioridade) e BTreeSet (conjunto ordenado). Cada uma tem seu lugar, mas as apresentadas aqui são as mais comuns para tarefas do dia a dia.

Todas as coleções em Rust são genéricas e seguem as mesmas traits (Eq, Hash, Ord, etc.), facilitando a troca entre elas quando necessário. Sempre consulte a documentação oficial para detalhes de API e desempenho.

Boas práticas

  • Prefira VecDeque a Vec quando fizer muitas inserções/remoções no início.
  • Use BTreeMap quando precisar de iteração ordenada ou intervalos; caso contrário, HashMap é mais rápido.
  • Para conjuntos, HashSet é a escolha padrão; use BTreeSet apenas se precisar de ordem.
  • Evite LinkedList na maioria dos casos; Vec ou VecDeque são mais eficientes devido à localidade de cache.

Referências

Exercícios

  1. Crie um programa que use VecDeque para implementar uma fila de impressão. Adicione três documentos (strings) e depois remova e imprima cada um na ordem FIFO.

    ✓ Resposta:
    use std::collections::VecDeque;

fn main() {
    let mut fila = VecDeque::new();
    fila.push_back("Documento1");
    fila.push_back("Documento2");
    fila.push_back("Documento3");

    while let Some(doc) = fila.pop_front() {
        println!("Imprimindo: {}", doc);
    }
}

  2. Escreva um programa que use BTreeMap para armazenar nomes de alunos e suas notas. Insira 5 alunos com notas, depois imprima-os em ordem alfabética. Em seguida, imprima apenas os alunos com nota entre 7.0 e 10.0.

    ✓ Resposta:
    use std::collections::BTreeMap;

fn main() {
    let mut notas = BTreeMap::new();
    notas.insert("Ana", 8.5);
    notas.insert("Bruno", 6.0);
    notas.insert("Carla", 9.0);
    notas.insert("Daniel", 7.5);
    notas.insert("Eduarda", 5.5);

    println!("Todos os alunos em ordem:");
    for (nome, nota) in ¬as {
        println!("{}: {}", nome, nota);
    }

    println!("\nAlunos com nota entre 7.0 e 10.0:");
    for (nome, nota) in notas.range("A"..) {
        if *nota >= 7.0 && *nota <= 10.0 {
            println!("{}: {}", nome, nota);
        }
    }
}

  3. Use HashSet para encontrar os elementos comuns entre dois vetores de números inteiros: [1, 2, 3, 4, 5] e [4, 5, 6, 7, 8]. Imprima o conjunto resultante.

    ✓ Resposta:
    use std::collections::HashSet;

fn main() {
    let a: HashSet = [1, 2, 3, 4, 5].iter().cloned().collect();
    let b: HashSet = [4, 5, 6, 7, 8].iter().cloned().collect();
    let intersecao: HashSet<_> = a.intersection(&b).cloned().collect();
    println!("Elementos comuns: {:?}", intersecao);
}

  4. Implemente uma função que receba uma string e retorne um BTreeMap com a contagem de cada caractere (ignorando espaços). Teste com a frase "hello world".

    ✓ Resposta:
    use std::collections::BTreeMap;

fn contagem_caracteres(s: &str) -> BTreeMap {
    let mut contagem = BTreeMap::new();
    for c in s.chars().filter(|c| !c.is_whitespace()) {
        *contagem.entry(c).or_insert(0) += 1;
    }
    contagem
}

fn main() {
    let resultado = contagem_caracteres("hello world");
    for (c, n) in &resultado {
        println!("'{}': {}", c, n);
    }
}

  5. Crie um programa que use VecDeque como uma pilha (LIFO). Empilhe os números 10, 20 e 30, depois desempilhe e imprima cada um.

    ✓ Resposta:
    use std::collections::VecDeque;

fn main() {
    let mut pilha = VecDeque::new();
    pilha.push_back(10);
    pilha.push_back(20);
    pilha.push_back(30);

    while let Some(valor) = pilha.pop_back() {
        println!("Desempilhado: {}", valor);
    }
}