Check if keys of hashmap is equal to or a subset of another hashmap's keys

Help
1

I’m trying to use a std.StringHashmapUnmanaged(void) as a set, but I can’t quite figure out how to compare the keys as sets, specifically the equality and subset operations. Does anybody know of an elegant way to do this or do I need to check if all keys in in one hashmap are contained within the other with a loop?

2

This is a set implementation written on top of std hash maps, there is also a supersetOf function. It seems to just iterate over all elements and check whether one set contains the other. I can’t really think of a more efficient way to do this, of course there could be optimizations if you can presuppose some things about your data.
If this is a common use case for you I’d also think about using ArrayHashMap since it offers cheaper iteration.

Also have a look at this short talk by Andrew about programming without pointers. He’s using a string table as an example there, I don’t know what exactly you’re trying to implement but it could help :slight_smile:

2 Likes
3

Thanks, I’ll iterate over the keys then.

I have looked at his and other’s talks about pointer-free programming but that’s an optimization I get to later if ever. In this case I’m trying to implement an algorithm from an older research paper that uses sets that needs equality checking. Specifically this paper about implementing left-recursive rules in packrat parsers. I’ve implemented this in C++ before, but the difference here being that C++ has sets in the standard library making this particular thing easier in C++. But I also had to use std::variant which is one of my least favorite things ever used in C++, proper tagged unions with language support like Zig is the way to go for sure.

2 Likes
4

I don’t know a lot about parsers but if you could map every rule to a stable index then you could use bitsets to represent which rules are currently being used/evaluated and have very cheap set operations.

2 Likes
5

Thanks for the pointers (heh)!

I’m a “self-learned” programmer (engineering physics and electrical engineering background) so I don’t know what all those things are, but I’ll remember to come back later if I want to make my code faster.

2 Likes
6

In the off chance you haven’t seen it, I thought I would point out that the Lua team wrote a paper on left-recursive PEG grammars defining them for the ‘parsing machine’ approach to PEG parsing.

I’ve seen the one you link to before, and I’ve often wondered if both approaches have the same semantics. Superficially they would, but the devil is in the details.

1 Like
7

Thanks for sharing!

I started reading that paper but my unfamiliarity with parsing theory made it hard to follow, might give it a chance later if I remember.

1 Like