开发者

Go equivalent to std::set?

What would be the equivalent in Go to a std::set? Note that only uniqueness is important, I don't ca开发者_开发百科re 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?


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.


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.


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).


If anyone need a set of int, you can use this:

package main
import "golang.org/x/tools/container/intsets"

func main() {
   var (
      a intsets.Sparse
      b bool
   )
   b = a.Insert(9)
   println(b) // true
   b = a.Insert(9)
   println(b) // false
}

https://pkg.go.dev/golang.org/x/tools/container/intsets

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜