Rust: Coleções comuns do Rust

Última atualização: 2026-08-26

VecDeque é uma fila de duas extremidades que permite inserções e exclusões eficientes em ambas as extremidades; BTreeMap é um mapa ordenado de chave-valor que permite consultas por intervalo. São membros “especializados” da biblioteca de coleções do Rust.

Se um Vec é como “esperar na fila para entrar no ônibus” (só é possível entrar no final da fila), então um VecDeque é como “alguém furando a fila” (é possível entrar e sair por qualquer uma das extremidades). Se um HashMap é como um “dicionário” (consultas aleatórias), então um BTreeMap é como uma “lista de contatos” (organizada em ordem alfabética, e você pode ir direto para uma página específica para começar a ler).

1. O que você vai aprender

• VecDeque: push_front / pop_back Operações em uma fila de duas extremidades
• BTreeMap: Armazenamento ordenado de chave-valor e consultas por intervalo range
• Casos de uso e limitações das listas encadeadas
• Comparação de desempenho entre quatro tipos de coleções (Vec / VecDeque / HashMap / BTreeMap)
• Definir a estratégia de seleção: escolher a estrutura de dados adequada com base no cenário

2. Diagramas conceituais

O diagrama comparativo do Mermaid a seguir ilustra as diferenças entre a fila de duas extremidades VecDeque e a estrutura de dados BTreeMap (mapa em árvore B):

graph LR
    subgraph VecDeque["VecDeque Double-ended queue"]
        direction LR
        V1["pop_front O(1)"] --> V2["Element1"]
        V2 --> V3["Element2"]
        V3 --> V4["..."]
        V4 --> V5["ElementN"]
        V5 --> V6["push_back O(1)"]
        V7["push_front O(1)"] -.-> V2
    end

    subgraph BTreeMap["BTreeMap BOrdered Map of Trees"]
        direction TB
        B0["Root Node"] --> B1["Left Branch<br/>Keys: A-M"]
        B0 --> B2["Right Branch<br/>Keys: N-Z"]
        B1 --> B3["(Alice, 95)"]
        B1 --> B4["(Bob, 72)"]
        B2 --> B5["(Charlie, 87)"]
        B2 --> B6["(David, 91)"]
    end

    VecDeque -.-> |Comparison of Data Structures| BTreeMap

graph LR
    subgraph VecDeque["VecDeque Double-ended queue"]
        direction LR
        V1["pop_front O(1)"] --> V2["Element1"]
        V2 --> V3["Element2"]
        V3 --> V4["..."]
        V4 --> V5["ElementN"]
        V5 --> V6["push_back O(1)"]
        V7["push_front O(1)"] -.-> V2
    end

    subgraph BTreeMap["BTreeMap BOrdered Map of Trees"]
        direction TB
        B0["Root Node"] --> B1["Left Branch<br/>Keys: A-M"]
        B0 --> B2["Right Branch<br/>Keys: N-Z"]
        B1 --> B3["(Alice, 95)"]
        B1 --> B4["(Bob, 72)"]
        B2 --> B5["(Charlie, 87)"]
        B2 --> B6["(David, 91)"]
    end

    VecDeque -.-> |Comparison of Data Structures| BTreeMap

3. A história de um sistema de filas e senhas

(1) Problema: Simulação de uma fila usando o Vec, mas tanto furar a fila quanto sair dela são lentos

Tom (Tom) está desenvolvendo um sistema de gerenciamento de filas para restaurantes. Os clientes pegam um número ao chegarem, e o garçom chama o número para que eles se sentem à mesa.

No início, ele implementou isso usando o Vec:

let mut queue = Vec::new();
queue.push("Customer A");   // A Get a ticket，At the back of the line
queue.push("Customer B");   // B Get a ticket，At the back of the line
queue.push("Customer C");   // C Get a ticket，At the back of the line

// Take a seat when your number is called：Remove from the front of the line
let first = queue.remove(0);  // O(n) —— All elements that follow must be moved forward！
println!("{} Take a seat", first);

A operação de Vec remove(0) tem complexidade O(n) — após remover o primeiro elemento, todos os elementos restantes precisam ser deslocados uma posição para a frente. Se houver 10.000 pessoas na fila, cada vez que um número for chamado, 9.999 elementos precisam ser deslocados. Isso claramente não é adequado para um sistema de produção.

(2) Requisitos mais complexos: prioridade VIP + busca por número

Para piorar a situação, o gerente do restaurante disse:

• Os clientes VIP podem pular a fila e ir direto para o início da fila
• Os atendentes de atendimento ao cliente precisam consultar rapidamente as informações dos clientes pelo número do ticket
• Às vezes, é necessário consultar a lista de “clientes que pegaram uma senha entre 14h e 15h”.

O Vec simplesmente não consegue lidar com esses requisitos de jeito nenhum.

(3) Soluções para coleções em Rust

use std::collections::VecDeque;
use std::collections::BTreeMap;

fn main() {
    // VecDeque：Accessible from both the front and the back
    let mut queue = VecDeque::new();
    queue.push_back("Customer A");   // Enter at the back of the line
    queue.push_back("Customer B");
    queue.push_front("VIP");         // VIP Cutting in line at the front of the line！

    println!("Next, please take a seat.: {}", queue.pop_front().unwrap());  // VIP
    println!("Next: {}", queue.pop_front().unwrap());    // Customer A

    // BTreeMap：Ordered Key-Value Store
    let mut customers = BTreeMap::new();
    customers.insert(1001, "Alice");
    customers.insert(1003, "Bob");
    customers.insert(1002, "Charlie");

    // Automatically Sort and Output Buttons
    for (id, name) in &customers {
        println!("Get a ticket #{}: {}", id, name);
    }
    // Output: #1001: Alice, #1002: Charlie, #1003: Bob
}

As operações em ambas as extremidades de um VecDeque têm complexidade O(1), enquanto um BTreeMap classifica automaticamente as chaves e suporta consultas por intervalo. O primeiro resolve o problema do “fila”, e o segundo resolve o problema da “busca ordenada”.

4. Conceitos fundamentais

(1) Comparação entre quatro estruturas de conjuntos

graph TB
    A[Rust Collection Library] --> B[Vec: Contiguous Arrays]
    A --> C[VecDeque: Double-ended queue]
    A --> D[HashMap: Hash Table]
    A --> E[BTreeMap: B Ordered Map of Trees]

    B --> F["push / pop: O(1) Amortized"]
    B --> G["insert(0) / remove(0): O(n)"]

    C --> H["push_front / pop_front: O(1)"]
    C --> I["push_back / pop_back: O(1)"]

    D --> J["Insert / Search: O(1) Amortized"]
    D --> K["Disorder —— No order guarantee"]

    E --> L["Insert / Search: O(log n)"]
    E --> M["Orderly —— Support for Range Queries range"]

graph TB
    A[Rust Collection Library] --> B[Vec: Contiguous Arrays]
    A --> C[VecDeque: Double-ended queue]
    A --> D[HashMap: Hash Table]
    A --> E[BTreeMap: B Ordered Map of Trees]

    B --> F["push / pop: O(1) Amortized"]
    B --> G["insert(0) / remove(0): O(n)"]

    C --> H["push_front / pop_front: O(1)"]
    C --> I["push_back / pop_back: O(1)"]

    D --> J["Insert / Search: O(1) Amortized"]
    D --> K["Disorder —— No order guarantee"]

    E --> L["Insert / Search: O(log n)"]
    E --> M["Orderly —— Support for Range Queries range"]

(2) Comparação do desempenho de quatro tipos de conjuntos

(3) Estratégia de seleção

(4) Referência rápida aos métodos comuns do VecDeque e do BTreeMap

5. Dar o exemplo

▶ Exemplo 1: Fila de duas extremidades com VecDeque — Sistema de fila e emissão de senhas (Dificuldade ⭐)

// ============================================
// VecDeque：Basic Operations on a Double-Ended Queue
// ============================================

use std::collections::VecDeque;

fn main() {
    let mut queue: VecDeque<&str> = VecDeque::new();

    // Regular customers enter from the back of the line
    queue.push_back("Alice");
    queue.push_back("Bob");
    queue.push_back("Charlie");

    // VIP A customer cut in line from the front of the line
    queue.push_front("VIP-David");
    queue.push_front("VIP-Eve");

    println!("Current number of people in line: {}", queue.len());
    println!("At the head of the line: {:?}, Bringing up the rear: {:?}", queue.front(), queue.back());

    // Take a seat when your number is called：Remove from the front of the queue
    println!("\nCall Order:");
    while let Some(customer) = queue.pop_front() {
        println!("  {} Take a seat", customer);
    }
}

Resultado:

Current number of people in line: 5
At the head of the line: Some("VIP-Eve"), Bringing up the rear: Some("Charlie")

Call Order:
  VIP-Eve Take a seat
  VIP-David Take a seat
  Alice Take a seat
  Bob Take a seat
  Charlie Take a seat

push_front() e push_back() são ambas operações de complexidade O(1). front() e back() retornam referências à frente e ao fim da fila, respectivamente, sem remover os elementos. pop_front() remove e retorna o elemento que está na frente da fila.

▶ Exemplo 2: BTreeMap — Armazenamento ordenado de chave-valor: Classificações por nota (Dificuldade ⭐⭐)

// ============================================
// BTreeMap：Automatic Button Sorting
// ============================================

use std::collections::BTreeMap;

fn main() {
    let mut scores = BTreeMap::new();

    scores.insert("Charlie", 87);
    scores.insert("Alice", 95);
    scores.insert("Bob", 72);
    scores.insert("David", 91);

    // BTreeMap Button（Alphabetical order）Automatic Sorting
    println!("=== Transcript（Sort by Name）===");
    for (name, score) in &scores {
        println!("  {}: {}", name, score);
    }

    // Search by Key
    println!("\nAlice the results: {}", scores.get("Alice").unwrap());

    // Check for the presence of
    if scores.contains_key("Eve") {
        println!("Eve There are discrepancies in the scores");
    } else {
        println!("Eve No results yet");
    }

    // Get the first and last entries
    println!("\nFirst: {:?}", scores.first_key_value());
    println!("The last one: {:?}", scores.last_key_value());
}

Resultado:

=== Transcript（Sort by Name）===
  Alice: 95
  Bob: 72
  Charlie: 87
  David: 91

Alice the results: 95
Eve No results yet

First: Some(("Alice", 95))
The last one: Some(("David", 91))

O BTreeMap ordena automaticamente as chaves na ordem Ord. A ordem de classificação padrão para strings é lexicográfica; portanto, “Alice” vem primeiro e “David” vem por último. first_key_value() e last_key_value() proporcionam acesso eficiente ao primeiro e ao último elemento.

▶ Exemplo 3: Consulta de intervalo no BTreeMap — Consulta de intervalo de datas (Dificuldade ⭐⭐)

// ============================================
// BTreeMap Range Query：range Methods
// ============================================

use std::collections::BTreeMap;

fn main() {
    // Simulated Order System：Date -> Order Amount
    let mut orders = BTreeMap::new();

    orders.insert("2026-07-01", 120);
    orders.insert("2026-07-03", 85);
    orders.insert("2026-07-05", 200);
    orders.insert("2026-07-07", 150);
    orders.insert("2026-07-10", 95);

    // Search orders placed between July 3 and July 7 (inclusive)
    println!("=== July 3 ~ July 7 Orders ===");
    for (date, amount) in orders.range("2026-07-03"..="2026-07-07") {
        println!("  {}: ${}", date, amount);
    }

    // Search all orders on or after July 5
    println!("\n=== July 5 and After Orders ===");
    for (date, amount) in orders.range("2026-07-05"..) {
        println!("  {}: ${}", date, amount);
    }

    // Total Amount
    let total: i32 = orders.range("2026-07-03"..="2026-07-07")
        .map(|(_, amount)| amount)
        .sum();
    println!("\nJuly 3 ~ July 7 Total Amount: ${}", total);
}

Resultado:

=== July 3 ~ July 7 Orders ===
  2026-07-03: $85
  2026-07-05: $200
  2026-07-07: $150

=== July 5 and After Orders ===
  2026-07-05: $200
  2026-07-07: $150
  2026-07-10: $95

July 3 ~ July 7 Total Amount: $435

range() é um método exclusivo do BTreeMap. Ele aceita uma expressão de intervalo (.. para um intervalo aberto, ..= para um intervalo fechado e start.. para um intervalo semiaberto) e retorna um iterador. Isso é algo que o HashMap não consegue fazer.

▶ Exemplo 4: Comparação de desempenho entre quatro tipos de conjuntos (Dificuldade ⭐⭐⭐)

// ============================================
// Comparison of the Performance of Four Types of Sets：Insert 10000 element
// ============================================

use std::collections::{BTreeMap, HashMap, VecDeque};
use std::time::Instant;

fn main() {
    let n = 10_000;

    // Vec Insert at the end
    let start = Instant::now();
    let mut vec = Vec::new();
    for i in 0..n {
        vec.push(i);
    }
    println!("Vec Insert at the end: {:?}", start.elapsed());

    // VecDeque Insert at the end
    let start = Instant::now();
    let mut deque = VecDeque::new();
    for i in 0..n {
        deque.push_back(i);
    }
    println!("VecDeque Insert at the end: {:?}", start.elapsed());

    // HashMap Insert
    let start = Instant::now();
    let mut hmap = HashMap::new();
    for i in 0..n {
        hmap.insert(i, i);
    }
    println!("HashMap Insert: {:?}", start.elapsed());

    // BTreeMap Insert
    let start = Instant::now();
    let mut bmap = BTreeMap::new();
    for i in 0..n {
        bmap.insert(i, i);
    }
    println!("BTreeMap Insert: {:?}", start.elapsed());

    // Search for Performance Comparisons
    println!("\n--- Search Performance ---");

    let start = Instant::now();
    let _ = vec.contains(&9999);
    println!("Vec Linear Search: {:?}", start.elapsed());

    let start = Instant::now();
    let _ = hmap.get(&9999);
    println!("HashMap Search: {:?}", start.elapsed());

    let start = Instant::now();
    let _ = bmap.get(&9999);
    println!("BTreeMap Search: {:?}", start.elapsed());
}

Resultado (exemplo; o tempo real pode variar dependendo da máquina):

Vec Insert at the end: 78.2µs
VecDeque Insert at the end: 82.1µs
HashMap Insert: 1.2ms
BTreeMap Insert: 2.8ms

--- Search Performance ---
Vec Linear Search: 42.5µs
HashMap Search: 138ns
BTreeMap Search: 312ns

Os dados de desempenho mostram que o HashMap é o mais rápido para consultas (O(1)), seguido pelo BTreeMap (O(log n)), enquanto o Vec é o mais lento para consultas lineares (O(n)). Para inserções, a inserção na cauda é mais rápida com o Vec e o VecDeque, e mais lenta com o BTreeMap. Isso confirma que “não existe uma solução milagrosa” — a escolha da coleção depende do caso de uso específico.

▶ Exemplo 5: Exercício abrangente — Sistema de agendamento de tarefas (Dificuldade ⭐⭐⭐)

// ============================================
// Comprehensive Example：VecDeque Queue + BTreeMap Priority
// ============================================

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

#[derive(Debug, Clone)]
struct Task {
    id: u32,
    name: String,
    priority: u8,
}

fn main() {
    let mut queue: VecDeque<Task> = VecDeque::new();
    queue.push_back(Task { id: 1, name: "Check email".into(), priority: 3 });
    queue.push_back(Task { id: 2, name: "Fix bug #42".into(), priority: 1 });
    queue.push_back(Task { id: 3, name: "Write report".into(), priority: 2 });
    queue.push_back(Task { id: 4, name: "Urgent deploy".into(), priority: 0 });

    println!("=== FIFO Queue Processing ===");
    while let Some(task) = queue.pop_front() {
        println!("[P{}] #{}: {}", task.priority, task.id, task.name);
    }

    let mut priority_map: BTreeMap<u8, Vec<String>> = BTreeMap::new();
    let tasks = vec![
        ("Check email", 3u8), ("Fix bug #42", 1), ("Write report", 2),
        ("Urgent deploy", 0), ("Code review", 1), ("Team meeting", 3),
        ("Security patch", 0), ("Update docs", 2),
    ];

    for (name, pri) in tasks {
        priority_map.entry(pri).or_insert_with(Vec::new).push(name.to_string());
    }

    println!("\n=== Sort by priority ===");
    for (pri, task_list) in &priority_map {
        println!("P{}: {:?}", pri, task_list);
    }

    println!("\n=== High-Priority Tasks (P0-P1) ===");
    for (pri, task_list) in priority_map.range(0..=1) {
        println!("P{}: {:?}", pri, task_list);
    }

    let mut history: VecDeque<String> = VecDeque::with_capacity(3);
    for i in 0..5 {
        history.push_back(format!("task_{}", i));
        if history.len() > 3 {
            history.pop_front();
        }
    }
    println!("\nLast 3 history entries: {:?}", history);
}

Resultado:

=== FIFO Queue Processing ===
[P3] #1: Check email
[P1] #2: Fix bug #42
[P2] #3: Write report
[P0] #4: Urgent deploy

=== Sort by priority ===
P0: ["Urgent deploy", "Security patch"]
P1: ["Fix bug #42", "Code review"]
P2: ["Write report", "Update docs"]
P3: ["Check email", "Team meeting"]

=== High-Priority Tasks (P0-P1) ===
P0: ["Urgent deploy", "Security patch"]
P1: ["Fix bug #42", "Code review"]

Last 3 history entries: ["task_2", "task_3", "task_4"]

Use um VecDeque como fila FIFO (push_back + pop_front); o BTreeMap agrupa os itens por prioridade e os classifica automaticamente; range(0..=1) exibe apenas tarefas de alta prioridade; o VecDeque de capacidade fixa implementa um histórico das “últimas N entradas”.

❓ Perguntas Frequentes

P: Qual é a diferença entre VecDeque e Vec? Quando devo usar o VecDeque? R: O VecDeque suporta operações O(1) em ambas as extremidades, enquanto o Vec suporta operações O(1) apenas na cauda. Se você precisar remover elementos da cabeça (como em um cenário de fila) ou realizar inserções/exclusões em ambas as extremidades, use o VecDeque. Se você precisar apenas de operações na cauda (como em um cenário de pilha), usar o Vec é mais simples.

P: Qual é a diferença entre um BTreeMap e um HashMap? R: Um BTreeMap é ordenado, enquanto um HashMap não é ordenado. Um BTreeMap armazena entradas em ordem de chave e suporta consultas por intervalo, mas as inserções e pesquisas têm complexidade temporal de O(log n). Um HashMap não garante nenhuma ordem específica, mas as inserções e pesquisas têm complexidade temporal de O(1). Use um BTreeMap quando for necessário fazer ordenamento ou consultas por intervalo; caso contrário, um HashMap é mais rápido.

P: Por que o LinkedList é raramente usado em Rust? R: Cada nó em um LinkedList acarreta uma sobrecarga adicional de ponteiros e não é compatível com o cache. Embora as inserções e exclusões sejam, teoricamente, O(1), o desempenho real costuma ser pior do que o do Vec ou do VecDeque, pois a memória não contígua leva a baixas taxas de acertos no cache. A menos que você esteja realizando um grande número de inserções e exclusões no meio da lista e lidando com uma quantidade enorme de dados, deve priorizar o uso de Vec ou VecDeque.

P: Como o BTreeMap implementa a paginação para a operação range? R: Ele utiliza next() e nth() para implementar a paginação baseada em cursor. Por exemplo, map.range(start..).take(20) recupera os primeiros 20 registros a partir de start e usa a chave do último registro como o novo start para a próxima solicitação. Isso é mais eficiente do que LIMIT OFFSET ao lidar com grandes conjuntos de dados.

P: Existe alguma regra mnemônica simples para escolher entre os quatro tipos de coleção? R: Sim. “Use Vec para operações na extremidade, VecDeque para operações em ambas as extremidades, HashMap para consultas não ordenadas e BTreeMap para consultas ordenadas.” Se você se lembrar dessas quatro frases, não vai errar na escolha em 90% dos casos.

📖 Resumo

• Lista duplamente encadeada VecDeque: push_front / push_back / pop_front / pop_back são todas O(1)
• BTreeMap Mapa ordenado: as chaves são classificadas automaticamente; suporta consultas por intervalo range()
• A LinkedList raramente é usada em Rust — ela não é compatível com o cache, e seu desempenho real é inferior ao do VecDeque
• O HashMap tem tempo de consulta O(1), mas não é ordenado; o BTreeMap tem tempo de consulta O(log n), mas é ordenado
• Definir estratégia de seleção: Selecione o conjunto correto com base no modo de operação (final/ambas as extremidades/busca/intervalo)
• VecDeque e BTreeMap são joias subestimadas na biblioteca std::collections — em muitos cenários, elas são mais adequadas do que Vec e HashMap

📝 Exercícios

1. Dificuldade ⭐: Implemente um “histórico de desfazer” usando VecDeque. Registre cada operação usando push_back e, ao desfazer, remova a operação mais recente usando pop_back. Simule três operações seguidas de duas operações de desfazer e imprima o conteúdo de cada operação.
2. Dificuldade ⭐⭐: Implemente um “Sistema de Gerenciamento de Notas dos Alunos” utilizando um mapa em árvore B. Insira os nomes e as notas de 5 alunos e imprima a classificação em ordem decrescente por nota (Dica: um mapa em árvore B não pode classificar diretamente por valor; você deve usar a nota como chave e o nome como valor, ou usar iter().rev()).
3. Dificuldade ⭐⭐⭐: Escreva uma função fn analyze_collections(data: &[i32]) que receba como entrada uma fatia de inteiros, conte o número de ocorrências de cada dígito usando, respectivamente, VecDeque, HashMap e BTreeMap, e compare as diferenças de desempenho entre as três abordagens (usando std::time::Instant para medir o tempo).

Equipe Técnica Web-Tutorial

Uma plataforma de tutoriais mantida por diversos desenvolvedores. Cada tutorial é escrito e revisado por profissionais da área correspondente. Trabalhamos para manter nosso conteúdo preciso e confiável — se encontrar algum problema, avise-nos.

Sobre Nós