Outras coleções

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 três delas: VecDeque, BTreeMap e HashSet. Cada uma possui propriedades únicas que as tornam ideais para determinados cenários.

Entender essas coleções amplia seu leque de ferramentas para escrever código mais eficiente e expressivo. Vamos mergulhar em cada uma com exemplos práticos.

VecDeque, BTreeMap, HashSet

VecDeque (Double-ended queue)

VecDeque é uma fila dupla, que permite inserções e remoções eficientes tanto no início quanto no final. Internamente, é implementada como um buffer circular, o que evita realocações frequentes. É ideal quando você precisa de uma fila (FIFO) ou uma pilha (LIFO) com acesso rápido a ambas as extremidades.

Exemplo de uso:

use std::collections::VecDeque;

fn main() {
    let mut deque: VecDeque<i32> = VecDeque::new();
    deque.push_back(1);
    deque.push_back(2);
    deque.push_front(0);
    println!("{:?}", deque); // [0, 1, 2]
    
    if let Some(front) = deque.pop_front() {
        println!("Removido do início: {}", front); // 0
    }
    if let Some(back) = deque.pop_back() {
        println!("Removido do final: {}", back); // 2
    }
}

BTreeMap

BTreeMap é um mapa ordenado baseado em uma árvore B. As chaves são armazenadas em ordem crescente (de acordo com a implementação de Ord). Isso permite iteração ordenada, além de operações de busca, inserção e remoção com complexidade O(log n). É útil quando você precisa de dados ordenados ou de intervalos de chaves.

Exemplo:

use std::collections::BTreeMap;

fn main() {
    let mut mapa = BTreeMap::new();
    mapa.insert("banana", 3);
    mapa.insert("maçã", 5);
    mapa.insert("abacaxi", 2);
    
    // Iteração em ordem alfabética
    for (fruta, qtd) in &mapa {
        println!("{}: {}", fruta, qtd);
    }
    // abacaxi: 2
    // banana: 3
    // maçã: 5
    
    // Intervalo: chaves entre "a" e "c"
    for (fruta, qtd) in mapa.range("a".."c") {
        println!("Intervalo: {}: {}", fruta, qtd);
    }
    // Intervalo: abacaxi: 2
    // Intervalo: banana: 3
}

HashSet

HashSet é um conjunto baseado em hash, similar ao HashMap mas sem valores associados. Ele armazena elementos únicos e oferece operações de conjunto como união, interseção e diferença. A ordem dos elementos não é garantida.

Exemplo:

use std::collections::HashSet;

fn main() {
    let mut set = HashSet::new();
    set.insert(1);
    set.insert(2);
    set.insert(2); // ignorado
    println!("{:?}", set); // {1, 2}
    
    if set.contains(&1) {
        println!("Contém 1");
    }
    
    let other: HashSet<i32> = [2, 3].iter().cloned().collect();
    let intersection: HashSet<_> = set.intersection(&other).cloned().collect();
    println!("Interseção: {:?}", intersection); // {2}
}

Quando usar cada uma

A escolha da coleção depende das operações que você pretende realizar com mais frequência. Aqui estão diretrizes práticas:

• VecDeque: Use quando precisar de uma fila ou pilha com inserções/remoções frequentes em ambas as extremidades. Exemplo: processamento de tarefas em ordem FIFO ou LIFO.
• BTreeMap: Use quando precisar de dados ordenados por chave ou realizar consultas por intervalo. Exemplo: índice de palavras em um dicionário.
• HashSet: Use quando precisar armazenar elementos únicos e realizar operações de conjunto (união, interseção, diferença) ou verificar pertinência rapidamente. Exemplo: lista de palavras proibidas.

Considere também o custo de cada operação: VecDeque tem O(1) para push/pop nas extremidades; BTreeMap tem O(log n) para inserção, busca e remoção; HashSet tem O(1) médio para inserção e busca, mas sem ordem garantida.

Visão geral

A biblioteca padrão do Rust oferece várias coleções além das vistas aqui. A tabela abaixo resume as principais:

Cada coleção tem seus trade-offs. A escolha correta pode impactar significativamente o desempenho e a legibilidade do código. Sempre prefira a coleção que oferece as operações de que você precisa com a menor complexidade possível.

Boas práticas

• Use Vec como padrão para listas; só use VecDeque se precisar de inserções no início.
• Para mapas, prefira HashMap a menos que precise de ordenação ou intervalos.
• Para conjuntos, prefira HashSet a menos que precise de ordenação.
• Considere usar BTreeSet como alternativa ordenada ao HashSet.
• Evite LinkedList a menos que tenha um motivo muito específico, pois tem má localidade de cache e overhead.

Referências

• Documentação oficial do VecDeque
• Documentação oficial do BTreeMap
• Documentação oficial do HashSet
• The Rust Programming Language - Capítulo 8: Coleções
• Módulo std::collections
• Too Many Lists - Aprendendo sobre listas em Rust

Exercícios

1. Crie um programa que leia uma string e use um VecDeque para verificar se ela é um palíndromo (ignorando espaços e maiúsculas). Dica: insira os caracteres no final e compare com os removidos do início e do final.

   Ver resposta

   ✓ Resposta:

   use std::collections::VecDeque;
   
   fn eh_palindromo(s: &str) -> bool {
       let mut deque = VecDeque::new();
       for ch in s.chars().filter(|c| !c.is_whitespace()).map(|c| c.to_ascii_lowercase()) {
           deque.push_back(ch);
       }
       while deque.len() > 1 {
           if deque.pop_front() != deque.pop_back() {
               return false;
           }
       }
       true
   }
   
   fn main() {
       let texto = "A man a plan a canal Panama";
       println!("{}", eh_palindromo(texto)); // true
   }

2. Use um BTreeMap para contar a frequência de palavras em uma frase e exibir as palavras em ordem alfabética.

   Ver resposta

   ✓ Resposta:

   use std::collections::BTreeMap;
   
   fn main() {
       let frase = "o rato roeu a roupa do rei de roma";
       let mut contagem = BTreeMap::new();
       for palavra in frase.split_whitespace() {
           *contagem.entry(palavra).or_insert(0) += 1;
       }
       for (palavra, qtd) in &contagem {
           println!("{}: {}", palavra, qtd);
       }
   }

3. Dados dois vetores de números, use HashSet para encontrar os números que aparecem em ambos (interseção) e os que aparecem apenas no primeiro (diferença).

   Ver resposta

   ✓ Resposta:

   use std::collections::HashSet;
   
   fn main() {
       let v1 = vec![1, 2, 3, 4, 5];
       let v2 = vec![4, 5, 6, 7];
       let set1: HashSet<_> = v1.into_iter().collect();
       let set2: HashSet<_> = v2.into_iter().collect();
       
       let intersecao: HashSet<_> = set1.intersection(&set2).cloned().collect();
       let diferenca: HashSet<_> = set1.difference(&set2).cloned().collect();
       
       println!("Interseção: {:?}", intersecao); // {4, 5}
       println!("Diferença (set1 - set2): {:?}", diferenca); // {1, 2, 3}
   }

4. Implemente uma fila de tarefas usando VecDeque onde cada tarefa é uma string. Adicione tarefas no final e processe removendo do início. Mostre o estado da fila após cada operação.

   Ver resposta

   ✓ Resposta:

   use std::collections::VecDeque;
   
   fn main() {
       let mut fila: VecDeque<String> = VecDeque::new();
       fila.push_back("Tarefa 1".to_string());
       fila.push_back("Tarefa 2".to_string());
       fila.push_back("Tarefa 3".to_string());
       println!("Fila inicial: {:?}", fila);
       
       while let Some(tarefa) = fila.pop_front() {
           println!("Processando: {}", tarefa);
           println!("Fila restante: {:?}", fila);
       }
   }

5. Use BTreeMap para armazenar notas de alunos (nome -> nota). Depois, exiba os alunos com nota acima de 7 em ordem alfabética.

   Ver resposta

   ✓ Resposta:

   use std::collections::BTreeMap;
   
   fn main() {
       let mut notas = BTreeMap::new();
       notas.insert("Ana", 8.5);
       notas.insert("Beto", 6.0);
       notas.insert("Carla", 9.0);
       notas.insert("Davi", 7.5);
       
       for (nome, nota) in notas.iter().filter(|(_, &n)| n > 7.0) {
           println!("{}: {}", nome, nota);
       }
   }