As data structures em Rust são componentes fundamentais que permitem aos desenvolvedores organizar e gerenciar dados de forma eficiente. A biblioteca padrão do Rust oferece diversas estruturas, cada uma otimizada para diferentes casos de uso, garantindo segurança, concorrência e praticidade. Neste artigo, vamos explorar algumas das mais importantes data structures em Rust, como Vectors, Hash Maps e Hash Sets, além de outras opções avançadas.
Explorando as Data Structures em Rust
A biblioteca padrão do Rust fornece estruturas de dados essenciais, como Vectors (Vec<T>), Hash Maps (HashMap<K, V>) e Hash Sets (HashSet<T>). Essas três estruturas são as mais utilizadas e úteis na maioria dos cenários de programação. Seu design está alinhado com os objetivos do Rust de oferecer uma linguagem de programação segura, concorrente e prática. Essas estruturas cobrem a maioria das necessidades de armazenamento e acesso a dados, mantendo a natureza leve e eficiente da biblioteca padrão do Rust.
Vectors (Vec<T>)
Um vector é a implementação de array dinâmico mais utilizada no Rust. Ele oferece acesso indexado rápido, redimensionamento dinâmico e travessia eficiente devido ao seu armazenamento de memória contíguo, que aproveita os modernos mecanismos de caching da CPU.
No código abaixo, podemos ver como criar, inicializar, adicionar, remover e acessar elementos em um vector:
fn main() {
// Cria um vector vazio
let mut numbers: Vec = Vec::new();
// Cria e inicializa um vector usando uma macro
let mut names = vec!["Alice", "Bob", "Carol"];
// Adiciona elementos ao vector
numbers.push(1);
numbers.push(2);
numbers.push(3);
// Remove elementos do vector
numbers.pop(); // Remove e retorna o último elemento
// Acessa elementos no vector
if let Some(first_name) = names.get(0) {
println!("O primeiro nome é: {}", first_name);
}
// Itera através dos elementos do vector
for name in &names {
println!("{}", name);
}
// Modifica elementos no vector
if let Some(first_name) = names.get_mut(0) {
*first_name = "Dave";
}
// Usa um iterador para processar elementos do vector
let numbers_squared: Vec = numbers.iter().map(|&x| x * x).collect();
println!("Números ao quadrado: {:?}", numbers_squared);
// Estende o vector com elementos adicionais
numbers.extend([4, 5, 6].iter().copied());
// Acessa diretamente elementos usando um índice
println!("Segundo nome: {}", names[1]); // Nota: Indexação direta pode causar pânico
}
Vectors são ideais para lidar com sequências de elementos do mesmo tipo, sejam eles strings, inteiros ou tipos personalizados. Eles permitem fácil adição, remoção e acesso aleatório de elementos.
Hash Maps (HashMap<K, V>)
Um hash map fornece armazenamento de chave-valor implementado usando uma tabela hash. Ele suporta busca, inserção e exclusão rápidas, tornando-se uma estrutura de dados crítica para recuperação e gerenciamento eficiente de dados.
O exemplo a seguir mostra como criar, inserir, acessar, remover e iterar sobre elementos em um hash map:
use std::collections::HashMap;
fn main() {
// Cria um hash map vazio
let mut book_reviews: HashMap = HashMap::new();
// Adiciona elementos ao hash map
book_reviews.insert("The Hobbit".to_string(), "Excellent fantasy book".to_string());
book_reviews.insert("The Catcher in the Rye".to_string(), "Classic novel".to_string());
// Acessa elementos no hash map
if let Some(review) = book_reviews.get("The Hobbit") {
println!("Review de The Hobbit: {}", review);
}
// Remove elementos do hash map
book_reviews.remove("The Catcher in the Rye");
// Itera sobre o hash map
for (book, review) in &book_reviews {
println!("{}: {}", book, review);
}
// Atualiza elementos no hash map
book_reviews.entry("The Hobbit".to_string()).or_insert("No review found".to_string());
book_reviews.entry("1984".to_string()).or_insert("Dystopian science fiction".to_string());
let mut scores = HashMap::new();
// Insere diretamente usando `insert`
scores.insert("Blue", 10);
scores.insert("Blue", 25); // Sobrescreve o valor anterior
// Usa `entry` para atualizar ou inserir
scores.entry("Yellow").or_insert(50); // Insere porque "Yellow" não existe
scores.entry("Blue").or_insert(50); // Não faz nada porque "Blue" já existe
// Resultado: {"Blue": 25, "Yellow": 50}
// Verifica se uma chave existe
if book_reviews.contains_key("1984") {
println!("Review para 1984 está disponível.");
}
}
Hash maps são úteis quando você precisa acessar dados rapidamente usando chaves, como em indexação de banco de dados e implementações de cache. Eles oferecem associações chave-valor flexíveis, tornando a organização e recuperação de dados simples e eficientes.
Hash Sets (HashSet<T>)
Um hash set é uma coleção não ordenada que armazena elementos únicos. Ele é implementado usando uma tabela hash, fornecendo operações rápidas de busca, inserção e exclusão.
No exemplo abaixo, vemos como criar, adicionar, remover, verificar a existência e iterar sobre elementos em um hash set, além de realizar operações de conjunto como união, interseção e diferença:
use std::collections::HashSet;
fn main() {
// Cria um set vazio
let mut numbers = HashSet::new();
// Adiciona elementos ao set
numbers.insert(1);
numbers.insert(2);
numbers.insert(3);
// Remove um elemento do set
numbers.remove(&3);
// Verifica se um elemento existe no set
if numbers.contains(&1) {
println!("1 está no set");
}
// Itera sobre o set
for number in &numbers {
println!("{}", number);
}
// Operações de conjunto: união, interseção, diferença, diferença simétrica
// Neste ponto, numbers contém {1, 2}
let other_numbers: HashSet = [2, 3, 4].iter().cloned().collect::>();
// other_numbers contém {2, 3, 4}
let union: HashSet = numbers.union(&other_numbers).cloned().collect::>();
println!("União: {:?}", union);
// União: `{1, 2, 3, 4}` (todos os elementos únicos de ambos os sets)
let intersection: HashSet = numbers.intersection(&other_numbers).cloned().collect::>();
println!("Interseção: {:?}", intersection);
// Interseção: `{2}` (elementos comuns)
let difference: HashSet = numbers.difference(&other_numbers).cloned().collect::>();
println!("Diferença: {:?}", difference);
// Diferença: `{1}` (elementos em `numbers` mas não em `other_numbers`)
let symmetric_difference: HashSet = numbers.symmetric_difference(&other_numbers).cloned().collect::>();
println!("Diferença Simétrica: {:?}", symmetric_difference);
// Diferença Simétrica: `{1, 3, 4}` (elementos únicos para cada set)
}
Hash sets são particularmente úteis para lidar com coleções de elementos únicos, como listas de ID de usuário e registros sob condições específicas. Operações de conjunto como união, interseção e diferença fornecem ferramentas poderosas para lidar com dados de coleção de forma eficiente.
Outras Data Structures em Rust
Além das estruturas de dados mais comuns, Rust oferece outras opções que podem ser mais adequadas para casos de uso específicos.
Lista Duplamente Ligada (LinkedList<T>)
LinkedList<T> é uma lista duplamente ligada fornecida pela biblioteca padrão do Rust. Comparada aos vectors (Vec<T>), listas ligadas permitem inserção e exclusão eficientes de elementos, especialmente no início ou no final da lista. No entanto, elas têm um desempenho ruim em acesso aleatório.
O código a seguir demonstra como criar, adicionar, remover, iterar e modificar elementos em uma lista duplamente ligada:
use std::collections::LinkedList;
fn main() {
// Cria uma nova lista ligada vazia
let mut list: LinkedList = LinkedList::new();
// Adiciona elementos ao final da lista
list.push_back(1);
list.push_back(2);
// Adiciona elementos ao início da lista
list.push_front(0);
// Remove elementos do início e do final da lista
assert_eq!(list.pop_front(), Some(0));
assert_eq!(list.pop_back(), Some(2));
// Itera sobre a lista
for elem in list.iter() {
println!("{}", elem);
}
// Modifica elementos na lista (requer usar um iterador)
let mut iter_mut = list.iter_mut();
if let Some(first_elem) = iter_mut.next() {
*first_elem = 3;
}
// Imprime a lista modificada
println!("Lista modificada: {:?}", list);
}
Quando adições ou exclusões frequentes no início ou no final de uma lista são necessárias, LinkedList é uma boa escolha, pois essas operações têm uma complexidade de tempo de O(1).
Se sua aplicação raramente precisa de acesso aleatório e se concentra mais na travessia sequencial, uma lista ligada pode ser uma opção melhor do que um vector.
Mapa B-Tree (BTreeMap<K, V>)
BTreeMap<K, V> é uma coleção de chave-valor implementada usando uma B-tree. Ela mantém as chaves em ordem classificada. Comparado aos hash maps (HashMap<K, V>), BTreeMap se destaca quando chaves ordenadas, buscas de intervalo ou travessias ordenadas são necessárias.
O exemplo abaixo mostra como criar, inserir, acessar, remover, iterar e realizar consultas de intervalo em um mapa B-tree:
use std::collections::BTreeMap;
fn main() {
// Cria um novo BTreeMap vazio
let mut map: BTreeMap = BTreeMap::new();
// Insere pares de chave-valor no BTreeMap
map.insert("apple".to_string(), 3);
map.insert("banana".to_string(), 2);
map.insert("pear".to_string(), 4);
// Recupera o valor correspondente a uma chave
if let Some(v) = map.get("apple") {
println!("apple: {}", v);
}
// Remove um par de chave-valor
map.remove("banana");
// Itera sobre o BTreeMap
for (key, value) in &map {
println!("{}: {}", key, value);
}
// Consulta de intervalo: obtém todos os pares de chave-valor com chaves entre "apple" e "pear" (inclusive)
let range = map.range("apple".to_string()..="pear".to_string());
for (key, value) in range {
println!("Consulta de intervalo: {}: {}", key, value);
}
}
BTreeMap é uma boa opção quando um mapa automaticamente classificado é necessário, especialmente útil para consultas de intervalo e travessia ordenada.
Se seu programa frequentemente executa operações de busca, inserção e exclusão onde as chaves são naturalmente ordenadas, BTreeMap pode ser mais adequado do que HashMap, pois mantém a ordem das chaves, facilitando buscas de intervalo e travessia ordenada.
Conjunto B-Tree (BTreeSet<T>)
BTreeSet<T> é um conjunto implementado com base em uma B-tree. Ele armazena elementos únicos e os mantém em ordem classificada. Comparado a HashSet<T>, BTreeSet suporta operações ordenadas e consultas de intervalo, mas pode ser mais lento para algumas operações.
O código a seguir mostra como criar, adicionar, verificar a existência, remover, iterar e realizar consultas de intervalo em um conjunto B-tree:
use std::collections::BTreeSet;
fn main() {
// Cria um novo BTreeSet vazio
let mut set: BTreeSet = BTreeSet::new();
// Adiciona elementos ao set
set.insert(12);
set.insert(5);
set.insert(18);
// Verifica se um elemento existe
if set.contains(&12) {
println!("Set contém 12");
}
// Remove um elemento
set.remove(&5);
// Itera sobre o set (elementos estarão em ordem crescente)
for num in &set {
println!("{}", num);
}
// Consulta de intervalo: recupera todos os elementos maiores ou iguais a 10 e menores que 20
for num in set.range(10..20) {
println!("Consulta de intervalo: {}", num);
}
}
BTreeSet é uma boa escolha quando você precisa de um conjunto ordenado para buscas rápidas, consultas de intervalo ou travessia ordenada.
É adequado para cenários onde elementos únicos precisam ser armazenados e os elementos têm uma relação comparável.
Binary Heap (BinaryHeap<T>)
BinaryHeap<T> é uma implementação de uma fila de prioridade baseada em um binary heap. Ele permite a inserção rápida de elementos e a remoção do elemento máximo (ou mínimo), dependendo se é um max-heap ou min-heap. Por padrão, o BinaryHeap do Rust é um max-heap.
O exemplo abaixo demonstra como criar, adicionar, espiar o elemento máximo, remover o elemento máximo e iterar sobre um binary heap:
use std::collections::BinaryHeap;
fn main() {
// Cria um novo BinaryHeap vazio
let mut heap = BinaryHeap::new();
// Adiciona elementos ao heap
heap.push(1);
heap.push(5);
heap.push(2);
// Espia o elemento máximo no heap sem removê-lo
if let Some(max) = heap.peek() {
println!("Elemento máximo: {}", max);
}
// Remove e retorna o elemento máximo
println!("Elemento máximo removido: {}", heap.pop().unwrap());
// Itera sobre o heap (a ordem de iteração não é classificada)
for num in &heap {
println!("{}", num);
}
}
Quando uma estrutura de dados é necessária para acesso rápido e remoção do elemento máximo (ou mínimo), BinaryHeap é ideal. Isso é especialmente útil em algoritmos como o caminho mais curto de Dijkstra.
BinaryHeap é adequado para agendamento de tarefas, algoritmos gulosos ou qualquer cenário que exija uma fila de prioridade.
As data structures em Rust são ferramentas essenciais para qualquer desenvolvedor que busca eficiência e segurança no gerenciamento de dados. Seja utilizando vectors para armazenar sequências, hash maps para associações chave-valor, ou binary heaps para filas de prioridade, Rust oferece uma variedade de opções para atender às necessidades de cada projeto. E para hospedar seus projetos Rust com a melhor plataforma serverless, conte com a Leapcell, que oferece suporte multi-linguagem, escalabilidade无阻力 e alta performance. Explore a documentação e comece a construir hoje mesmo!
Este conteúdo foi auxiliado por Inteligência Artificiado, mas escrito e revisado por um humano.
Via dev.to