Go equivalent to std::set?

Question

What would be the equivalent in Go to a std::set? Note that only uniqueness is important, I don't care about ordering.

I've considered using dummy type, such as map[string]bool (where bool is the dummy), however often I find in Go I need to provide a type where one is not required, such as a channel used as a semaphore, and this case. Am I missing something idiomatic to Go?

Answer 1

Using a map with dummy values as a set is common practice in languages like Perl, which do not have sets. I think it is an acceptable way to get sets in Go, unless you want to implement it yourself or use some third-party implementation. Of course, your datatype has to be one that is allowed as the key in a map, i.e. not struct, array, or slice.

Answer 2

Using map[string]bool is perfectly fine.

There are also some more fancy libraries to handle sets, see for example: https://github.com/pwil3058/gosets

But I would still stick with a simple map, it is more idiomatic and simpler, which is always good.

Answer 3

Using map[string]bool (with true as the dummy value) or map[string]struct{} as a set is considered idiomatic Go. Each of them has its own pros and cons.

Assume:

b := make(map[string]bool)
s := make(map[string]struct{})

1. Checking whether a set has an element is easier with b:

   if b["x"] {
       // b has "x"
   }
   
   if _, ok := s["x"]; ok {
       // s has "x"
   }
   

2. Unless you can guarantee that b does not have any false values, iterating over the elements is easier with s:

   for e, v := range b {
       if v {
           // e is an element of b
       }
   }
   
   for e := range s {
       // e is an element of s
   }
   

3. s is more memory-efficient than b.

As an alternative, you can use an open-source library. For instance:

• github.com/soroushj/menge implements sets of all basic types.
• k8s.io/apimachinery/pkg/util/sets implements sets of integers (byte, int, int32, int64) and strings.

Of course, currently, it's not possible to implement generic sets in Go. But with the planned addition of generics to Go, it will be possible in a later version (no earlier than 1.17).