BTreeSet em Rust: Guia da Stdlib | Rust Brasil

O BTreeSet<T> é a implementação de conjunto ordenado da biblioteca padrão do Rust. Ele armazena elementos únicos e os mantém sempre em ordem crescente. Internamente, é construído sobre um BTreeMap<T, ()>, herdando a eficiência da árvore B com complexidade O(log n) para as operações principais.

Quando Usar BTreeSet

Use BTreeSet quando:

Precisa de um conjunto de elementos únicos com iteração em ordem.
Deseja realizar consultas por faixa (range) — por exemplo, “todos os números entre 10 e 50”.
Precisa acessar o menor ou maior elemento rapidamente.
O tipo dos elementos implementa Ord mas não Hash.

Se a ordem não importa e você quer busca O(1), use HashSet.

Criando e Inicializando

use std::collections::BTreeSet;

fn main() {
    // Criar vazio
    let mut numeros: BTreeSet<i32> = BTreeSet::new();

    // Criar a partir de um array
    let vogais = BTreeSet::from(['a', 'e', 'i', 'o', 'u']);

    // Criar a partir de um vetor com collect (remove duplicatas e ordena!)
    let dados = vec![5, 3, 8, 1, 3, 5, 9, 1, 7];
    let ordenados: BTreeSet<i32> = dados.into_iter().collect();
    println!("{:?}", ordenados); // {1, 3, 5, 7, 8, 9}

    // Criar a partir de caracteres de uma string
    let texto = "abracadabra";
    let letras: BTreeSet<char> = texto.chars().collect();
    println!("{:?}", letras); // {'a', 'b', 'c', 'd', 'r'}
}

Tabela de Métodos Comuns

Método	Descrição	Complexidade
`insert(value)`	Insere elemento; retorna `true` se era novo	O(log n)
`remove(&value)`	Remove elemento; retorna `true` se existia	O(log n)
`contains(&value)`	Verifica se o elemento existe	O(log n)
`len()` / `is_empty()`	Tamanho e verificação de vazio	O(1)
`iter()`	Iterador sobre `&T` em ordem crescente	O(n)
`range(range)`	Iterador sobre um intervalo	O(log n + k)
`first()` / `last()`	Menor/maior elemento	O(log n)
`pop_first()` / `pop_last()`	Remove e retorna menor/maior	O(log n)
`union(&other)`	Elementos em `self` OU `other` (em ordem)	O(n + m)
`intersection(&other)`	Elementos em `self` E `other`	O(n + m)
`difference(&other)`	Elementos em `self` mas NÃO em `other`	O(n + m)
`symmetric_difference(&other)`	Em um OU outro, mas não ambos	O(n + m)
`is_subset(&other)`	Verifica se `self` ⊆ `other`	O(n + m)
`is_superset(&other)`	Verifica se `self` ⊇ `other`	O(n + m)
`is_disjoint(&other)`	Verifica se não há elementos em comum	O(n + m)
`split_off(&value)`	Divide o conjunto em dois	O(n)
`retain(f)`	Mantém elementos onde `f` retorna `true`	O(n)

Exemplos Práticos

1. Inserção, Busca e Iteração Ordenada

use std::collections::BTreeSet;

fn main() {
    let mut alunos: BTreeSet<String> = BTreeSet::new();

    alunos.insert("Zara".to_string());
    alunos.insert("Ana".to_string());
    alunos.insert("Miguel".to_string());
    alunos.insert("Bruno".to_string());
    alunos.insert("Ana".to_string()); // duplicata, ignorada

    println!("Total: {} alunos", alunos.len()); // 4

    // Iteração é sempre em ordem alfabética
    println!("Lista de chamada:");
    for (i, aluno) in alunos.iter().enumerate() {
        println!("  {}. {}", i + 1, aluno);
    }
    // 1. Ana
    // 2. Bruno
    // 3. Miguel
    // 4. Zara

    // Verificação de pertinência
    println!("Ana matriculada? {}", alunos.contains("Ana")); // true

    // Primeiro e último
    println!("Primeiro: {:?}", alunos.first()); // Some("Ana")
    println!("Último: {:?}", alunos.last());    // Some("Zara")
}

2. Range Queries — Consultas por Faixa

use std::collections::BTreeSet;

fn main() {
    let mut portas: BTreeSet<u16> = BTreeSet::new();

    // Portas de serviços conhecidos
    for porta in [22, 53, 80, 443, 993, 3306, 5432, 6379, 8080, 8443, 27017] {
        portas.insert(porta);
    }

    // Portas "well-known" (0-1023)
    println!("Portas well-known:");
    for porta in portas.range(..1024) {
        println!("  {}", porta);
    }

    // Portas entre 1024 e 9999
    println!("\nPortas registradas:");
    for porta in portas.range(1024..10000) {
        println!("  {}", porta);
    }

    // Portas acima de 5000 (inclusive)
    println!("\nPortas altas (>= 5000):");
    for porta in portas.range(5000..) {
        println!("  {}", porta);
    }

    // Iteração reversa com range
    println!("\nPortas (decrescente):");
    for porta in portas.range(..).rev() {
        print!("{} ", porta);
    }
    println!();
}

3. Operações de Conjunto

use std::collections::BTreeSet;

fn main() {
    let primos: BTreeSet<i32> = BTreeSet::from([2, 3, 5, 7, 11, 13, 17, 19]);
    let impares: BTreeSet<i32> = BTreeSet::from([1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);

    // Interseção: primos E ímpares (primos ímpares)
    let primos_impares: BTreeSet<i32> = primos.intersection(&impares).copied().collect();
    println!("Primos ímpares: {:?}", primos_impares);
    // {3, 5, 7, 11, 13, 17, 19}

    // Diferença: primos que NÃO são ímpares (único primo par)
    let primos_pares: BTreeSet<i32> = primos.difference(&impares).copied().collect();
    println!("Primos pares: {:?}", primos_pares); // {2}

    // União: primos OU ímpares
    let todos: BTreeSet<i32> = primos.union(&impares).copied().collect();
    println!("Primos ou ímpares: {:?}", todos);

    // Diferença simétrica: em um OU outro, mas não em ambos
    let exclusivos: BTreeSet<i32> = primos.symmetric_difference(&impares).copied().collect();
    println!("Exclusivos: {:?}", exclusivos); // {1, 2, 9, 15}

    // Os resultados de operações em BTreeSet já vêm em ordem!
    println!("\nSubconjunto? {:?}", primos_pares.is_subset(&primos)); // true
    println!("Disjuntos? {:?}", primos_pares.is_disjoint(&impares)); // true
}

4. Usando como Fila de Prioridade Simples

use std::collections::BTreeSet;

fn main() {
    // BTreeSet como agenda de eventos ordenados por timestamp
    #[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
    struct Evento {
        timestamp: u64,
        descricao: String,
    }

    let mut agenda: BTreeSet<Evento> = BTreeSet::new();

    agenda.insert(Evento {
        timestamp: 1700000000,
        descricao: "Reunião de equipe".to_string(),
    });
    agenda.insert(Evento {
        timestamp: 1699999000,
        descricao: "Café da manhã".to_string(),
    });
    agenda.insert(Evento {
        timestamp: 1700003600,
        descricao: "Almoço".to_string(),
    });

    // Próximo evento (menor timestamp)
    if let Some(proximo) = agenda.first() {
        println!("Próximo evento: {} ({})", proximo.descricao, proximo.timestamp);
    }

    // Processar eventos em ordem
    println!("\nAgenda do dia:");
    for evento in &agenda {
        println!("  [{}] {}", evento.timestamp, evento.descricao);
    }

    // Remover o primeiro evento (já processado)
    if let Some(processado) = agenda.pop_first() {
        println!("\nEvento processado: {}", processado.descricao);
    }
}

5. Filtrando e Dividindo Conjuntos

use std::collections::BTreeSet;

fn main() {
    let mut numeros: BTreeSet<i32> = (1..=20).collect();
    println!("Original: {:?}", numeros);

    // retain: manter apenas múltiplos de 3
    let mut multiplos_3 = numeros.clone();
    multiplos_3.retain(|&n| n % 3 == 0);
    println!("Múltiplos de 3: {:?}", multiplos_3); // {3, 6, 9, 12, 15, 18}

    // split_off: dividir em dois conjuntos no valor 11
    let maiores = numeros.split_off(&11);
    println!("Menores que 11: {:?}", numeros);  // {1, 2, ..., 10}
    println!("11 ou mais: {:?}", maiores);       // {11, 12, ..., 20}

    // Combinar dois conjuntos mantendo a ordem
    let pares: BTreeSet<i32> = (0..=10).filter(|n| n % 2 == 0).collect();
    let fibonacci: BTreeSet<i32> = BTreeSet::from([0, 1, 1, 2, 3, 5, 8, 13]);

    let combinados: BTreeSet<i32> = pares.union(&fibonacci).copied().collect();
    println!("Pares ∪ Fibonacci: {:?}", combinados);
}

Características de Desempenho

Operação	BTreeSet	HashSet
`insert`	O(log n)	O(1) amortizado
`remove`	O(log n)	O(1) amortizado
`contains`	O(log n)	O(1) amortizado
`first` / `last`	O(log n)	O(n)
`range`	O(log n + k)	Indisponível
Iteração ordenada	O(n)	O(n log n)*
Operações de conjunto	O(n + m)	O(n) ou O(n + m)

* HashSet requer coletar e ordenar para iteração em ordem.

Memória: BTreeSet geralmente usa menos memória que HashSet, pois a árvore B não precisa de slots vazios na tabela hash. Ambos armazenam os dados no heap.

BTreeSet vs HashSet

Critério	BTreeSet	HashSet
Ordem de iteração	Crescente (garantida)	Não determinística
Requisito do tipo	`Ord`	`Eq + Hash`
Range queries	Sim (`range()`)	Não
Menor/Maior	O(log n)	O(n)
Busca individual	O(log n)	O(1) amortizado
Uso de memória	Menor	Maior

Regra prática: Use HashSet como padrão para conjuntos. Troque para BTreeSet quando precisar de ordem, range queries, ou acesso ao menor/maior elemento.

Veja Também

HashSet: Conjunto em Rust — conjunto não ordenado com busca O(1)
BTreeMap: Mapa Ordenado — mapa chave-valor baseado na mesma estrutura
HashMap em Rust — mapa não ordenado
BinaryHeap: Fila de Prioridade — quando só precisa do maior/menor elemento
Ordenar Vetor em Rust — técnicas de ordenação
Traits e Generics — entendendo Ord e PartialOrd