Capítulo 12: Coleções Padrão (Vec, HashMap, HashSet) e Iteradores Idiomáticos

Especialização em Sistemas com Rust • Rust 2021 Edition • Ownership, Concorrência Segura e Sistemas de Alta Performance

🗺️ Mapa Conceitual de Coleções da Biblioteca Padrão e Pipelines de Iteradores

flowchart TD
    Origem["Coleções em Memória (Vec, HashMap, HashSet)"] --> Adaptadores["Criação do Iterador (.iter() / .iter_mut() / .into_iter())"]

    subgraph PIPELINE_COMBINADORES["Combinadores Funcionais Preguiçosos (Lazy Evaluation)"]
        Filtro[".filter(|x| ...): Filtra elementos"]
        Mapeamento[".map(|x| ...): Transforma valores"]
        Achatamento[".flatten() / .flat_map(): Desaninha coleções"]
        TakeDrop[".take(n) / .skip(n): Janelamento de dados"]
    end

    Adaptadores --> PIPELINE_COMBINADORES

    subgraph CONSUMIDORES_FINAIS["Métodos Consumidores (Terminal Operations)"]
        Collect[".collect(): Materializa em nova Coleção"]
        Fold[".fold(0, |acc, x| ...): Redução Acumuladora"]
        SumCount[".sum() / .count() / .any() / .all()"]
    end

    PIPELINE_COMBINADORES --> CONSUMIDORES_FINAIS
    CONSUMIDORES_FINAIS --> AssemblyOtimizado["Compilação em Assembly Vetorizado (SIMD / Zero-Cost Abstraction)"]

    style Origem fill:#e1f5fe,stroke:#03a9f4,stroke-width:2px
    style Adaptadores fill:#fff3e0,stroke:#ff9800,stroke-width:2px
    style PIPELINE_COMBINADORES fill:#ede7f6,stroke:#7e57c2,stroke-width:2px
    style CONSUMIDORES_FINAIS fill:#e8f5e9,stroke:#4caf50,stroke-width:2px
    style AssemblyOtimizado fill:#c8e6c9,stroke:#2e7d32,stroke-width:2px

🏛️ 1. O Modelo de Coleções da Biblioteca Padrão (`std::collections`)

O Rust disponibiliza uma suíte balanceada de estruturas de dados contíguas e associativas, desenhadas para garantir máxima eficiência de CPU, alocação determinística na Heap e segurança contra violações de tipos:

Sequenciais Contíguas: Vec<T> (Vetor dinâmico contíguo na Heap) e VecDeque<T> (Fila de ponta dupla baseada em buffer circular).
Associativas Baseadas em Hash: HashMap<K, V> e HashSet<T> (Implementação baseada no algoritmo SwissTable do Google, garantindo velocidade brutal de lookup com SipHash resistente a ataques DoS de colisão de hash).
Ordenadas Baseadas em Árvore: BTreeMap<K, V> e BTreeSet<T> (Baseadas em Árvores B otimizadas para cache lines de hardware, mantendo os elementos sempre ordenados com busca $O(\log n)$).

⚙️ 2. A API de Entrada Elegante: O Padrão `Entry API`

Em linguagens como Java ou C++, atualizar um mapa baseado na existência prévia de uma chave geralmente exige duas buscas separadas (contains_key seguida de get/put).

No Rust, a Entry API do HashMap realiza a busca uma única vez e retorna um tipo que permite mutação atômica in-place:

use std::collections::HashMap;

let transacoes = vec!["pix", "boleto", "pix", "cartao", "pix", "boleto"];
let mut estatisticas = HashMap::new();

for metodo in transacoes {
    // .entry(chave).or_insert(0):
    // Se a chave existe, retorna &mut contador. Se não existe, insere 0 e retorna &mut contador.
    let contador = estatisticas.entry(metodo).or_insert(0);
    *contador += 1;
}

// estatisticas = {"pix": 3, "boleto": 2, "cartao": 1}

🔄 3. A Trait `Iterator` e os 3 Tipos de Iteração

No Rust, um iterador é qualquer tipo que implementa a trait std::iter::Iterator:

pub trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
}

Ao iterar sobre uma coleção, você deve escolher conscientemente qual nível de acesso deseja:

.iter(): Itera sobre referências imutáveis (&T). A coleção original permanece intacta e pode ser lida novamente.
.iter_mut(): Itera sobre referências mutáveis (&mut T). Permite alterar os valores diretamente dentro da coleção original.
.into_iter(): Consume a coleção (takes ownership), iterando sobre os valores por posse (T). A coleção original deixa de existir!

⚡ 4. Combinadores Funcionais e Avaliação Preguiçosa (Lazy)

Os combinadores de iteradores (map, filter, fold, take) são estritamente preguiçosos (lazy): nenhum cálculo é realizado enquanto você apenas os encadeia. O processamento só acontece quando um método consumidor terminal (como .collect() ou .sum()) for executado:

let metricas = vec![12, 45, 98, 120, 23, 75, 210];

// Pipeline de processamento declarativo
let media_critica: f64 = {
    let valores_criticos: Vec<f64> = metricas
        .iter()
        .filter(|&&x| x > 50)             // Mantém apenas > 50
        .map(|&x| x as f64 * 1.15)        // Aplica fator de correção
        .collect();                       // Coleta no novo vetor

    let soma: f64 = valores_criticos.iter().sum();
    soma / valores_criticos.len() as f64
};

println!("Média ponderada dos picos críticos: {:.2}", media_critica);

🚀 5. Abstrações de Custo Zero (Zero-Cost Abstractions)

Uma das afirmações mais famosas de Bjarne Stroustrup, adotada como pilar pelo Rust, é a garantia de abstração com custo zero:

“O que você não usa, você não paga. E o que você usa, você não conseguiria escrever manualmente de forma mais eficiente.”

Ao compilar pipelines de iteradores, o otimizador LLVM do rustc:

Desfaz as chamadas de funções e faz inlining completo de todas as closures.
Elimina todas as estruturas intermediárias do iterador.
Transforma o pipeline em loops assembly com vetorização SIMD (instruções AVX2/AVX-512 que processam 4 a 8 inteiros por ciclo de clock da CPU). O resultado é um código declarativo e legível que roda com a mesma performance ou até mais rápido que loops C brutos indexados manualmente.

⚖️ 6. Matriz de Escolha: `HashMap` vs `BTreeMap`

Critério	`std::collections::HashMap`	`std::collections::BTreeMap`
Complexidade Média de Busca	$O(1)$ amortizado	$O(\log n)$ determinístico
Ordem dos Elementos	Aleatória (determinada pelo hasher)	Sempre Ordenada pelo `Ord` da Chave
Consumo de Memória	Médio (tabela com fator de carga)	Otimizado para Cache Lines de CPU
Operações de Range	Ineficiente (varredura completa)	Nativo e instantâneo (`.range("A"..="Z")`)
Requisito de Trait	`Eq + Hash`	`Ord`

⚠️ 7. Armadilhas Comuns e Mensagens do Compilador

Mutar Coleção Durante Iteração (E0502):
```
for item in &mut vetor {
    vetor.push(10); // ERRO: cannot borrow `vetor` as mutable more than once
}
```
Explicação: Adicionar itens pode forçar o vetor a realocar a memória Heap, o que invalidaria o ponteiro do iterador atual. O compilador previne esse bug catastrófico.
Esquecer o Método Consumidor Terminal: Escrever vetor.iter().map(...) sem chamar .collect() ou .for_each() resultará em um aviso do compilador: warning: unused Map that must be used. Como iteradores são preguiçosos, nada será executado!

🛡️ 8. Boas Práticas Corporativas

Defina Capacidade Inicial em Mapas Grandes: Assim como no Vec, utilize HashMap::with_capacity(esperado) quando for inserir milhares de registros conhecidos, evitando recalcular hashes e rehashing da tabela em runtime.

📋 9. Cheat-Sheet: Resumo Executivo

// HashMap Entry API
map.entry("chave").or_insert(100);

// Iteradores
let soma: i32 = lista.iter().filter(|&&x| x > 0).sum();
let dobrados: Vec<i32> = lista.into_iter().map(|x| x * 2).collect();