--- title: "Arrays e Vec\u003cT\u003e: Estruturas Contíguas em Rust" url: "https://rustlang.com.br/estruturas-dados/array-vec/" markdown_url: "https://rustlang.com.br/estruturas-dados/array-vec.MD" description: "Guia completo sobre arrays de tamanho fixo [T; N] e vetores dinâmicos Vec\u003cT\u003e em Rust, incluindo layout de memória, estratégias de crescimento, slices e padrões com iteradores." date: "" author: "Equipe Rust Brasil" --- # Arrays e Vec: Estruturas Contíguas em Rust Guia completo sobre arrays de tamanho fixo [T; N] e vetores dinâmicos Vec em Rust, incluindo layout de memória, estratégias de crescimento, slices e padrões com iteradores. ## Introdução Arrays e vetores são as estruturas de dados mais fundamentais em qualquer linguagem de programação. Em Rust, temos duas formas principais de armazenar sequências contíguas de elementos: os **arrays de tamanho fixo** `[T; N]` e os **vetores dinâmicos** `Vec`. Compreender profundamente essas estruturas é essencial, pois elas formam a base sobre a qual muitas outras estruturas são construídas — pilhas, filas, heaps e até tabelas hash utilizam vetores internamente. A grande vantagem dessas estruturas é a **localidade de memória**: como os elementos ficam lado a lado na memória, o acesso sequencial é extremamente eficiente, aproveitando ao máximo as linhas de cache do processador. Essa propriedade torna arrays e vetores a escolha padrão para a maioria dos casos de uso em programação de sistemas. Neste artigo, exploraremos desde os conceitos teóricos até implementações práticas, incluindo um pipeline completo de processamento de dados CSV. --- ## Conceito e Teoria ### Array `[T; N]` — Tamanho Fixo Um array em Rust é uma coleção de tamanho fixo, determinado em tempo de compilação. Todos os elementos possuem o mesmo tipo `T` e o tamanho `N` faz parte do tipo. ``` Array [i32; 5] na Stack ┌─────────────────────────────────────────┐ │ Endereço base: 0x7FFE_1000 │ ├────────┬────────┬────────┬────────┬────────┤ │ [0] │ [1] │ [2] │ [3] │ [4] │ │ 10 │ 20 │ 30 │ 40 │ 50 │ │ 4bytes │ 4bytes │ 4bytes │ 4bytes │ 4bytes │ ├────────┴────────┴────────┴────────┴────────┤ │ Total: 5 × 4 = 20 bytes na stack │ └─────────────────────────────────────────┘ Acesso a [i]: endereço_base + i × tamanho_elemento Exemplo [3]: 0x7FFE_1000 + 3 × 4 = 0x7FFE_100C ``` ### Vec — Vetor Dinâmico O `Vec` é composto por três campos armazenados na stack, enquanto os dados residem na heap: ``` Stack Heap ┌──────────────────┐ ┌────────────────────────────────────────┐ │ Vec │ │ Endereço: 0x5596_A000 │ │ ┌──────────────┐ │ ├────────┬────────┬────────┬────────┬───┤ │ │ ptr ─────────┼─┼────────► │ 10 │ 20 │ 30 │ ???? │ │ │ ├──────────────┤ │ │ usado │ usado │ usado │ livre │ │ │ │ len: 3 │ │ ├────────┴────────┴────────┴────────┴───┤ │ ├──────────────┤ │ │ Capacidade alocada: 4 elementos │ │ │ capacity: 4 │ │ └────────────────────────────────────────┘ │ └──────────────┘ │ │ (24 bytes: 3×8) │ └──────────────────┘ ``` ### Estratégia de Crescimento do Vec Quando o `len` atinge o `capacity`, o Vec precisa realocar. A estratégia padrão do Rust é **dobrar a capacidade**: ``` Inserções sucessivas com push(): Estado 1: cap=1, len=1 [10] Estado 2: cap=2, len=2 [10][20] ← realocou (cap 1→2) Estado 3: cap=4, len=3 [10][20][30][ ] ← realocou (cap 2→4) Estado 4: cap=4, len=4 [10][20][30][40] Estado 5: cap=8, len=5 [10][20][30][40][50][ ][ ][ ] ← realocou (cap 4→8) Custo amortizado de push: O(1) Pior caso individual: O(n) quando precisa realocar e copiar tudo ``` ### Slices: `&[T]` e `&mut [T]` Slices são **visualizações** (views) sobre uma sequência contígua de memória. Elas não possuem os dados — apenas referenciam uma região de um array ou Vec: ``` let v = vec![10, 20, 30, 40, 50]; let fatia = &v[1..4]; Vec Slice &[i32] ┌─────┐ ┌───┬───┬───┬───┬───┐ ┌─────────┐ │ ptr─┼────►│10 │20 │30 │40 │50 │◄──┼─┤ ptr │ │len=5│ └───┴─▲─┴───┴───┴───┘ │ ├─────────┤ │cap=5│ │ │ │ len = 3 │ └─────┘ └──────────────────┘ └─────────┘ aponta para v[1] fatia = [20, 30, 40] ``` --- ## Complexidade | Operação | Array `[T; N]` | Vec | Notas | |-------------------------------|----------------|-----------------|------------------------------------------| | Acesso por índice `v[i]` | O(1) | O(1) | Cálculo direto de endereço | | Busca (elemento arbitrário) | O(n) | O(n) | Busca linear; O(log n) se ordenado | | Inserção no final (`push`) | — | O(1) amortizado | O(n) no pior caso (realocação) | | Remoção do final (`pop`) | — | O(1) | Sem necessidade de mover elementos | | Inserção no início/meio | O(n) | O(n) | Precisa deslocar elementos | | Remoção do início/meio | O(n) | O(n) | Precisa deslocar elementos | | `contains` / busca linear | O(n) | O(n) | Percorre todos os elementos | | Ordenação (`sort`) | O(n log n) | O(n log n) | Usa padrão TimSort (estável) | --- ## Implementação em Rust ### Operações Básicas com Arrays ```rust fn demonstrar_arrays() { // Declaração de array com tipo e tamanho explícitos let notas: [f64; 5] = [7.5, 8.0, 9.2, 6.8, 7.0]; // Array inicializado com valor padrão (todos iguais) let zeros: [i32; 10] = [0; 10]; // Acesso por índice (verificado em tempo de execução) let primeira_nota = notas[0]; println!("Primeira nota: {}", primeira_nota); // Iteração com enumerate for (i, nota) in notas.iter().enumerate() { println!("Aluno {}: {:.1}", i + 1, nota); } // Tamanho do array println!("Total de alunos: {}", notas.len()); // Slicing — criando uma fatia let tres_primeiras = ¬as[0..3]; println!("Três primeiras notas: {:?}", tres_primeiras); // Arrays suportam pattern matching match notas { [primeiro, .., ultimo] => { println!("Primeira: {}, Última: {}", primeiro, ultimo); } } // Média usando iteradores let soma: f64 = notas.iter().sum(); let media = soma / notas.len() as f64; println!("Média da turma: {:.2}", media); println!("Zeros: {:?}", zeros); } ``` ### Operações com Vec ```rust fn demonstrar_vec() { // Criação com macro vec! let mut frutas = vec!["maçã", "banana", "laranja"]; // Criação com capacidade pré-alocada (evita realocações) let mut numeros: Vec = Vec::with_capacity(100); println!("Len: {}, Capacidade: {}", numeros.len(), numeros.capacity()); // Inserção no final — O(1) amortizado numeros.push(10); numeros.push(20); numeros.push(30); // Remoção do final — O(1) if let Some(ultimo) = numeros.pop() { println!("Removido: {}", ultimo); // 30 } // Inserção em posição específica — O(n) frutas.insert(1, "manga"); // ["maçã", "manga", "banana", "laranja"] // Remoção por índice — O(n) let removida = frutas.remove(2); // remove "banana" println!("Fruta removida: {}", removida); // swap_remove — O(1), mas não preserva ordem frutas.push("uva"); frutas.push("pêra"); println!("Antes do swap_remove: {:?}", frutas); frutas.swap_remove(0); // troca o primeiro pelo último e remove println!("Após swap_remove(0): {:?}", frutas); // Busca if frutas.contains(&"manga") { println!("Temos manga!"); } // Encontrar posição if let Some(pos) = frutas.iter().position(|&f| f == "uva") { println!("Uva está na posição: {}", pos); } // Ordenação let mut valores = vec![42, 17, 93, 5, 28, 61]; valores.sort(); // ordenação estável println!("Ordenado: {:?}", valores); // Deduplicação (requer ordenação prévia) let mut com_duplicatas = vec![3, 1, 4, 1, 5, 9, 2, 6, 5, 3]; com_duplicatas.sort(); com_duplicatas.dedup(); println!("Sem duplicatas: {:?}", com_duplicatas); // Redimensionamento let mut buffer = vec![0u8; 10]; buffer.resize(20, 0xFF); // expande preenchendo com 0xFF println!("Buffer: {:?}", buffer); } ``` ### Padrões com Iteradores ```rust fn demonstrar_iteradores() { let numeros = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; // map — transformar cada elemento let dobrados: Vec = numeros.iter().map(|&x| x * 2).collect(); println!("Dobrados: {:?}", dobrados); // filter — selecionar elementos let pares: Vec<&i32> = numeros.iter().filter(|&&x| x % 2 == 0).collect(); println!("Pares: {:?}", pares); // fold — reduzir a um único valor (soma) let soma = numeros.iter().fold(0, |acumulador, &x| acumulador + x); println!("Soma: {}", soma); // Encadear operações: filtrar pares, dobrar e somar let resultado: i32 = numeros .iter() .filter(|&&x| x % 2 == 0) // [2, 4, 6, 8, 10] .map(|&x| x * 2) // [4, 8, 12, 16, 20] .sum(); // 60 println!("Pares dobrados somados: {}", resultado); // chunks — dividir em pedaços let dados = vec![1, 2, 3, 4, 5, 6, 7, 8, 9]; for (i, pedaco) in dados.chunks(3).enumerate() { println!("Lote {}: {:?}", i, pedaco); } // windows — janelas deslizantes let precos = vec![100, 102, 98, 105, 110, 108]; println!("Médias móveis (janela 3):"); for janela in precos.windows(3) { let media: f64 = janela.iter().sum::() as f64 / 3.0; println!(" {:?} → média = {:.1}", janela, media); } // flat_map — achatar estruturas aninhadas let frases = vec!["olá mundo", "rust é incrível"]; let palavras: Vec<&str> = frases.iter().flat_map(|f| f.split_whitespace()).collect(); println!("Palavras: {:?}", palavras); // zip — combinar dois iteradores let nomes = vec!["Ana", "Bruno", "Clara"]; let idades = vec![25, 30, 28]; let pessoas: Vec<(&str, &i32)> = nomes.iter().zip(idades.iter()).collect(); println!("Pessoas: {:?}", pessoas); // any e all — predicados let tem_negativo = numeros.iter().any(|&x| x < 0); let todos_positivos = numeros.iter().all(|&x| x > 0); println!("Tem negativo? {} | Todos positivos? {}", tem_negativo, todos_positivos); } ``` --- ## Métodos Principais ### Array `[T; N]` | Método / Operação | Descrição | |----------------------|------------------------------------------------| | `len()` | Retorna o número de elementos (sempre `N`) | | `iter()` | Retorna um iterador sobre referências | | `iter_mut()` | Retorna um iterador mutável | | `contains(&val)` | Verifica se o valor está presente | | `sort()` | Ordena os elementos in-place | | `reverse()` | Inverte a ordem dos elementos | | `[i..j]` | Cria uma slice (fatia) do array | | `map(f)` | Aplica uma função a cada elemento (Rust 1.55+) | ### Vec | Método | Descrição | |-----------------------|--------------------------------------------------| | `Vec::new()` | Cria um vetor vazio | | `Vec::with_capacity(n)` | Cria com capacidade pré-alocada | | `push(val)` | Adiciona ao final — O(1) amortizado | | `pop()` | Remove do final — O(1), retorna `Option` | | `insert(i, val)` | Insere na posição `i` — O(n) | | `remove(i)` | Remove da posição `i` — O(n) | | `swap_remove(i)` | Remove trocando pelo último — O(1) | | `retain(f)` | Mantém apenas elementos que satisfazem `f` | | `truncate(n)` | Reduz o tamanho para `n` elementos | | `drain(range)` | Remove e retorna elementos do intervalo | | `split_off(i)` | Divide o vetor na posição `i` | | `extend(iter)` | Adiciona elementos de um iterador | | `shrink_to_fit()` | Reduz a capacidade ao tamanho atual | --- ## Exemplo Prático: Pipeline de Processamento de Dados CSV Vamos implementar um sistema realista que lê dados de vendas em formato CSV, processa com iteradores e gera relatórios agregados. ```rust use std::fmt; /// Representa um registro de venda #[derive(Debug, Clone)] struct Venda { data: String, produto: String, categoria: String, quantidade: u32, preco_unitario: f64, regiao: String, } impl Venda { /// Calcula o valor total da venda fn valor_total(&self) -> f64 { self.quantidade as f64 * self.preco_unitario } } /// Relatório de vendas por categoria #[derive(Debug)] struct RelatorioCategoria { categoria: String, total_vendas: f64, quantidade_registros: usize, ticket_medio: f64, } impl fmt::Display for RelatorioCategoria { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { write!( f, "| {:<15} | R$ {:>10.2} | {:>6} registros | Ticket médio: R$ {:>8.2} |", self.categoria, self.total_vendas, self.quantidade_registros, self.ticket_medio ) } } /// Analisa uma linha CSV e retorna uma Venda fn parsear_linha_csv(linha: &str) -> Option { let campos: Vec<&str> = linha.split(',').map(|c| c.trim()).collect(); if campos.len() != 6 { return None; } Some(Venda { data: campos[0].to_string(), produto: campos[1].to_string(), categoria: campos[2].to_string(), quantidade: campos[3].parse().ok()?, preco_unitario: campos[4].parse().ok()?, regiao: campos[5].to_string(), }) } /// Gera relatório agrupado por categoria usando apenas Vec e iteradores fn gerar_relatorio_por_categoria(vendas: &[Venda]) -> Vec { // Coleta todas as categorias únicas let mut categorias: Vec = vendas.iter().map(|v| v.categoria.clone()).collect(); categorias.sort(); categorias.dedup(); // Para cada categoria, calcula as métricas categorias .into_iter() .map(|cat| { let vendas_categoria: Vec<&Venda> = vendas.iter().filter(|v| v.categoria == cat).collect(); let total: f64 = vendas_categoria.iter().map(|v| v.valor_total()).sum(); let qtd = vendas_categoria.len(); let ticket = if qtd > 0 { total / qtd as f64 } else { 0.0 }; RelatorioCategoria { categoria: cat, total_vendas: total, quantidade_registros: qtd, ticket_medio: ticket, } }) .collect() } /// Encontra os N produtos mais vendidos (por valor total) fn top_produtos(vendas: &[Venda], n: usize) -> Vec<(String, f64)> { // Agrupa por produto let mut produtos: Vec = vendas.iter().map(|v| v.produto.clone()).collect(); produtos.sort(); produtos.dedup(); let mut ranking: Vec<(String, f64)> = produtos .into_iter() .map(|prod| { let total: f64 = vendas .iter() .filter(|v| v.produto == prod) .map(|v| v.valor_total()) .sum(); (prod, total) }) .collect(); // Ordena por valor total decrescente ranking.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap()); // Retorna apenas os N primeiros ranking.into_iter().take(n).collect() } fn main() { // Simulando dados CSV (em produção, viria de um arquivo) let dados_csv = vec![ "2024-01-15, Notebook Dell, Eletrônicos, 2, 4500.00, Sudeste", "2024-01-15, Cadeira Gamer, Móveis, 5, 1200.00, Sul", "2024-01-16, Mouse Logitech, Eletrônicos, 15, 150.00, Sudeste", "2024-01-16, Mesa Escritório, Móveis, 3, 800.00, Nordeste", "2024-01-17, Monitor 27pol, Eletrônicos, 8, 2200.00, Sudeste", "2024-01-17, Teclado Mecânico, Eletrônicos, 20, 350.00, Sul", "2024-01-18, Sofá 3 Lugares, Móveis, 2, 3500.00, Sudeste", "2024-01-18, Webcam HD, Eletrônicos, 12, 280.00, Centro-Oeste", "2024-01-19, Estante Livros, Móveis, 4, 650.00, Nordeste", "2024-01-19, SSD 1TB, Eletrônicos, 25, 420.00, Sudeste", "2024-01-20, Cadeira Gamer, Móveis, 3, 1200.00, Norte", "2024-01-20, Notebook Dell, Eletrônicos, 1, 4500.00, Nordeste", ]; // Pipeline de processamento usando iteradores let vendas: Vec = dados_csv .iter() .filter_map(|linha| parsear_linha_csv(linha)) .collect(); println!("══════════════════════════════════════════════════════"); println!(" RELATÓRIO DE VENDAS - JANEIRO 2024 "); println!("══════════════════════════════════════════════════════\n"); // Resumo geral let total_geral: f64 = vendas.iter().map(|v| v.valor_total()).sum(); let total_itens: u32 = vendas.iter().map(|v| v.quantidade).sum(); println!("Total de registros: {}", vendas.len()); println!("Total de itens vendidos: {}", total_itens); println!("Valor total: R$ {:.2}\n", total_geral); // Relatório por categoria println!("─── Por Categoria ───────────────────────────────────"); let relatorio = gerar_relatorio_por_categoria(&vendas); for r in &relatorio { println!("{}", r); } // Top 5 produtos println!("\n─── Top 5 Produtos ──────────────────────────────────"); for (i, (produto, valor)) in top_produtos(&vendas, 5).iter().enumerate() { println!(" {}º {:<20} R$ {:.2}", i + 1, produto, valor); } // Vendas por região usando chunks para exibição paginada println!("\n─── Vendas por Região (paginado) ────────────────────"); let vendas_por_pagina = 4; for (pagina, grupo) in vendas.chunks(vendas_por_pagina).enumerate() { println!(" Página {}:", pagina + 1); for v in grupo { println!( " {} | {:<20} | {} un. | R$ {:.2}", v.data, v.produto, v.quantidade, v.valor_total() ); } } // Filtro avançado: vendas acima de R$ 5000 na região Sudeste println!("\n─── Vendas > R$ 5000 no Sudeste ─────────────────────"); let grandes_vendas_sudeste: Vec<&Venda> = vendas .iter() .filter(|v| v.regiao == "Sudeste" && v.valor_total() > 5000.0) .collect(); if grandes_vendas_sudeste.is_empty() { println!(" Nenhuma venda encontrada com esses critérios."); } else { for v in &grandes_vendas_sudeste { println!( " {} — {} — R$ {:.2}", v.data, v.produto, v.valor_total() ); } } } ``` --- ## Comparação com Outras Estruturas | Critério | Array/Vec | LinkedList | VecDeque | |--------------------------|--------------------|------------------|--------------------| | Acesso por índice | O(1) | O(n) | O(1) | | Inserção no final | O(1) amortizado | O(1) | O(1) amortizado | | Inserção no início | O(n) | O(1) | O(1) amortizado | | Inserção no meio | O(n) | O(1)* | O(n) | | Localidade de cache | Excelente | Ruim | Boa | | Uso de memória | Compacto | Alto (ponteiros) | Compacto | | Flexibilidade de tamanho | Vec: sim, Array: não | Sim | Sim | > *A inserção no meio de uma LinkedList é O(1) **se já temos o ponteiro**. Encontrar a posição > ainda é O(n). ### Quando usar Array/Vec? - **Use array `[T; N]`** quando o tamanho é conhecido em tempo de compilação e é relativamente pequeno (cabe na stack). - **Use `Vec`** na grande maioria dos casos — é a estrutura padrão para coleções dinâmicas. - **Prefira `Vec` sobre `LinkedList`** quase sempre: a localidade de cache compensa a complexidade teórica pior de inserções. - **Use `Vec::with_capacity(n)`** quando souber o tamanho aproximado — evita realocações desnecessárias. - **Considere `VecDeque`** apenas se precisa de inserções/remoções eficientes em ambas as extremidades. --- ## Exercícios ### Exercício 1: Estatísticas de um Vetor Implemente uma função `estatisticas(dados: &[f64]) -> (f64, f64, f64)` que retorna a **média**, a **mediana** e o **desvio padrão** de um vetor de números. Não utilize bibliotecas externas. **Dica:** Para a mediana, lembre-se de ordenar uma cópia do vetor. Para vetores de tamanho par, a mediana é a média dos dois valores centrais. ### Exercício 2: Merge de Vetores Ordenados Implemente uma função `merge_ordenado(a: &[i32], b: &[i32]) -> Vec` que recebe dois vetores já ordenados e retorna um novo vetor ordenado contendo todos os elementos de ambos. A complexidade deve ser O(n + m), onde n e m são os tamanhos dos vetores de entrada. ### Exercício 3: Rotação de Vetor Implemente uma função `rotacionar(v: &mut Vec, k: usize)` que rotaciona o vetor `k` posições para a direita **in-place**. Por exemplo: `[1, 2, 3, 4, 5]` rotacionado 2 posições resulta em `[4, 5, 1, 2, 3]`. Tente fazer com complexidade O(n) de tempo e O(1) de espaço adicional, utilizando a técnica de três reversões. --- ## Conclusão Arrays e `Vec` são os alicerces da programação em Rust. Sua memória contígua oferece desempenho excepcional para a maioria dos cenários, e o sistema de ownership do Rust garante segurança de memória sem custo em tempo de execução. **Pontos-chave a lembrar:** 1. **Arrays** são para tamanhos fixos e conhecidos em compilação; vivem na stack. 2. **Vec** é a escolha padrão para coleções dinâmicas — use `with_capacity` quando possível. 3. **Slices** (`&[T]`) são a forma idiomática de passar sequências para funções. 4. **Iteradores** são a forma preferida de processar dados — são preguiçosos, seguros e eficientes. 5. A **localidade de cache** faz com que Vec supere LinkedList na prática, mesmo em cenários onde a teoria favorece listas ligadas. Domine essas estruturas e você terá uma base sólida para todas as outras estruturas de dados em Rust.