Introdução
Um conjunto (set) é uma estrutura de dados que armazena valores únicos sem repetição. Em Zig, não existe um tipo Set nativo na biblioteca padrão, mas é simples implementar um usando AutoHashMap ou StringHashMap com valores void. Conjuntos são ideais para verificar pertencimento, remover duplicatas e realizar operações como união e interseção.
Nesta receita, você aprenderá a implementar e usar conjuntos em Zig.
Pré-requisitos
- Zig instalado (versão 0.13+). Veja o guia de instalação
- Conhecimento básico de Zig. Consulte a introdução ao Zig
- Familiaridade com HashMap
Conjunto Básico com HashMap
Use AutoHashMap(T, void) para criar um set:
const std = @import("std");
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
// Set de inteiros usando HashMap com valor void
var conjunto = std.AutoHashMap(i32, void).init(allocator);
defer conjunto.deinit();
// Adicionar elementos (duplicatas são ignoradas)
const numeros = [_]i32{ 5, 3, 8, 1, 3, 5, 9, 1, 7, 8, 2, 5 };
for (numeros) |n| {
try conjunto.put(n, {});
}
std.debug.print("Entrada: {d} elementos com duplicatas\n", .{numeros.len});
std.debug.print("Set: {d} elementos únicos\n", .{conjunto.count()});
// Verificar pertencimento
std.debug.print("Contém 5? {}\n", .{conjunto.contains(5)});
std.debug.print("Contém 4? {}\n", .{conjunto.contains(4)});
// Listar elementos
std.debug.print("Elementos: ", .{});
var it = conjunto.keyIterator();
while (it.next()) |key_ptr| {
std.debug.print("{d} ", .{key_ptr.*});
}
std.debug.print("\n", .{});
// Remover elemento
_ = conjunto.remove(3);
std.debug.print("Após remover 3: {d} elementos\n", .{conjunto.count()});
}
Set Genérico Reutilizável
Encapsule a lógica em um tipo genérico:
const std = @import("std");
fn Set(comptime T: type) type {
return struct {
const Self = @This();
map: std.AutoHashMap(T, void),
pub fn init(allocator: std.mem.Allocator) Self {
return .{ .map = std.AutoHashMap(T, void).init(allocator) };
}
pub fn deinit(self: *Self) void {
self.map.deinit();
}
pub fn add(self: *Self, valor: T) !void {
try self.map.put(valor, {});
}
pub fn remove(self: *Self, valor: T) bool {
return self.map.remove(valor);
}
pub fn contains(self: *Self, valor: T) bool {
return self.map.contains(valor);
}
pub fn count(self: *Self) usize {
return self.map.count();
}
pub fn iterator(self: *Self) @TypeOf(self.map.keyIterator()) {
return self.map.keyIterator();
}
};
}
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
var frutas = Set([]const u8).init(allocator);
defer frutas.deinit();
try frutas.add("maçã");
try frutas.add("banana");
try frutas.add("uva");
try frutas.add("maçã"); // Duplicata ignorada
try frutas.add("laranja");
try frutas.add("banana"); // Duplicata ignorada
std.debug.print("Frutas únicas: {d}\n", .{frutas.count()});
std.debug.print("Tem maçã? {}\n", .{frutas.contains("maçã")});
std.debug.print("Tem manga? {}\n", .{frutas.contains("manga")});
}
Operações de Conjunto: União, Interseção, Diferença
const std = @import("std");
const IntSet = struct {
map: std.AutoHashMap(i32, void),
allocator: std.mem.Allocator,
pub fn init(allocator: std.mem.Allocator) IntSet {
return .{
.map = std.AutoHashMap(i32, void).init(allocator),
.allocator = allocator,
};
}
pub fn deinit(self: *IntSet) void {
self.map.deinit();
}
pub fn add(self: *IntSet, valor: i32) !void {
try self.map.put(valor, {});
}
pub fn contains(self: *IntSet, valor: i32) bool {
return self.map.contains(valor);
}
pub fn count(self: *IntSet) usize {
return self.map.count();
}
// União: A ∪ B
pub fn uniao(a: *IntSet, b: *IntSet) !IntSet {
var resultado = IntSet.init(a.allocator);
errdefer resultado.deinit();
var it = a.map.keyIterator();
while (it.next()) |key| try resultado.add(key.*);
it = b.map.keyIterator();
while (it.next()) |key| try resultado.add(key.*);
return resultado;
}
// Interseção: A ∩ B
pub fn intersecao(a: *IntSet, b: *IntSet) !IntSet {
var resultado = IntSet.init(a.allocator);
errdefer resultado.deinit();
var it = a.map.keyIterator();
while (it.next()) |key| {
if (b.contains(key.*)) {
try resultado.add(key.*);
}
}
return resultado;
}
// Diferença: A - B
pub fn diferenca(a: *IntSet, b: *IntSet) !IntSet {
var resultado = IntSet.init(a.allocator);
errdefer resultado.deinit();
var it = a.map.keyIterator();
while (it.next()) |key| {
if (!b.contains(key.*)) {
try resultado.add(key.*);
}
}
return resultado;
}
pub fn imprimir(self: *IntSet) void {
std.debug.print("{{ ", .{});
var it = self.map.keyIterator();
var first = true;
while (it.next()) |key| {
if (!first) std.debug.print(", ", .{});
std.debug.print("{d}", .{key.*});
first = false;
}
std.debug.print(" }}", .{});
}
};
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
var a = IntSet.init(allocator);
defer a.deinit();
for ([_]i32{ 1, 2, 3, 4, 5 }) |n| try a.add(n);
var b = IntSet.init(allocator);
defer b.deinit();
for ([_]i32{ 3, 4, 5, 6, 7 }) |n| try b.add(n);
std.debug.print("A = ", .{});
a.imprimir();
std.debug.print("\nB = ", .{});
b.imprimir();
var u = try IntSet.uniao(&a, &b);
defer u.deinit();
std.debug.print("\nA ∪ B = ", .{});
u.imprimir();
var i = try IntSet.intersecao(&a, &b);
defer i.deinit();
std.debug.print("\nA ∩ B = ", .{});
i.imprimir();
var d = try IntSet.diferenca(&a, &b);
defer d.deinit();
std.debug.print("\nA - B = ", .{});
d.imprimir();
std.debug.print("\n", .{});
}
Remover Duplicatas de um Array
const std = @import("std");
fn removerDuplicatas(allocator: std.mem.Allocator, items: []const i32) ![]i32 {
var visto = std.AutoHashMap(i32, void).init(allocator);
defer visto.deinit();
var resultado = std.ArrayList(i32).init(allocator);
errdefer resultado.deinit();
for (items) |item| {
if (!visto.contains(item)) {
try visto.put(item, {});
try resultado.append(item);
}
}
return resultado.toOwnedSlice();
}
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
const dados = [_]i32{ 4, 2, 7, 2, 1, 4, 8, 7, 3, 1, 5, 8 };
const unicos = try removerDuplicatas(allocator, &dados);
defer allocator.free(unicos);
std.debug.print("Original: ", .{});
for (dados) |n| std.debug.print("{d} ", .{n});
std.debug.print("\nSem duplicatas: ", .{});
for (unicos) |n| std.debug.print("{d} ", .{n});
std.debug.print("\n", .{});
}
Dicas e Boas Práticas
Use
voidcomo valor:AutoHashMap(T, void)é a forma idiomática de criar sets em Zig.Sets de strings: Use
StringHashMap(void)para conjuntos de texto.Pré-aloque se souber o tamanho: Use
ensureTotalCapacitypara melhor performance.Mantenha a ordem com ArrayList: Se a ordem de inserção importa, combine um set (para unicidade) com um ArrayList (para ordem).
Receitas Relacionadas
- Como usar HashMap em Zig - Base para implementação
- Filtrar Arrays - Filtrar com sets
- Arrays Dinâmicos com ArrayList - Listas auxiliares
- Usando GeneralPurposeAllocator - Alocador