current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 27 down vote favorite
7

I really like google golang but could some one explain what the rationale is for the implementors having left out a basic data structure such as sets from the standard library?

share|improve this question
7  
The language is actually called Go, not golang – jozefg Nov 28 '12 at 2:44
43  
But "golang" is more searchable – Matt May 29 '13 at 19:27
7  
Way more searchable. Googling "go set" returns images of a wooden board with black and white pieces. – Doug Richardson Feb 10 '14 at 5:55
up vote 27 down vote accepted

One potential reason for this omission is that it's really easy to model sets with a map.

To be honest I think it's a bit of an oversight too, however looking at Perl, the story's exactly the same. In Perl you get lists and hashtables, in Go you get arrays, slices, and maps. In Perl you'd generally use a hashtable for any and all problems relating to a set, the same is applicable to Go.

Example

to imitate a set ints in Go, we define a map:

set := make(map[int]bool)

To add something is as easy as:

i := valueToAdd()
set[i] = true

Deleting something is just

delete(set, i)

And the potential awkwardness of this construct is easily abstracted away:

type IntSet struct {
    set map[int]bool
}

func (set *IntSet) Add(i int) bool {
    _, found := set.set[i]
    set.set[i] = true
    return !found   //False if it existed already
}

And delete and get can be defined similarly, I have the complete implementation here . The major disatvantage here is the fact that go doesn't have generics. However it is possible to do this with interface{} in which case you'd have cast the results of get.

share|improve this answer
1  
Here's my slightly-revised version with Contains and Size methods: play.golang.org/p/tDdutH672- – Rick-777 Apr 16 '13 at 18:07
8  
Instead of map[int]bool one can use map[int]struct{} instead. I prefer the last. – pepper_chico Dec 11 '13 at 2:26
7  
map[int]struct{} .. The struct{} takes 0 bytes. – Boopathi Rajaa Dec 13 '13 at 4:34
2  
github.com/fatih/set is an implementation of my based on maps and empty structs. It's thread safe and has a simple api. – Fatih Arslan Jan 11 '14 at 23:50
2  
With map[int]struct{} you can't do if mymap["key"] { to check for membership. Google recommends using bool (search for "A set can be implemented"). – Timmmm Jan 6 '15 at 13:18
up vote 0 down vote

The previous answer works ONLY IF the key are a built-in type. To complement the previous answer, here is a way to implement a set whose elements are user-defined types:

package math

// types

type IntPoint struct {
    X, Y int
}

// set implementation for small number of items
type IntPointSet struct {
    slice []IntPoint 
}

// functions

func (p1 IntPoint) Equals(p2 IntPoint) bool {
    return (p1.X == p2.X) && (p1.Y == p2.Y)
}

func (set *IntPointSet) Add(p IntPoint) {
    if ! set.Contains(p) {
        set.slice = append(set.slice, p)
    }
}

func (set IntPointSet) Contains(p IntPoint) bool {
  for _, v := range set.slice {
    if v.Equals(p) {
      return true
    }
  }
  return false
}

func (set IntPointSet) NumElements() int {
    return len(set.slice)
}

func NewIntPointSet() IntPointSet {
  return IntPointSet{(make([]IntPoint, 0, 10))}
}
share|improve this answer
3  
"works ONLY IF the key are a built-in type" is wrong. type mySet map[IntPoint]bool works perfectly well. All that is required of the key type used in a map is that it has == and !=. Equality of struct types is well defined, your Equals method should be just p1 == p2. – Dave C Mar 27 '15 at 1:48
up vote 0 down vote

I think this has to do with golang focus on simplicity. sets become really useful with difference, intersection, union, issubset, and so on.. methods. Perhaps golang team felt that it is too much for one data structure. But otherwise a "dumb set" that only has add, contains and remove can be easily replicated with map as explained by @jozefg.

share|improve this answer

protected by gnat May 2 '15 at 17:30

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.