Visao Geral de std::collections em Rust

Visao Geral do Modulo std::collections

O modulo std::collections fornece as estruturas de dados da biblioteca padrao do Rust. Cada colecao e otimizada para um conjunto especifico de operacoes, e escolher a correta pode significar a diferenca entre codigo rapido e codigo lento.

Rust oferece quatro categorias de colecoes:

Sequencias — Vec, VecDeque, LinkedList
Mapas — HashMap, BTreeMap
Conjuntos — HashSet, BTreeSet
Filas de prioridade — BinaryHeap

Este guia funciona como um guia de decisao: dado seu problema, qual colecao escolher?

Tabela de Complexidade (Big-O)

Sequencias

Operacao	`Vec<T>`	`VecDeque<T>`	`LinkedList<T>`
Acessar por indice	O(1)	O(1)	O(n)
Push no final	O(1)*	O(1)*	O(1)
Push no inicio	O(n)	O(1)*	O(1)
Pop do final	O(1)	O(1)	O(1)
Pop do inicio	O(n)	O(1)	O(1)
Inserir no meio	O(n)	O(n)	O(1) **
Remover no meio	O(n)	O(n)	O(1) **
Buscar	O(n)	O(n)	O(n)
Localidade de cache	Excelente	Boa	Ruim

* Amortizado. ** Com cursor ja posicionado.

Mapas e Conjuntos

Operacao	`HashMap`/`HashSet`	`BTreeMap`/`BTreeSet`
Inserir	O(1)*	O(log n)
Remover	O(1)*	O(log n)
Buscar	O(1)*	O(log n)
Iterar ordenado	O(n log n)	O(n)
Range query	N/A	O(log n + k)
Menor/Maior	O(n)	O(log n)

* Amortizado, caso medio. Pior caso O(n) com colisoes.

Fila de Prioridade

Operacao	`BinaryHeap<T>`
Push	O(log n)
Pop (maior)	O(log n)
Peek (maior)	O(1)
Buscar	O(n)

Fluxograma: Qual Colecao Usar?

Responda as perguntas abaixo para escolher a colecao ideal:

1. Voce precisa de pares chave-valor?

Sim -> Precisa de ordenacao? -> Sim: BTreeMap | Nao: HashMap
Nao -> Prossiga para 2

2. Voce precisa apenas de valores unicos (conjunto)?

Sim -> Precisa de ordenacao? -> Sim: BTreeSet | Nao: HashSet
Nao -> Prossiga para 3

3. Voce precisa de acesso por indice?

Sim -> Vec (ou VecDeque se inserir/remover no inicio)
Nao -> Prossiga para 4

4. Voce insere/remove frequentemente em ambas as pontas?

Sim -> VecDeque
Nao -> Prossiga para 5

5. Voce sempre precisa do maior (ou menor) elemento?

Sim -> BinaryHeap
Nao -> Use Vec (a colecao padrao)

Regra de ouro: Na duvida, comece com Vec ou HashMap. Eles sao as colecoes mais usadas e raramente sao a escolha errada.

Exemplos Praticos

1. Vec — A Colecao Padrao

fn main() {
    let mut numeros = Vec::new();
    numeros.push(3);
    numeros.push(1);
    numeros.push(4);
    numeros.push(1);
    numeros.push(5);

    // Acesso por indice: O(1)
    println!("Terceiro: {}", numeros[2]); // 4

    // Ordenacao
    numeros.sort();
    println!("Ordenado: {numeros:?}"); // [1, 1, 3, 4, 5]

    // Deduplicar (requer ordenacao previa)
    numeros.dedup();
    println!("Unico: {numeros:?}"); // [1, 3, 4, 5]

    // Filtrar e coletar
    let pares: Vec<_> = numeros.iter().filter(|&&n| n % 2 == 0).collect();
    println!("Pares: {pares:?}"); // [4]

    // Prealoque para performance
    let mut grande = Vec::with_capacity(10_000);
    for i in 0..10_000 {
        grande.push(i);
    }
    println!("Capacidade final: {}", grande.capacity()); // >= 10_000
}

2. HashMap vs BTreeMap

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

fn main() {
    // HashMap: rapido, sem ordem
    let mut hash: HashMap<&str, i32> = HashMap::new();
    hash.insert("banana", 3);
    hash.insert("maca", 5);
    hash.insert("laranja", 2);
    hash.insert("abacaxi", 1);

    println!("HashMap (sem ordem):");
    for (fruta, qtd) in &hash {
        println!("  {fruta}: {qtd}");
    }

    // BTreeMap: mais lento, mas ordenado por chave
    let mut btree: BTreeMap<&str, i32> = BTreeMap::new();
    btree.insert("banana", 3);
    btree.insert("maca", 5);
    btree.insert("laranja", 2);
    btree.insert("abacaxi", 1);

    println!("\nBTreeMap (ordenado):");
    for (fruta, qtd) in &btree {
        println!("  {fruta}: {qtd}");
    }
    // abacaxi, banana, laranja, maca (ordem alfabetica)

    // BTreeMap suporta range queries
    println!("\nFrutas de 'b' a 'l':");
    for (fruta, qtd) in btree.range("b"..="l") {
        println!("  {fruta}: {qtd}");
    }

    // BTreeMap: menor e maior chave
    println!("\nPrimeiro: {:?}", btree.iter().next());
    println!("Ultimo: {:?}", btree.iter().next_back());
}

3. VecDeque — Fila de Duas Pontas

use std::collections::VecDeque;

fn main() {
    let mut fila: VecDeque<String> = VecDeque::new();

    // Inserir no final (como Vec)
    fila.push_back("primeiro".into());
    fila.push_back("segundo".into());
    fila.push_back("terceiro".into());

    // Inserir no inicio: O(1)!
    fila.push_front("zero".into());

    println!("Fila: {fila:?}");
    // ["zero", "primeiro", "segundo", "terceiro"]

    // Remover do inicio (FIFO): O(1)
    while let Some(item) = fila.pop_front() {
        println!("Processando: {item}");
    }

    // Usar como buffer circular
    let mut buffer: VecDeque<i32> = VecDeque::with_capacity(3);
    for i in 0..10 {
        if buffer.len() == 3 {
            buffer.pop_front(); // Remove o mais antigo
        }
        buffer.push_back(i);
        println!("Buffer: {buffer:?}");
    }
    // Ultimos 3 valores: [7, 8, 9]
}

4. HashSet e BTreeSet — Conjuntos

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

fn main() {
    let mut frutas: HashSet<&str> = HashSet::new();
    frutas.insert("maca");
    frutas.insert("banana");
    frutas.insert("maca"); // Duplicata ignorada
    println!("Frutas: {frutas:?} (tamanho: {})", frutas.len()); // 2

    // Verificar pertinencia: O(1)
    println!("Tem maca? {}", frutas.contains("maca")); // true

    // Operacoes de conjunto
    let tropicais: HashSet<&str> = ["banana", "manga", "abacaxi"].into();
    let brasileiras: HashSet<&str> = ["banana", "acerola", "caju"].into();

    let uniao: HashSet<_> = tropicais.union(&brasileiras).collect();
    let intersecao: HashSet<_> = tropicais.intersection(&brasileiras).collect();
    let diferenca: HashSet<_> = tropicais.difference(&brasileiras).collect();

    println!("Uniao: {uniao:?}");
    println!("Intersecao: {intersecao:?}");
    println!("Diferenca (tropicais - brasileiras): {diferenca:?}");

    // BTreeSet: ordenado
    let numeros: BTreeSet<i32> = [5, 3, 8, 1, 9, 2].into();
    println!("\nBTreeSet ordenado: {numeros:?}"); // {1, 2, 3, 5, 8, 9}

    // Range query em BTreeSet
    let entre_3_e_8: Vec<_> = numeros.range(3..=8).collect();
    println!("Entre 3 e 8: {entre_3_e_8:?}"); // [3, 5, 8]
}

5. BinaryHeap — Fila de Prioridade

use std::collections::BinaryHeap;
use std::cmp::Reverse;

#[derive(Debug, Eq, PartialEq)]
struct Tarefa {
    prioridade: u32,
    descricao: String,
}

impl Ord for Tarefa {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.prioridade.cmp(&other.prioridade)
    }
}

impl PartialOrd for Tarefa {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

fn main() {
    // Max-heap (maior primeiro)
    let mut heap = BinaryHeap::new();
    heap.push(3);
    heap.push(1);
    heap.push(5);
    heap.push(2);

    println!("Maior: {:?}", heap.peek()); // Some(5)

    // Remover em ordem decrescente
    print!("Em ordem: ");
    while let Some(val) = heap.pop() {
        print!("{val} ");
    }
    println!(); // 5 3 2 1

    // Min-heap usando Reverse
    let mut min_heap = BinaryHeap::new();
    min_heap.push(Reverse(3));
    min_heap.push(Reverse(1));
    min_heap.push(Reverse(5));

    println!("Menor: {:?}", min_heap.peek()); // Some(Reverse(1))

    // Fila de prioridade com struct customizada
    let mut tarefas = BinaryHeap::new();
    tarefas.push(Tarefa { prioridade: 2, descricao: "Revisar codigo".into() });
    tarefas.push(Tarefa { prioridade: 5, descricao: "Corrigir bug critico".into() });
    tarefas.push(Tarefa { prioridade: 1, descricao: "Atualizar docs".into() });

    println!("\nOrdem de execucao:");
    while let Some(tarefa) = tarefas.pop() {
        println!("  [P{}] {}", tarefa.prioridade, tarefa.descricao);
    }
}

Tabela Comparativa de Decisao

Necessidade	Colecao Recomendada	Motivo
Lista ordenavel, acesso por indice	`Vec`	Cache-friendly, versatil
Fila FIFO	`VecDeque`	O(1) em ambas as pontas
Busca por chave rapida	`HashMap`	O(1) amortizado
Mapa ordenado, range queries	`BTreeMap`	Iteracao ordenada, range O(log n)
Eliminar duplicatas	`HashSet`	O(1) para contains
Conjunto ordenado	`BTreeSet`	Menor/maior em O(log n)
Sempre o maior/menor primeiro	`BinaryHeap`	O(log n) push/pop
Lista com insercao no meio	`Vec` (com splice)	LinkedList raramente e melhor

Padroes Comuns

Entry API para HashMap/BTreeMap

use std::collections::HashMap;

fn main() {
    let mut contagem: HashMap<&str, u32> = HashMap::new();
    let palavras = ["rust", "e", "rapido", "rust", "e", "seguro"];

    for palavra in palavras {
        *contagem.entry(palavra).or_insert(0) += 1;
    }
    println!("{contagem:?}");
}

Escolhendo Capacidade Inicial

Pre-alocar evita realocacoes:

use std::collections::HashMap;

fn main() {
    // Se voce sabe o tamanho aproximado, pre-aloque
    let mut mapa = HashMap::with_capacity(1000);
    for i in 0..1000 {
        mapa.insert(i, i * 2);
    }
}

Quando Usar (e Quando Nao Usar)

Use Vec para quase tudo. E a colecao mais rapida para a maioria dos casos gracas a localidade de cache.

Use HashMap quando precisar buscar por chave e nao se importar com ordem.

Use BTreeMap quando precisar de ordenacao ou range queries.

Evite LinkedList — em Rust moderno, Vec e VecDeque sao quase sempre mais rapidos gracas a localidade de cache, mesmo para insercoes no meio.

Dica de performance: O hashing padrao do HashMap (SipHash) e resistente a ataques DoS, mas nao e o mais rapido. Para dados nao-adversariais, considere crates como rustc-hash ou ahash para performance maxima.

Veja Tambem

Vec<T>: Vetor Dinamico — aprofundamento em Vec
HashMap<K, V> — aprofundamento em HashMap
BTreeMap<K, V> — aprofundamento em BTreeMap
Iterator Trait — como iterar sobre colecoes
Modulo std::fmt — como exibir colecoes com Debug/Display
Documentacao oficial — std::collections