4 ms·

Go still doesn't have Set types. The usual thing to do is using a map of your type to either an empty struct, or maybe a bool, if I got that correctly (have onl

• porridgeraisin 3y ago
  Most languages implement sets using maps. The only major difference you can optimise for is the fact that in majority usage, keys in maps are likely to exist, whereas sets are used for membership checks. Bar that, you can just as well use a map with a dummy value.
  • zogrodea 3y ago
    Can you give a reference for that? It sounds very unlikely to me, although I've only read/gone through two relevant standard library implementations: F# and OCaml. Neither of them use dummy values as you suggest. They have similar implementations (both are AVL trees) but sets really do contain only one value while maps contain two. I would be surprised if many other languages did as you suggest.
    • djur 3y ago
      Python, Ruby, Perl. Languages where hashmaps are a builtin.
      • eesmith 3y ago
        Python has its own set type not based on hashmap/dict, and that's been the case for years. The set implementation points out some of the differences, at https://github.com/python/cpython/blob/main/Objects/setobject.c https://github.com/python/cpython/blob/main/Objects/setobjec... : Unlike the dictionary implementation, the lookkey function can return NULL if the rich comparison returns an error. Use cases for sets differ considerably from dictionaries where looked-up keys are more likely to be present. In contrast, sets are primarily about membership testing where the presence of an element is not known in advance. Accordingly, the set implementation needs to optimize for both the found and not-found case.
      • brabel 3y ago
        Java as well: https://github.com/pengisgood/jdk-source-code/blob/master/src/java/util/HashSet.java#L106 https://github.com/pengisgood/jdk-source-code/blob/master/sr... EDIT : and Rust: https://docs.rs/hashbrown/latest/hashbrown/hash_set/index.html https://docs.rs/hashbrown/latest/hashbrown/hash_set/index.ht... (this is used by the default implementation of HashSet).
    • alpaca128 3y ago
      Rust's HashSet is a HashMap mapping to "()", which is Rust's equivalent to "void".
      • progbits 3y ago
        That is true for the internal implementation details but HashSet provides a different API, it is not just a type alias. So you don't have to worry about semantics of what the values mean (like the bools in Go), and it has no size overhead.
    • zogrodea 3y ago
      Update: Looks like I had good reason to be surprised. Thanks everyone for the examples.
• jmaker 3y ago
  Yes in Go I think I’m mostly tempted to reinvent the wheel every few lines of code, for the sheer lack of stdlib abstractions I’ve grown used to.
  • IggleSniggle 3y ago
    This is funny to me, because Go is often touted as a language that has "everything you need" in the stdlib. Of course, I'm coming from the nodejs world, where before you can start working you first need to evaluate and choose: typescript or not typescript and if yes what build tool chain, which test runner, which assertion lib, which mocking lib, etc etc. Not really that long ago when you had to choose which async lib (now you just need to choose which async color). Thankfully a lot of that stuff is in nodejs now, and there's a commitment to maintain parity with Web APIs which also helps, but there's still a lot of half-done work and path-dependencies on outside libs.
    • vitus 3y ago
      > This is funny to me, because Go is often touted as a language that has "everything you need" in the stdlib. My usual example of something missing from the standard library is func max(a, b int) int { if a > b { return a } else { return b } } math.Max only operates on two float64s (due to the absence of function overloads; many standard library functions such as this predated generics), so if you want to avoid casting (and/or potential loss of precision if you're working with int64), you need to reinvent the wheel.
      • pyth0 3y ago
        Go has had generic forms of the `min` and `max` functions as builtins since 1.21. https://pkg.go.dev/builtin#max https://pkg.go.dev/builtin#max
        • j1elo 3y ago
          Go 1.21 is the version from which it is noticeable that they are pushing towards (re)implementing things that were lacking before due to missing support for generics. Like the new slices package, meant to do common operations on slices, that is brand new on 1.21. I wouldn't be surprised to see more and more new additions leveraging generics in next releases.
• gchamonlive 3y ago
  I did it using maps and generics and implemented a subset of the convenience methods that python has in sets.