A simple Set implementation

As a spin-off of banging my head with Advent of Code, here’s a simple Set implemented in Zig. It surely isn’t the most efficient, bullet-proof impl, but it’s passing the basic functionality tests. :^)

vim build.exe?.. Why does this file have exe suffix, not zig?

OMG, that’s what Advent of Code does to your brain. lol. Thanks for the good catch!

Another misprint in README.md:

exe.addPackagePath("set", "libs/set/src/set.zig");

Must be

exe.addPackagePath("set", "libs/set/src/Set.zig");

I tried to build a set of structures with 3 f32 fields:

const std = @import("std");
const set = @import("set");

const Object = struct {
    x: f32,
    y: f32,
    z: f32,
};

const ObjectSet = set.Set(Object);

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer std.debug.print("leakage?.. {}\n", .{gpa.deinit()});
    const allocator = gpa.allocator();

    var set_1 = try ObjectSet.fromSlice(
        allocator,
        &[_]Object{
            .{.x = 1.1, .y = 2.2, .z = 3.3},
            .{.x = 4.4, .y = 5.5, .z = 6.6},
        }
    );

    const b = set_1.contains(.{.x = 1.1, .y = 2.2, .z = 3.3});
    std.debug.print("b = {}\n", .{b});
}

Compiler says

/opt/zig-0.10/lib/std/hash/auto_hash.zig:84:12: error: unable to hash type f32
        => @compileError("unable to hash type " ++ @typeName(Key)),
           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
referenced by:
    hash__anon_7769: /opt/zig-0.10/lib/std/hash/auto_hash.zig:127:17
    autoHash__anon_6976: /opt/zig-0.10/lib/std/hash/auto_hash.zig:193:5

However it works with a set of

const Object = struct {
    x: i32,
    y: i32,
    z: i32,
};

set.zig is actually correct. It’s just that I did a normal mv instead of using git mv. I pushed the correction to the repo. Zig convention recommends lowercase if the namespace in question doesn’t have any fields as is the case here.

Yes, that’s the normal rules for a Zig hash map; you can’t have keys with floats. I believe it has to do with the fact that comparing floats is imprecise and in a hash map comparing keys (their hashes to be exact) is the critical step in their functionality.

We have to compare keys directly in case of conflicts, that’s the reason, I think. Calculating hash/index is not a problem by itself.

A couple of articles about using floats as keys in hash tables.

1 Like