--- title: "BTreeMap\u003cK,V\u003e: Mapa Ordenado em Rust" url: "https://rustlang.com.br/stdlib/btreemap/" markdown_url: "https://rustlang.com.br/stdlib/btreemap.MD" description: "Guia completo do BTreeMap em Rust: mapa ordenado por chaves, range queries, Entry API, iteração em ordem e comparação com HashMap. Exemplos práticos." date: "2026-02-23" author: "Equipe Rust Brasil" --- # BTreeMap: Mapa Ordenado em Rust Guia completo do BTreeMap em Rust: mapa ordenado por chaves, range queries, Entry API, iteração em ordem e comparação com HashMap. Exemplos práticos. O `BTreeMap` é 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`](/stdlib/hashmap/). ## Criando e Inicializando ```rust use std::collections::BTreeMap; fn main() { // Criar vazio let mut mapa: BTreeMap = 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` 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` | 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 ```rust use std::collections::BTreeMap; fn main() { let mut estoque: BTreeMap = 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 ```rust use std::collections::BTreeMap; fn main() { let mut temperaturas: BTreeMap = 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 ```rust 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 ```rust use std::collections::BTreeMap; fn main() { let mut scores: BTreeMap = 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 ```rust use std::collections::BTreeMap; fn main() { let mut numeros: BTreeMap = 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](/stdlib/hashmap/) --- mapa não ordenado com busca O(1) amortizado - [BTreeSet: Conjunto Ordenado](/stdlib/btreeset/) --- conjunto baseado em BTreeMap, sem valores - [HashSet: Conjunto em Rust](/stdlib/hashset/) --- conjunto não ordenado baseado em HashMap - [Como Usar HashMap](/receitas/usar-hashmap/) --- receita prática com HashMap - [Ordenar Vetor em Rust](/receitas/ordenar-vetor/) --- técnicas de ordenação para vetores - [Variáveis, Tipos e Funções](/tutoriais/variaveis-tipos-funcoes/) --- fundamentos dos tipos em Rust - [Traits e Generics](/tutoriais/traits-generics/) --- entendendo Ord, Eq e Hash