BTreeMap<K,V>: Mapa Ordenado em Rust

O BTreeMap<K, V> é um mapa associativo da biblioteca padrão do Rust que mantém suas chaves sempre ordenadas. Internamente, ele utiliza uma árvore B (B-Tree), o que garante complexidade O(log n) para inserção, busca e remoção. É a escolha ideal quando você precisa iterar sobre os elementos em ordem ou realizar consultas por faixa de chaves (range queries).

Quando Usar BTreeMap

Use BTreeMap quando:

Você precisa iterar sobre as chaves em ordem crescente (ou decrescente).
Precisa fazer consultas por faixa (range) — por exemplo, “todas as entradas com chave entre 10 e 50”.
Deseja um mapa com comportamento determinístico na iteração (a ordem é sempre a mesma para os mesmos dados).
As chaves implementam Ord mas não implementam Hash.

Se a ordem não importa e você quer o melhor desempenho médio, prefira HashMap.

Criando e Inicializando

use std::collections::BTreeMap;

fn main() {
    // Criar vazio
    let mut mapa: BTreeMap<String, i32> = BTreeMap::new();

    // Criar a partir de um array de tuplas
    let capitais = BTreeMap::from([
        ("Brasil", "Brasília"),
        ("Argentina", "Buenos Aires"),
        ("Chile", "Santiago"),
        ("Uruguai", "Montevidéu"),
    ]);

    // Criar a partir de iteradores com collect
    let chaves = vec!["x", "a", "m"];
    let valores = vec![10, 20, 30];
    let mapa2: BTreeMap<&str, i32> = chaves.into_iter().zip(valores).collect();

    // As chaves já estarão ordenadas: "a", "m", "x"
    for (k, v) in &mapa2 {
        println!("{}: {}", k, v);
    }
}

Tabela de Métodos Comuns

Método	Descrição	Complexidade
`insert(key, value)`	Insere par chave-valor; retorna `Option<V>` com valor anterior	O(log n)
`get(&key)`	Retorna `Option<&V>` para a chave	O(log n)
`get_mut(&key)`	Retorna `Option<&mut V>` para a chave	O(log n)
`remove(&key)`	Remove e retorna `Option<V>`	O(log n)
`contains_key(&key)`	Verifica se a chave existe	O(log n)
`entry(key)`	Acessa a Entry API para inserção condicional	O(log n)
`range(range)`	Itera sobre um intervalo de chaves	O(log n + k)
`iter()`	Iterador sobre pares `(&K, &V)` em ordem	O(n)
`keys()` / `values()`	Iteradores sobre chaves ou valores em ordem	O(n)
`len()` / `is_empty()`	Tamanho e verificação de vazio	O(1)
`first_key_value()`	Retorna o menor par chave-valor	O(log n)
`last_key_value()`	Retorna o maior par chave-valor	O(log n)
`pop_first()`	Remove e retorna o menor par	O(log n)
`pop_last()`	Remove e retorna o maior par	O(log n)
`split_off(&key)`	Divide o mapa em dois no ponto da chave	O(n)

Exemplos Práticos

1. Inserção, Busca e Remoção

use std::collections::BTreeMap;

fn main() {
    let mut estoque: BTreeMap<String, u32> = BTreeMap::new();

    // Inserindo produtos
    estoque.insert("Arroz".to_string(), 50);
    estoque.insert("Feijão".to_string(), 30);
    estoque.insert("Macarrão".to_string(), 45);
    estoque.insert("Café".to_string(), 20);

    // Buscando
    if let Some(qtd) = estoque.get("Café") {
        println!("Café em estoque: {} unidades", qtd);
    }

    // Atualizando com insert (retorna valor anterior)
    let anterior = estoque.insert("Café".to_string(), 25);
    println!("Quantidade anterior de Café: {:?}", anterior); // Some(20)

    // Removendo
    let removido = estoque.remove("Macarrão");
    println!("Removido Macarrão: {:?}", removido); // Some(45)

    // Iterando — a saída estará em ordem alfabética!
    println!("\nEstoque ordenado:");
    for (produto, qtd) in &estoque {
        println!("  {}: {} unidades", produto, qtd);
    }
    // Saída:
    //   Arroz: 50 unidades
    //   Café: 25 unidades
    //   Feijão: 30 unidades
}

2. Range Queries — Consultas por Faixa

use std::collections::BTreeMap;

fn main() {
    let mut temperaturas: BTreeMap<u32, f64> = BTreeMap::new();

    // Registros de temperatura por hora (0-23)
    temperaturas.insert(0, 18.5);
    temperaturas.insert(3, 16.2);
    temperaturas.insert(6, 15.0);
    temperaturas.insert(9, 22.3);
    temperaturas.insert(12, 28.7);
    temperaturas.insert(15, 30.1);
    temperaturas.insert(18, 25.4);
    temperaturas.insert(21, 20.8);

    // Temperaturas entre 9h e 18h (inclusive)
    println!("Temperaturas durante o dia (9h-18h):");
    for (hora, temp) in temperaturas.range(9..=18) {
        println!("  {}h: {:.1}°C", hora, temp);
    }

    // Temperaturas da manhã (antes das 12h)
    println!("\nTemperaturas da manhã:");
    for (hora, temp) in temperaturas.range(..12) {
        println!("  {}h: {:.1}°C", hora, temp);
    }

    // Menor e maior registro
    if let Some((hora, temp)) = temperaturas.first_key_value() {
        println!("\nPrimeiro registro: {}h = {:.1}°C", hora, temp);
    }
    if let Some((hora, temp)) = temperaturas.last_key_value() {
        println!("Último registro: {}h = {:.1}°C", hora, temp);
    }
}

3. Entry API — Inserção Condicional e Atualização

use std::collections::BTreeMap;

fn main() {
    let palavras = vec![
        "rust", "é", "rápido", "rust", "é", "seguro",
        "rust", "é", "divertido", "aprender", "rust",
    ];

    let mut contagem: BTreeMap<&str, usize> = BTreeMap::new();

    for palavra in &palavras {
        // or_insert retorna &mut V, permitindo incrementar
        *contagem.entry(palavra).or_insert(0) += 1;
    }

    // Resultado em ordem alfabética
    println!("Contagem de palavras (ordem alfabética):");
    for (palavra, freq) in &contagem {
        println!("  {}: {}", palavra, freq);
    }

    // Usando and_modify + or_insert
    let mut inventario: BTreeMap<&str, (u32, f64)> = BTreeMap::new();

    // (quantidade, preço)
    inventario.entry("Widget")
        .and_modify(|(qtd, _)| *qtd += 10)
        .or_insert((10, 29.99));

    inventario.entry("Widget")
        .and_modify(|(qtd, _)| *qtd += 5)
        .or_insert((0, 0.0));

    println!("\nWidget: {:?}", inventario["Widget"]); // (15, 29.99)
}

4. Iteração Reversa e Operações com Primeiro/Último

use std::collections::BTreeMap;

fn main() {
    let mut scores: BTreeMap<String, u32> = BTreeMap::new();
    scores.insert("Alice".to_string(), 95);
    scores.insert("Bruno".to_string(), 87);
    scores.insert("Carla".to_string(), 92);
    scores.insert("Daniel".to_string(), 78);
    scores.insert("Elena".to_string(), 99);

    // Iteração reversa (Z -> A)
    println!("Ranking inverso (Z -> A):");
    for (nome, score) in scores.iter().rev() {
        println!("  {}: {}", nome, score);
    }

    // Remover o primeiro (menor chave) e o último (maior chave)
    if let Some((nome, score)) = scores.pop_first() {
        println!("\nRemovido primeiro: {} ({})", nome, score);
    }
    if let Some((nome, score)) = scores.pop_last() {
        println!("Removido último: {} ({})", nome, score);
    }

    println!("\nRestantes:");
    for (nome, score) in &scores {
        println!("  {}: {}", nome, score);
    }
}

5. Dividindo e Mesclando Mapas

use std::collections::BTreeMap;

fn main() {
    let mut numeros: BTreeMap<i32, &str> = BTreeMap::new();
    numeros.insert(1, "um");
    numeros.insert(2, "dois");
    numeros.insert(3, "três");
    numeros.insert(4, "quatro");
    numeros.insert(5, "cinco");
    numeros.insert(6, "seis");

    // split_off divide: chaves >= 4 vão para o novo mapa
    let maiores = numeros.split_off(&4);

    println!("Menores que 4: {:?}", numeros);
    // {1: "um", 2: "dois", 3: "três"}

    println!("Maiores ou iguais a 4: {:?}", maiores);
    // {4: "quatro", 5: "cinco", 6: "seis"}

    // Mesclando dois mapas
    let mut mapa_a = BTreeMap::from([("a", 1), ("b", 2)]);
    let mapa_b = BTreeMap::from([("b", 20), ("c", 3)]);

    // extend sobrescreve chaves duplicadas
    mapa_a.extend(mapa_b);
    println!("\nMesclado: {:?}", mapa_a);
    // {"a": 1, "b": 20, "c": 3}
}

Características de Desempenho

O BTreeMap usa uma árvore B internamente, o que proporciona desempenho consistente e previsível.

Operação	BTreeMap	HashMap
Inserção	O(log n)	O(1) amortizado
Busca	O(log n)	O(1) amortizado
Remoção	O(log n)	O(1) amortizado
Iteração ordenada	O(n)	O(n log n)*
Range query	O(log n + k)	Não disponível
Menor/Maior chave	O(log n)	O(n)

* Para iterar em ordem com HashMap, é necessário coletar as chaves e ordená-las primeiro.

Considerações de memória:

BTreeMap usa menos memória que HashMap porque não precisa de uma tabela hash com slots vazios.
BTreeMap tem melhor localidade de cache para iteração sequencial, pois os dados são armazenados em nós contíguos.
HashMap é geralmente mais rápido para operações individuais de busca/inserção/remoção quando a ordem não importa.

BTreeMap vs HashMap — Quando Escolher Cada Um

Critério	BTreeMap	HashMap
Ordem das chaves	Garantida (crescente)	Não determinística
Requisito da chave	`Ord`	`Eq + Hash`
Melhor para	Range queries, iteração ordenada	Busca rápida por chave
Range queries	Sim (`range()`)	Não
Primeiro/Último	O(log n) com `first_key_value()`	O(n) — percorre tudo
Uso de memória	Menor	Maior (tabela hash)
Desempenho médio	O(log n)	O(1) amortizado

Regra prática: Use HashMap como padrão. Troque para BTreeMap quando precisar de ordem, range queries, ou quando as chaves não implementam Hash.

Veja Também

HashMap em Rust — mapa não ordenado com busca O(1) amortizado
BTreeSet: Conjunto Ordenado — conjunto baseado em BTreeMap, sem valores
HashSet: Conjunto em Rust — conjunto não ordenado baseado em HashMap
Como Usar HashMap — receita prática com HashMap
Ordenar Vetor em Rust — técnicas de ordenação para vetores
Variáveis, Tipos e Funções — fundamentos dos tipos em Rust
Traits e Generics — entendendo Ord, Eq e Hash