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_backOperaçõ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
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"]
(2) Comparação do desempenho de quatro tipos de conjuntos
| Operação | Vec | VecDeque | HashMap | BTreeMap |
|---|---|---|---|---|
| Inserção na cauda | O(1) amortizado | O(1) | O(1) amortizado | O(log n) |
| Inserção no início | O(n) | O(1) | — | — |
| Acesso por índice | O(1) | O(1) | — | — |
| Pesquisa de chave | — | — | O(1) amortizado | O(log n) |
| Consulta de intervalo | Não suportado | Não suportado | Não suportado | O(log n + k) |
| Traversal ordenada | Deve estar ordenada | Deve estar ordenada | Não ordenada | O(n) (ordenada) |
| Uso de memória | Baixo | Baixo | Médio | Médio |
(3) Estratégia de seleção
| Cenário | Coleção recomendada | Motivo |
|---|---|---|
| Fila / Buffer (operações em ambas as extremidades) | VecDeque | O(1) em ambas as extremidades — nada é mais adequado do que isso |
| Requer percorrimento ordenado por chave | BTreeMap | Ordenado automaticamente; não são necessárias etapas adicionais de ordenação |
| Consultas por intervalo necessárias | BTreeMap | A única coleção que suporta consultas por intervalo |
| Requer apenas operações na cauda | Vec | Mais simples e com menor consumo de memória |
| Requer apenas consultas de chave-valor | HashMap | Consultas em O(1), mais rápidas que o BTreeMap |
| Inserção e exclusão frequentes de elementos no meio | LinkedList | Teoricamente O(1), mas raramente usada na prática |
(4) Referência rápida aos métodos comuns do VecDeque e do BTreeMap
| Conjunto | Método | Descrição | Complexidade temporal |
|---|---|---|---|
| VecDeque | push_front(val) |
Inserção no início | O(1) |
| VecDeque | push_back(val) |
Inserir no final | O(1) |
| VecDeque | pop_front() |
Retirar o primeiro elemento da matriz | O(1) |
| VecDeque | pop_back() |
Retirar do final | O(1) |
| VecDeque | front() / back() |
Exibir o primeiro e o último elementos | O(1) |
| VecDeque | len() / is_empty() |
Consulta de comprimento | O(1) |
| BTreeMap | insert(k, v) |
Inserir par chave-valor | O(log n) |
| BTreeMap | get(&k) |
Pesquisa por chave | O(log n) |
| BTreeMap | remove(&k) |
Exclusão por chave | O(log n) |
| BTreeMap | range(start..=end) |
Consulta de intervalo | O(log n + k) |
| BTreeMap | first_key_value() |
Menor número de pares chave-valor | O(log n) |
| BTreeMap | last_key_value() |
Número máximo de pares chave-valor | O(log n) |
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()epush_back()são ambas operações de complexidade O(1).front()eback()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()elast_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 estart..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 umLinkedListacarreta 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 doVecou doVecDeque, 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 deVecouVecDeque.
P: Como o BTreeMap implementa a paginação para a operação
range? R: Ele utilizanext()enth()para implementar a paginação baseada em cursor. Por exemplo,map.range(start..).take(20)recupera os primeiros 20 registros a partir destarte usa a chave do último registro como o novostartpara a próxima solicitação. Isso é mais eficiente do queLIMIT OFFSETao 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_backsã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
- Dificuldade ⭐: Implemente um “histórico de desfazer” usando VecDeque. Registre cada operação usando
push_backe, ao desfazer, remova a operação mais recente usandopop_back. Simule três operações seguidas de duas operações de desfazer e imprima o conteúdo de cada operação. - 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()). - 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 (usandostd::time::Instantpara medir o tempo).
