Estruturas de dados são fundamentais em qualquer linguagem de programação. Zig oferece contêineres eficientes na biblioteca padrão, com controle explícito de memória e performance previsível. Neste guia, vamos explorar as principais estruturas de dados de Zig: desde arrays estáticos até HashMaps dinâmicos.
Arrays em Zig
Arrays Estáticos
Arrays em Zig têm tamanho conhecido em tempo de compilação:
const std = @import("std");
pub fn main() void {
// Array com tamanho e tipo explícitos
const numeros = [5]i32{ 1, 2, 3, 4, 5 };
// Zig pode inferir o tamanho
const letras = [_]u8{ 'a', 'b', 'c' };
// Acesso por índice
std.debug.print("Primeiro: {}\n", .{numeros[0]});
std.debug.print("Último: {}\n", .{numeros[4]});
// Tamanho sempre disponível
std.debug.print("Tamanho: {}\n", .{numeros.len});
// Iteração
for (numeros, 0..) |num, i| {
std.debug.print("numeros[{}] = {}\n", .{ i, num });
}
}
Arrays Multidimensionais
// Matriz 3x3
const matriz = [3][3]i32{
.{ 1, 2, 3 },
.{ 4, 5, 6 },
.{ 7, 8, 9 },
};
// Acesso
const elemento = matriz[1][2]; // 6
// Iteração
for (matriz) |linha| {
for (linha) |valor| {
std.debug.print("{} ", .{valor});
}
std.debug.print("\n", .{});
}
Arrays de Tamanho Zero e Sentinela
// Array vazio
const vazio = [_]i32{};
// Array nulo-terminado (sentinela)
const string: [:0]const u8 = "Hello"; // :0 indica sentinela 0
std.debug.print("Len: {}, null-terminated\n", .{string.len});
// Útil para interoperabilidade com C
Slices
O Que São Slices?
Slices são a estrutura mais importante de Zig. São referências para uma sequência de elementos:
const array = [_]i32{ 10, 20, 30, 40, 50 };
// Slice do array inteiro
const slice: []const i32 = &array;
// Slice parcial
const parte: []const i32 = array[1..4]; // [20, 30, 40]
// Slice com sentinela
const str: [:0]const u8 = "Zig";
std.debug.print("Slice: ", .{});
for (parte) |val| {
std.debug.print("{} ", .{val});
}
std.debug.print("\n", .{});
Slices vs Arrays
| Característica | Array | Slice |
|---|---|---|
| Tamanho | Compile-time | Runtime |
| Tipo | [N]T | []T |
| Storage | Stack (geralmente) | Referência |
| Flexibilidade | Fixo | Dinâmico |
| Bounds checking | Sim | Sim |
Criando Slices
// De array
const array = [_]i32{ 1, 2, 3, 4, 5 };
const slice1: []const i32 = &array;
// De ponteiro + tamanho
const ptr: [*]const i32 = &array;
const slice2: []const i32 = ptr[0..array.len];
// Alocando slice dinamicamente
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
const allocator = gpa.allocator();
const slice3 = try allocator.alloc(i32, 100);
defer allocator.free(slice3);
// Preenchendo
for (slice3, 0..) |*item, i| {
item.* = @intCast(i32, i);
}
ArrayList
O Básico de ArrayList
std.ArrayList é o array dinâmico de Zig — cresce automaticamente quando necessário:
const std = @import("std");
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
// Criar ArrayList de i32
var lista = std.ArrayList(i32).init(allocator);
defer lista.deinit();
// Adicionar elementos
try lista.append(10);
try lista.append(20);
try lista.append(30);
std.debug.print("Tamanho: {}\n", .{lista.items.len});
std.debug.print("Capacidade: {}\n", .{lista.capacity});
// Acessar
std.debug.print("Primeiro: {}\n", .{lista.items[0]});
// Iterar
for (lista.items) |item| {
std.debug.print("{} ", .{item});
}
std.debug.print("\n", .{});
}
Operações Comuns
var lista = std.ArrayList(i32).init(allocator);
defer lista.deinit();
// Adicionar um elemento
try lista.append(42);
// Adicionar múltiplos elementos
try lista.appendSlice(&[_]i32{ 1, 2, 3 });
// Inserir no meio
try lista.insert(1, 99); // índice 1, valor 99
// Remover
const removido = lista.orderedRemove(0); // Remove índice 0, retorna valor
const ultimo = lista.pop(); // Remove e retorna último
// Buscar
if (std.mem.indexOf(i32, lista.items, 42)) |idx| {
std.debug.print("Encontrado no índice {}\n", .{idx});
}
// Limpar
lista.clearRetainingCapacity(); // Mantém capacidade
// ou
lista.clearAndFree(); // Libera memória
// Garantir capacidade
try lista.ensureTotalCapacity(1000);
ArrayList com Structs
const Pessoa = struct {
nome: []const u8,
idade: u32,
};
var pessoas = std.ArrayList(Pessoa).init(allocator);
defer {
// Se Pessoa tiver ponteiros que precisam de free, faça aqui
pessoas.deinit();
}
try pessoas.append(.{
.nome = "Alice",
.idade = 30,
});
try pessoas.append(.{
.nome = "Bob",
.idade = 25,
});
for (pessoas.items) |pessoa| {
std.debug.print("{s} tem {} anos\n", .{ pessoa.nome, pessoa.idade });
}
ArrayList de Strings
// ArrayList de strings (slices)
var nomes = std.ArrayList([]const u8).init(allocator);
defer nomes.deinit();
// Cuidado: strings precisam de lifecycle management
const nome1 = try allocator.dupe(u8, "Alice");
try nomes.append(nome1);
const nome2 = try allocator.dupe(u8, "Bob");
try nomes.append(nome2);
defer {
for (nomes.items) |nome| {
allocator.free(nome);
}
nomes.deinit();
}
ArrayList vs Slice Alocado
Quando usar cada um?
// Use ArrayList quando:
// - Precisa adicionar elementos dinamicamente
// - Tamanho é desconhecido em compile-time
var lista = std.ArrayList(i32).init(allocator);
// Use slice alocado quando:
// - Tamanho máximo é conhecido antecipadamente
const slice = try allocator.alloc(i32, 100);
defer allocator.free(slice);
HashMap
HashMap Básico
std.HashMap armazena pares chave-valor com busca O(1):
const std = @import("std");
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
// HashMap: u32 → []const u8
var map = std.HashMap(u32, []const u8, std.hash_map.defaultContext(u32), std.hash_map.defaultMaxLoadPercentage).init(allocator);
defer map.deinit();
// Inserir
try map.put(1, "Alice");
try map.put(2, "Bob");
try map.put(3, "Carol");
// Buscar
if (map.get(1)) |nome| {
std.debug.print("ID 1: {s}\n", .{nome});
}
// Verificar existência
if (map.contains(2)) {
std.debug.print("ID 2 existe\n", .{});
}
// Tamanho
std.debug.print("Tamanho: {}\n", .{map.count()});
// Remover
_ = map.remove(2);
// Iterar
var it = map.iterator();
while (it.next()) |entry| {
std.debug.print("{} → {s}\n", .{ entry.key_ptr.*, entry.value_ptr.* });
}
}
StringHashMap
Para chaves do tipo string, use StringHashMap:
// StringHashMap: string → qualquer tipo
var usuarios = std.StringHashMap(u32).init(allocator);
defer usuarios.deinit();
// Inserir
try usuarios.put("alice", 30);
try usuarios.put("bob", 25);
// Buscar
if (usuarios.get("alice")) |idade| {
std.debug.print("Alice tem {} anos\n", .{idade});
}
// Chaves são copiadas automaticamente
const chave = try allocator.dupe(u8, "carol");
try usuarios.put(chave, 35);
// Chaves são gerenciadas pelo HashMap - não dê free!
HashMap com Structs Complexos
const Usuario = struct {
nome: []const u8,
email: []const u8,
ativo: bool,
};
// HashMap: u64 (ID) → Usuario
var db = std.HashMap(u64, Usuario, std.hash_map.defaultContext(u64), std.hash_map.defaultMaxLoadPercentage).init(allocator);
defer {
// Se Usuario tem ponteiros alocados, libere aqui
db.deinit();
}
try db.put(1, .{
.nome = "Alice Silva",
.email = "alice@example.com",
.ativo = true,
});
try db.put(2, .{
.nome = "Bob Santos",
.email = "bob@example.com",
.ativo = false,
});
// Atualizar
if (db.getPtr(1)) |usuario| {
usuario.ativo = false;
}
// Entry API para upsert
const result = try db.getOrPut(3);
if (!result.found_existing) {
result.value_ptr.* = .{
.nome = "Carol",
.email = "carol@example.com",
.ativo = true,
};
}
Custom Hash e Equality
Para tipos customizados como chave:
const Ponto = struct {
x: i32,
y: i32,
// Implementar hash
pub fn hash(self: Ponto) u64 {
var hasher = std.hash.Wyhash.init(0);
std.hash.autoHash(&hasher, self.x);
std.hash.autoHash(&hasher, self.y);
return hasher.final();
}
// Implementar equality
pub fn eql(self: Ponto, other: Ponto) bool {
return self.x == other.x and self.y == other.y;
}
};
var pontos = std.HashMap(Ponto, []const u8, Ponto.hash, Ponto.eql).init(allocator);
defer pontos.deinit();
try pontos.put(.{ .x = 0, .y = 0 }, "Origem");
try pontos.put(.{ .x = 10, .y = 20 }, "Destino");
if (pontos.get(.{ .x = 0, .y = 0 })) |desc| {
std.debug.print("{s}\n", .{desc});
}
Outras Estruturas Úteis
AutoHashMap
Para usar tipos que já implementam hash e eql automaticamente:
// AutoHashMap para tipos básicos
var contador = std.AutoHashMap([]const u8, u32).init(allocator);
defer contador.deinit();
// Contar ocorrências de palavras
const texto = "a a b a c b a";
var it = std.mem.split(u8, texto, " ");
while (it.next()) |palavra| {
const result = try contador.getOrPut(palavra);
if (result.found_existing) {
result.value_ptr.* += 1;
} else {
result.key_ptr.* = try allocator.dupe(u8, palavra);
result.value_ptr.* = 1;
}
}
// Cleanup especial necessário para chaves alocadas
defer {
var it_keys = contador.keyIterator();
while (it_keys.next()) |key| {
allocator.free(key.*);
}
contador.deinit();
}
Bunyan (Binary Tree) - Não Nativo
Zig std não tem árvore binária nativa. Use bibliotecas externas ou implemente:
// Árvore binária simples (exemplo educacional)
fn BinaryTree(comptime T: type) type {
return struct {
const Node = struct {
value: T,
left: ?*Node,
right: ?*Node,
};
root: ?*Node,
allocator: std.mem.Allocator,
const Self = @This();
pub fn init(allocator: std.mem.Allocator) Self {
return .{
.root = null,
.allocator = allocator,
};
}
pub fn insert(self: *Self, value: T) !void {
const node = try self.allocator.create(Node);
node.* = .{
.value = value,
.left = null,
.right = null,
};
if (self.root == null) {
self.root = node;
return;
}
// Inserção simples (não balanceada)
var current = self.root.?;
while (true) {
if (value < current.value) {
if (current.left) |left| {
current = left;
} else {
current.left = node;
return;
}
} else {
if (current.right) |right| {
current = right;
} else {
current.right = node;
return;
}
}
}
}
};
}
PriorityQueue
// Fila de prioridade (min-heap)
var pq = std.PriorityQueue(i32, void, struct {
fn lessThan(_: void, a: i32, b: i32) std.math.Order {
return std.math.order(a, b);
}
}.lessThan).init(allocator, {});
defer pq.deinit();
try pq.add(5);
try pq.add(1);
try pq.add(3);
while (pq.removeOrNull()) |val| {
std.debug.print("{} ", .{val}); // 1, 3, 5
}
Queue (Fila)
// Fila FIFO usando std.TailQueue (lista duplamente ligada)
var fila = std.TailQueue(i32){};
// Enqueue
const node1 = try allocator.create(std.TailQueue(i32).Node);
node1.data = 10;
fila.append(node1);
const node2 = try allocator.create(std.TailQueue(i32).Node);
node2.data = 20;
fila.append(node2);
// Dequeue
if (fila.popFirst()) |node| {
std.debug.print("{}", .{node.data}); // 10
allocator.destroy(node);
}
Performance e Considerações
Comparação de Estruturas
| Estrutura | Inserção | Busca | Memória | Uso Ideal |
|---|---|---|---|---|
| Array | O(n)* | O(n) | Mínima | Tamanho fixo |
| Slice | N/A | O(n) | Referência | Passagem de dados |
| ArrayList | O(1)** | O(n) | Contígua | Lista dinâmica |
| HashMap | O(1) | O(1) | Hash table | Busca rápida |
| StringHashMap | O(1) | O(1) | Hash table | Strings como chave |
*Inserção no meio do array **Amortizado; ocasionalmente O(n) para resize
Dicas de Performance
// 1. Reserve capacidade antecipadamente
var lista = std.ArrayList(i32).init(allocator);
try lista.ensureTotalCapacity(10000); // Evita realocações
// 2. Reuse ArrayLists
defer lista.clearRetainingCapacity(); // Mantém capacidade
// 3. Prefira getPtr para modificar em vez de remove+put
if (map.getPtr(key)) |value| {
value.* = novo_valor; // O(1)
}
// vs
// const old = map.remove(key);
// try map.put(key, novo_valor); // O(n) pior caso
// 4. Use StringHashMap para strings em vez de HashMap genérico
// Mais otimizado para strings
// 5. Considere ArrayListUnmanaged se precisar de múltiplas listas
// com o mesmo allocator
Gerenciamento de Memória
// Padrão seguro para estruturas complexas
const Sistema = struct {
usuarios: std.StringHashMap(Usuario),
logs: std.ArrayList(LogEntry),
allocator: std.mem.Allocator,
pub fn init(allocator: std.mem.Allocator) Sistema {
return .{
.usuarios = std.StringHashMap(Usuario).init(allocator),
.logs = std.ArrayList(LogEntry).init(allocator),
.allocator = allocator,
};
}
pub fn deinit(self: *Sistema) void {
// Libere recursos internos primeiro
var it = self.usuarios.iterator();
while (it.next()) |entry| {
self.allocator.free(entry.key_ptr.*);
entry.value_ptr.deinit(self.allocator);
}
self.usuarios.deinit();
for (self.logs.items) |*log| {
log.deinit(self.allocator);
}
self.logs.deinit();
}
};
Exemplo Completo: Sistema de Cache
const std = @import("std");
const CacheEntry = struct {
value: []const u8,
created_at: i64,
ttl_seconds: u32,
pub fn isExpired(self: CacheEntry) bool {
const now = std.time.timestamp();
return (now - self.created_at) > self.ttl_seconds;
}
};
const Cache = struct {
data: std.StringHashMap(CacheEntry),
allocator: std.mem.Allocator,
max_size: usize,
pub fn init(allocator: std.mem.Allocator, max_size: usize) Cache {
return .{
.data = std.StringHashMap(CacheEntry).init(allocator),
.allocator = allocator,
.max_size = max_size,
};
}
pub fn deinit(self: *Cache) void {
var it = self.data.iterator();
while (it.next()) |entry| {
self.allocator.free(entry.key_ptr.*);
self.allocator.free(entry.value_ptr.*.value);
}
self.data.deinit();
}
pub fn get(self: *Cache, key: []const u8) ?[]const u8 {
const entry = self.data.getPtr(key) orelse return null;
if (entry.isExpired()) {
_ = self.remove(key);
return null;
}
return entry.value;
}
pub fn put(self: *Cache, key: []const u8, value: []const u8, ttl_seconds: u32) !void {
// Evitar estouro
if (self.data.count() >= self.max_size) {
// Estratégia simples: não adiciona (em produção: LRU)
return error.CacheFull;
}
// Liberar entrada existente se houver
if (self.data.getEntry(key)) |existing| {
self.allocator.free(existing.value_ptr.value);
}
const key_copy = try self.allocator.dupe(u8, key);
const value_copy = try self.allocator.dupe(u8, value);
const entry = CacheEntry{
.value = value_copy,
.created_at = std.time.timestamp(),
.ttl_seconds = ttl_seconds,
};
try self.data.put(key_copy, entry);
}
pub fn remove(self: *Cache, key: []const u8) bool {
if (self.data.fetchRemove(key)) |kv| {
self.allocator.free(kv.key);
self.allocator.free(kv.value.value);
return true;
}
return false;
}
pub fn cleanupExpired(self: *Cache) void {
var to_remove = std.ArrayList([]const u8).init(self.allocator);
defer to_remove.deinit();
var it = self.data.iterator();
while (it.next()) |entry| {
if (entry.value_ptr.isExpired()) {
to_remove.append(entry.key_ptr.*) catch continue;
}
}
for (to_remove.items) |key| {
_ = self.remove(key);
}
}
};
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
var cache = Cache.init(allocator, 100);
defer cache.deinit();
// Inserir valores
try cache.put("user:1", "Alice", 60); // TTL 60 segundos
try cache.put("user:2", "Bob", 60);
// Recuperar
if (cache.get("user:1")) |nome| {
std.debug.print("Usuário 1: {s}\n", .{nome});
}
// Verificar não-existente
if (cache.get("user:99") == null) {
std.debug.print("Usuário 99 não encontrado\n", .{});
}
std.debug.print("Tamanho do cache: {}\n", .{cache.data.count()});
}
Erros Comuns
1. Use-After-Free
// ❌ ERRADO
const slice = try allocator.alloc(i32, 10);
allocator.free(slice);
slice[0] = 42; // Use-after-free!
// ✅ CERTO
const slice = try allocator.alloc(i32, 10);
defer allocator.free(slice);
slice[0] = 42; // OK
2. Esquecer de Liberar HashMap Keys
// ❌ ERRADO
var map = std.StringHashMap(i32).init(allocator);
try map.put(try allocator.dupe(u8, "key"), 42);
map.deinit(); // Memory leak das keys!
// ✅ CERTO
defer {
var it = map.keyIterator();
while (it.next()) |key| allocator.free(key.*);
map.deinit();
}
3. Modificar Durante Iteração
// ❌ ERRADO
for (lista.items) |item| {
try lista.append(item * 2); // Modifica durante iteração!
}
// ✅ CERTO
const len = lista.items.len;
var i: usize = 0;
while (i < len) : (i += 1) {
try lista.append(lista.items[i] * 2);
}
Próximos Passos
Agora que você domina as estruturas de dados de Zig:
- Zig HTTP Client — Use ArrayList para buffers dinâmicos
- Zig HTTP Server — HashMap para rotas, ArrayList para handlers
- Gerenciamento de Memória — Aprofunde allocators
- Tratamento de Erros — Estratégias com collections
Estruturas de dados eficientes são a base de código performático. Pratique com projetos reais!