[data-structures] golang why don't we have a set datastructure

I'm trying to solve "The go programming lanaguage" exercise #1.4 which requires me to have a set. I can create a set type but why doesn't the language come with one ? go, having come from google, where guava also originated, why didn't the language designers opt for adding support for fundamental data structures ? why force your users to create their own implementations for something so basic as a set ?

This question is related to data-structures go set

The answer is


Partly, because Go doesn't have generics (so you would need one set-type for every type, or fall back on reflection, which is rather inefficient).

Partly, because if all you need is "add/remove individual elements to a set" and "relatively space-efficient", you can get a fair bit of that simply by using a map[yourtype]bool (and set the value to true for any element in the set) or, for more space efficiency, you can use an empty struct as the value and use _, present = the_setoid[key] to check for presence.


Another possibility is to use bit sets, for which there is at least one package or you can use the built-in big package. In this case, basically you need to define a way to convert your object to an index.


Like Vatine wrote: Since go lacks generics it would have to be part of the language and not the standard library. For that you would then have to pollute the language with keywords set, union, intersection, difference, subset...

The other reason is, that it's not clear at all what the "right" implementation of a set is:

  1. There is a functional approach:

    func IsInEvenNumbers(n int) bool {
        if n % 2 == 0 {
            return true
        }
       return false
    }
    

This is a set of all even ints. It has a very efficient lookup and union, intersect, difference and subset can easily be done by functional composition.

  1. Or you do a has-like approach like Dali showed.

A map does not have that problem, since you store something associated with the value.


One reason is that it is easy to create a set from map:

s := map[int]bool{5: true, 2: true}
_, ok := s[6] // check for existence
s[8] = true // add element 
delete(s, 2) // remove element

Union

s_union := map[int]bool{}
for k, _ := range s1{
    s_union[k] = true
}
for k, _ := range s2{
    s_union[k] = true
}

Intersection

s_intersection := map[int]bool{}
for k,_ := range s1 { 
  if s2[k] {
    s_intersection[k] = true
  }
}

It is not really that hard to implement all other set operations.


Examples related to data-structures

Program to find largest and second largest number in array golang why don't we have a set datastructure How to initialize a vector with fixed length in R C compiling - "undefined reference to"? List of all unique characters in a string? Binary Search Tree - Java Implementation How to clone object in C++ ? Or Is there another solution? How to check queue length in Python Difference between "Complete binary tree", "strict binary tree","full binary Tree"? Write code to convert given number into words (eg 1234 as input should output one thousand two hundred and thirty four)

Examples related to go

Has been blocked by CORS policy: Response to preflight request doesn’t pass access control check Go test string contains substring Golang read request body How to uninstall Golang? Decode JSON with unknown structure Access HTTP response as string in Go How to search for an element in a golang slice How to delete an element from a Slice in Golang How to set default values in Go structs MINGW64 "make build" error: "bash: make: command not found"

Examples related to set

java, get set methods golang why don't we have a set datastructure Simplest way to merge ES6 Maps/Sets? Swift Set to Array JavaScript Array to Set How to sort a HashSet? Python Set Comprehension How to get first item from a java.util.Set? Getting the difference between two sets Python convert set to string and vice versa