std.SegmentedList — Lista Segmentada
O std.SegmentedList é uma estrutura de dados que combina as vantagens de arrays e listas encadeadas. Diferente do ArrayList, que realoca e copia todo o bloco quando precisa crescer, a SegmentedList aloca novos segmentos separados. Isso garante que ponteiros para elementos existentes nunca são invalidados após inserções — uma propriedade chamada de estabilidade de ponteiros, fundamental quando outros componentes mantêm referências para os dados.
Visão Geral
const std = @import("std");
const SegmentedList = std.SegmentedList;
Tipo e Assinatura
pub fn SegmentedList(comptime T: type, comptime prealloc_item_count: usize) type
O parâmetro prealloc_item_count define o número de itens pré-alocados inline (sem alocação dinâmica). Segmentos adicionais são alocados conforme necessário, com tamanhos que crescem exponencialmente.
Como Funciona
A lista é organizada em segmentos de tamanho crescente:
- Segmento 0:
prealloc_item_countitens (inline) - Segmento 1: 1 item
- Segmento 2: 2 itens
- Segmento 3: 4 itens
- Segmento 4: 8 itens
- E assim por diante…
Os segmentos são alocados independentemente, de forma que crescer a lista nunca move os dados existentes.
Funções Principais
Criação e Destruição
// Cria lista vazia
pub fn init(allocator: Allocator) Self // se prealloc > 0
pub fn initEmpty() Self // se prealloc == 0
// Libera toda a memória
pub fn deinit(self: *Self) void
Inserção e Acesso
// Adiciona um elemento ao final
pub fn append(self: *Self, item: T) Allocator.Error!void
// Adiciona e retorna ponteiro para o novo elemento
pub fn addOne(self: *Self) Allocator.Error!*T
// Acesso por índice (retorna ponteiro estável)
pub fn at(self: Self, index: usize) *T
// Acesso sem checagem de limites
pub fn uncheckedAt(self: Self, index: usize) *T
// Número de elementos
pub fn count(self: Self) usize // via self.len
Iteração
// Retorna iterador
pub fn iterator(self: *Self, start: usize) Iterator
// Iterador const
pub fn constIterator(self: *const Self, start: usize) ConstIterator
Exemplo 1: Grafo com Ponteiros Estáveis
const std = @import("std");
const No = struct {
valor: i32,
vizinhos: std.ArrayList(*No),
fn init(valor: i32, allocator: std.mem.Allocator) No {
return .{
.valor = valor,
.vizinhos = std.ArrayList(*No).init(allocator),
};
}
fn deinit(self: *No) void {
self.vizinhos.deinit();
}
};
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
// SegmentedList garante que ponteiros permanecem válidos
var nos = std.SegmentedList(No, 4){};
defer {
var i: usize = 0;
while (i < nos.len) : (i += 1) {
nos.at(i).deinit();
}
nos.deinit(allocator);
}
// Adiciona nós — ponteiros permanecem estáveis
for (0..5) |val| {
try nos.append(allocator, No.init(@intCast(val), allocator));
}
// Cria conexões usando ponteiros diretos (seguros!)
try nos.at(0).vizinhos.append(nos.at(1));
try nos.at(0).vizinhos.append(nos.at(2));
try nos.at(1).vizinhos.append(nos.at(3));
try nos.at(2).vizinhos.append(nos.at(4));
const stdout = std.io.getStdOut().writer();
try stdout.writeAll("Grafo (lista de adjacência):\n");
var i: usize = 0;
while (i < nos.len) : (i += 1) {
const no = nos.at(i);
try stdout.print(" Nó {d} -> ", .{no.valor});
for (no.vizinhos.items) |vizinho| {
try stdout.print("{d} ", .{vizinho.valor});
}
try stdout.print("\n", .{});
}
}
Exemplo 2: Pool de Objetos
const std = @import("std");
const Entidade = struct {
id: u32,
nome: [32]u8,
nome_len: usize,
ativa: bool,
fn criar(id: u32, nome: []const u8) Entidade {
var e: Entidade = .{
.id = id,
.nome = [_]u8{0} ** 32,
.nome_len = nome.len,
.ativa = true,
};
@memcpy(e.nome[0..nome.len], nome);
return e;
}
};
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
var pool = std.SegmentedList(Entidade, 8){};
defer pool.deinit(allocator);
// Cria entidades
try pool.append(allocator, Entidade.criar(1, "Jogador"));
try pool.append(allocator, Entidade.criar(2, "Inimigo"));
try pool.append(allocator, Entidade.criar(3, "NPC"));
// Referências diretas permanecem válidas mesmo após mais inserções
const jogador_ptr = pool.at(0);
// Mais inserções não invalidam jogador_ptr
try pool.append(allocator, Entidade.criar(4, "Item"));
try pool.append(allocator, Entidade.criar(5, "Projetil"));
// jogador_ptr ainda é válido!
const stdout = std.io.getStdOut().writer();
try stdout.print("Jogador: id={d}, nome={s}\n", .{
jogador_ptr.id,
jogador_ptr.nome[0..jogador_ptr.nome_len],
});
// Desativa uma entidade
pool.at(1).ativa = false;
try stdout.writeAll("\nEntidades ativas:\n");
var i: usize = 0;
while (i < pool.len) : (i += 1) {
const e = pool.at(i);
if (e.ativa) {
try stdout.print(" [{d}] {s}\n", .{
e.id,
e.nome[0..e.nome_len],
});
}
}
}
Exemplo 3: Construtor de AST
const std = @import("std");
const Expr = union(enum) {
numero: i64,
soma: struct { esq: *const Expr, dir: *const Expr },
mult: struct { esq: *const Expr, dir: *const Expr },
fn avaliar(self: *const Expr) i64 {
return switch (self.*) {
.numero => |n| n,
.soma => |s| s.esq.avaliar() + s.dir.avaliar(),
.mult => |m| m.esq.avaliar() * m.dir.avaliar(),
};
}
};
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
// SegmentedList como arena para nós da AST
var nos = std.SegmentedList(Expr, 16){};
defer nos.deinit(allocator);
// Constrói: (2 + 3) * 4
try nos.append(allocator, .{ .numero = 2 }); // índice 0
try nos.append(allocator, .{ .numero = 3 }); // índice 1
try nos.append(allocator, .{ .soma = .{ // índice 2
.esq = nos.at(0), .dir = nos.at(1),
} });
try nos.append(allocator, .{ .numero = 4 }); // índice 3
try nos.append(allocator, .{ .mult = .{ // índice 4
.esq = nos.at(2), .dir = nos.at(3),
} });
const raiz = nos.at(4);
const resultado = raiz.avaliar();
const stdout = std.io.getStdOut().writer();
try stdout.print("(2 + 3) * 4 = {d}\n", .{resultado}); // 20
}
SegmentedList vs ArrayList
| Característica | SegmentedList | ArrayList |
|---|---|---|
| Ponteiros estáveis | Sim | Não |
| Memória contígua | Não | Sim |
| Cache-friendliness | Menor | Maior |
| Crescimento | Sem cópia | Com cópia/realocação |
Módulos Relacionados
- std.ArrayList — Array dinâmico contíguo
- std.LinkedList — Lista duplamente encadeada
- std.mem.Allocator — Interface de alocação