A simple set type for the Go language. Trusted by Docker, 1Password, Ethereum and Hashicorp.

Overview

Build Status Go Report Card GoDoc

golang-set

The missing set collection for the Go language. Until Go has sets built-in...use this.

Coming from Python one of the things I miss is the superbly wonderful set collection. This is my attempt to mimic the primary features of the set from Python. You can of course argue that there is no need for a set in Go, otherwise the creators would have added one to the standard library. To those I say simply ignore this repository and carry-on and to the rest that find this useful please contribute in helping me make it better by:

  • Helping to make more idiomatic improvements to the code.
  • Helping to increase the performance of it. (So far, no attempt has been made, but since it uses a map internally, I expect it to be mostly performant.)
  • Helping to make the unit-tests more robust and kick-ass.
  • Helping to fill in the documentation.
  • Simply offering feedback and suggestions. (Positive, constructive feedback is appreciated.)

I have to give some credit for helping seed the idea with this post on stackoverflow.

Update - as of 3/9/2014, you can use a compile-time generic version of this package in the gen framework. This framework allows you to use the golang-set in a completely generic and type-safe way by allowing you to generate a supporting .go file based on your custom types.

Features (as of 9/22/2014)

Features (as of 9/15/2014)

Features (as of 4/22/2014)

  • One common interface to both implementations
  • Two set implementations to choose from
    • a thread-safe implementation designed for concurrent use
    • a non-thread-safe implementation designed for performance
  • 75 benchmarks for both implementations
  • 35 unit tests for both implementations
  • 14 concurrent tests for the thread-safe implementation

Please see the unit test file for additional usage examples. The Python set documentation will also do a better job than I can of explaining how a set typically works. Please keep in mind however that the Python set is a built-in type and supports additional features and syntax that make it awesome.

Examples but not exhaustive:

requiredClasses := mapset.NewSet()
requiredClasses.Add("Cooking")
requiredClasses.Add("English")
requiredClasses.Add("Math")
requiredClasses.Add("Biology")

scienceSlice := []interface{}{"Biology", "Chemistry"}
scienceClasses := mapset.NewSetFromSlice(scienceSlice)

electiveClasses := mapset.NewSet()
electiveClasses.Add("Welding")
electiveClasses.Add("Music")
electiveClasses.Add("Automotive")

bonusClasses := mapset.NewSet()
bonusClasses.Add("Go Programming")
bonusClasses.Add("Python Programming")

//Show me all the available classes I can take
allClasses := requiredClasses.Union(scienceClasses).Union(electiveClasses).Union(bonusClasses)
fmt.Println(allClasses) //Set{Cooking, English, Math, Chemistry, Welding, Biology, Music, Automotive, Go Programming, Python Programming}


//Is cooking considered a science class?
fmt.Println(scienceClasses.Contains("Cooking")) //false

//Show me all classes that are not science classes, since I hate science.
fmt.Println(allClasses.Difference(scienceClasses)) //Set{Music, Automotive, Go Programming, Python Programming, Cooking, English, Math, Welding}

//Which science classes are also required classes?
fmt.Println(scienceClasses.Intersect(requiredClasses)) //Set{Biology}

//How many bonus classes do you offer?
fmt.Println(bonusClasses.Cardinality()) //2

//Do you have the following classes? Welding, Automotive and English?
fmt.Println(allClasses.IsSuperset(mapset.NewSetFromSlice([]interface{}{"Welding", "Automotive", "English"}))) //true

Thanks!

-Ralph

Bitdeli Badge

Analytics

Comments
  • Add thread-safe implementation

    Add thread-safe implementation

    It might be useful to add a set implementation which is thread-safe. It'd be trivially simple. You'd make something like the following changes:

    • Change the Set type to be an interface type
    • Remove the NewSet and NewSetFromSlice methods from the interface
    • Make the current Set implementation unexported (for example, call it "set")
    • Make another Set implementation (called, for example, "safeSet") which is thread-safe. Do this by making the type a struct with two fields: the map, and an embedded sync.RWMutex. When performing read operations, first RLock the struct, and then RUnlock at the end. When performing write operations, first Lock the struct, and then Unlock at the end.
    • Make a NewSet function (not a method) which returns a new set
    • Make a NewSafeSet function (not a method) which returns a new safeSet
    • Make a NewSetFromSlice function (not a method) which returns a new set from the given slice
    • Make a NewSafeSetFromSlice function (not a method) which returns a new safeSet from the given slice

    I'd be happy to make this changes and submit a pull request if you'd like. I figured I'd consult you on what you thought about the changes before I did, though.

    opened by joshlf 14
  • Someone said this function (mapset.Iter) has bug, but I don't know where is it. Plz tell me

    Someone said this function (mapset.Iter) has bug, but I don't know where is it. Plz tell me

    The interview question url is:https://zhuanlan.zhihu.com/p/26972862 The title is 9、下面的迭代会有什么问题?

    Your code url is : https://github.com/deckarep/golang-set/blob/master/threadsafe.go#L154

    I think that code is right, no bug. So what you opinion?

    opened by gravitywp 8
  • Update the `latest` tag on github to point to v2 series?

    Update the `latest` tag on github to point to v2 series?

    I've been watching this repo waiting for a tag to be cut for the new generic-based code.

    Today I finally realized that a version was cut nearly a week ago... but I never saw it because https://github.com/deckarep/golang-set/releases points to v1.7.1

    However, the newest released tag is actually https://github.com/deckarep/golang-set/releases/tag/v2.1.0

    Can you update that latest release to show v2.1.0 as the latest?

    That will also likely cut down on folks reporting bugs against the v1 series, not realizing they should switch to the v2 series...

    opened by jeffwidman 7
  • generics branch no longer works on go1.18rc1

    generics branch no longer works on go1.18rc1

    I realise it is not intended for use at this point, but thought it might be useful to bring to your attention.

    The generics branch works great on go1.18beta1 & go1.18beta2

    But on go1.18rc1, it has these errors:

    # github.com/deckarep/golang-set
    ./set.go:169:17: any does not implement comparable
    ./set.go:172:37: any does not implement comparable
    ./threadsafe.go:230:43: any does not implement comparable
    ./threadsafe.go:232:55: any does not implement comparable
    ./threadsafe.go:235:24: any does not implement comparable
    ./threadsafe.go:237:44: any does not implement comparable
    ./threadsafe.go:238:26: any does not implement comparable
    ./threadsafe.go:249:63: any does not implement comparable
    ./threadsafe.go:255:72: any does not implement comparable
    ./threadsafe.go:256:24: any does not implement comparable
    ./threadsafe.go:256:24: too many errors
    

    I think this is as a consequence of https://github.com/golang/go/issues/50646#ref-commit-360e1b8

    I've had a good look at it, and made some adjustments which seem to resolve most of it. But I wasn't able to find a way to get PowerSet working

    For Pop:

    func (s *threadUnsafeSet[T]) Pop() (v T, ok bool) {
    	for item := range *s {
    		delete(*s, item)
    		return item, true
    	}
    	return
    }
    

    (Though this does require a change to the method signature - an alternative might be to introduce a new method and return the zero value on the old one, or to return a pointer)

    Edit: For CartesianProduct, your intended code still seems to have the same problem

    For PowerSet, the problem is that it won't allow Set[Set[T]] (Set[T] does not implement comparable), and the interface cannot be declared as comparable (interface is (or embeds) comparable)

    Perhaps an alternative might be to return []Set[T](?)

    opened by billinghamj 7
  • Code comments and stylistic changes

    Code comments and stylistic changes

    opened by spakin 7
  • Serialization with gob

    Serialization with gob

    It is possible to make golang-set work with encoding/gob? gob is the good "go to" for serializing things for internal consumption later.

    I've prepare a demo here, currently it is giving out error of:

    SaveState failed:gob: type sync.RWMutex has no exported fields

    Thanks

    opened by suntong 6
  • Add support for threadsafe element removal with reporting whether element was removed.

    Add support for threadsafe element removal with reporting whether element was removed.

    An example use case for this is as follows: Imagine we have a resource A that owns a set of resources of type B. Both types have a public API to close the resource, where closing A implies closing all owned B. B.Close() can be called only once, otherwise it will fail/panic. Closing a B removes it from the set of resources that the parent A owns.

    type A struct {
      setOfB Set
    }
    type B struct {}
    
    func (a *A) CloseAllB()
    func (b *B) Close()
    

    To be able to avoid race conditions where two goroutines are calling A.CloseAllB() and B.Close() I would need to guarantee that I perform the business logic of B.Close() only when setOfB.Remove() actually removed the element. AFAIU current Set API doesn't allow me to determine this.

    I welcome suggestions on how to name this new method (ideally I'd have Remove return the boolean, but that would be a backwards-incompatible change...)

    I'll be happy to add tests if you agree that such an API should be added to this lib.

    opened by firejump 5
  • Fix PowerSet return values

    Fix PowerSet return values

    Previously, calling PowerSet() on a threadSafeSet would return a threadUnsafeSet of threadUnsafeSets. Now it returns a threadSafeSet of threadSafeSets.

    I found this issue while trying to use the results of PowerSet() in other functions, which panic on a threadUnsafeSet.

    opened by robyoder 5
  • OrderedSet implementation

    OrderedSet implementation

    Look at building an OrderedSet implementation of the set which preserves order of items added. One idea, is to still use a map where the value is an int which indicates order.

    Is this even useful to many people? Must not be a breaking change.

    Gotchas:

    • minimizing number of times we iterate when visiting each item.
    • wholes in the order
    • what the order should be when applying set operations
    opened by deckarep 5
  • Extra empty elements in String() and ToSlice() methods

    Extra empty elements in String() and ToSlice() methods

    I think there are extra empty elements in the String() and ToSlice() methods:

    func (set *threadUnsafeSet) ToSlice() []interface{} {
    	keys := make([]interface{}, 0, set.Cardinality())
    	for elem := range *set {
    		keys = append(keys, elem)
    	}
    
    	return keys
    }
    

    The make call creates an array of the specified size with empty values. For instances if the interface is just an int, it initializes the array with 0s of the specified cardinality. Then the append append() call appends the keys to the end of the array. As a result, all the values get appended.

    Would this be better?

    func (set *threadUnsafeSet) ToSlice() []interface{} {
    	var keys []interface{}
    	for elem := range *set {
    		keys = append(keys, elem)
    	}
    
    	return keys
    }
    

    Or making the slice with the length and then iterating through the slice and assigning to the index value rather than appending to the slice.

    opened by dgiridharan 4
  • Make `Remove()` return a bool indicating whether present

    Make `Remove()` return a bool indicating whether present

    Make Remove() return a bool indicating whether the object was present.

    This is useful for the thread-safe-set because the underlying mutex isn't public, so without this it's impossible to know if the element was originally present.

    This is a tweak on https://github.com/deckarep/golang-set/pull/66.

    This won't be a breaking change because today there's no returned value... so if there starts being a bool returned, legacy code will simply ignore it.

    I'm sure this will have a minor perf hit, so putting this up to play around with. If it's a super minor perf regression, then probably okay, otherwise better to split Remove() from RemoveWithResult() or some such API so that Remove() stays as high perf as possible.

    opened by jeffwidman 3
  • iterate with random sequence?

    iterate with random sequence?

    it := join_seq.Iterator() for elem := range it.C { }

    Following your document, I use the iterator to scan the set, but the result will be random... and is not the fixed sequence in data.s

    opened by ZhengQiushi 1
  • Code and style improvements

    Code and style improvements

    • renamed docstrings describing Set[T] interface methods to be compatible with a community styleguide - to start with a name of actual method. This also allows us to generate documentation more effectively (because go doc by default ignores docstrings that are not starting with an object name)
    • in unsafe implementation of set, removed pointer receivers, because unsafe set is already a pointer - because it is a map, and map is a pointer-type, and passing it by value anyway allows us to mutate the origin destination
      • also updated Clear() method. It now REALLY clears the set instead of allocating a new one. All the details are provided in the description of the last one commit
    opened by fakefloordiv 1
  • Panics with trivial test cases

    Panics with trivial test cases

    The internals of this library use a downcast of the Set interface to *threadSafeSet and *threadUnsafeSet everywhere. I'm unclear why an interface is used in this package when the logic panics if you use literally any implementation of the interface other than one that matches the type of set you requested.

    For example: https://github.com/deckarep/golang-set/blob/main/threadsafe.go#L88

    Right now, the API is suggesting that any implementation of the Set interface is acceptable (that's what an interface means), but that's not true. In fact, once you have two Sets returned from this package, you can't even tell if they are compatible or if they'll panic when you try to use methods of one on the other.

    s1 := mapset.NewSet[int]()
    s1.Add(1)
    s2 := mapset.NewThreadUnsafeSet[int]()
    s2.Add(2)
    s1.Union(s2) // compiles, but panics at runtime
    

    My suggestion is instead to simply return structs for both the threadsafe and unsafe versions. The Set interface is not giving the package any benefit, and indeed, there is actually a negative to its existence, since the two types are incompatible (as are any third-party implementations). If they each just were structs and the arguments you pass to Union etc were structs, there would be compile-time safety that ensures you don't pass in a struct that the code doesn't work with.

    opened by natefinch 1
  • add Append() method for adding multiple elements to set

    add Append() method for adding multiple elements to set

    This PR implements Append method and resolves #92 .

    Test results:

    $ go test -cover
    PASS
    coverage: 94.8% of statements
    ok      github.com/deckarep/golang-set/v2       0.767s
    
    opened by SignorMercurio 6
  • What about adding a `set.Append(vals...T)` method to add multiple values to an existing set?

    What about adding a `set.Append(vals...T)` method to add multiple values to an existing set?

    We've got NewSet(vals...T) for creating a set from multiple values.

    But today I found myself wanting to add a slice of objects to an existing set... today I have to write a for loop to range over the objects.

    What about adding an append(vals... T) method... similar to Python, which allows adding multiple objects.

    Alternatively Add(val T) bool could be modified to take multiple args, which would keep the API surface small. But it's a little undefined that it returns a bool... for multiple objects would that return true if all the objects got added to the existing set, or if at least one object got added?

    Thoughts?

    opened by jeffwidman 1
Releases(v2.1.0)
  • v2.1.0(Apr 3, 2022)

    What's Changed

    • Remove dead code by @jeffwidman in https://github.com/deckarep/golang-set/pull/85
    • Make NewThreadUnsafeSet() take optional vals. by @jeffwidman in https://github.com/deckarep/golang-set/pull/83
    • Delete New*SetFromSlice() and NewSetWith() APIs by @jeffwidman in https://github.com/deckarep/golang-set/pull/84
    • feat: improve Add performance by @orisano in https://github.com/deckarep/golang-set/pull/88

    New Contributors

    • @jeffwidman made their first contribution in https://github.com/deckarep/golang-set/pull/85
    • @orisano made their first contribution in https://github.com/deckarep/golang-set/pull/88

    Full Changelog: https://github.com/deckarep/golang-set/compare/v2.0.0...v2.1.0

    Source code(tar.gz)
    Source code(zip)
  • v1.7.1(Sep 15, 2018)

  • v1.7(Nov 5, 2017)

  • v1.6(Feb 2, 2017)

Owner
Ralph Caraveo III
- Love to solve challenging problems with code - Weapons of choice Go, Python, C# - Currently learning Rust
Ralph Caraveo III
A simple Set data structure implementation in Go (Golang) using LinkedHashMap.

Set Set is a simple Set data structure implementation in Go (Golang) using LinkedHashMap. This library allow you to get a set of int64 or string witho

Studio Sol Comunicação Digital Ltda 22 Sep 26, 2022
Null Types, Safe primitive type conversion and fetching value from complex structures.

Typ Typ is a library providing a powerful interface to impressive user experience with conversion and fetching data from built-in types in Golang Feat

Gurukami 33 Sep 26, 2022
Type-agnostic partitioning for Go's indexable collections and strings.

Go Type-Agnostic Collection Partitioning Type-agnostic partitioning for anything that can be indexed in Go - slices, arrays,strings. Inspired by Guava

Meir Fischer 35 Aug 11, 2021
low level data type and utils in Golang.

low low level data type and utils in Golang. A stable low level function set is the basis of a robust architecture. It focuses on stability and requir

null 71 Nov 17, 2022
ID type with marshalling to/from hash to prevent sending IDs to clients.

Hide IDs Hide is a simple package to provide an ID type that is marshalled to/from a hash string. This prevents sending technical IDs to clients and c

Emvi 51 Sep 26, 2022
flexible data type for Go

Generic flexible data type for Go support: Go 1.12+ Install standard go get: go get -u github.com/usk81/generic/v2 Usage encode/decode: package main

Yusuke Komatsu 45 Oct 26, 2022
A faster method to get elements from an interface (Struct or Slice type) for Go.

A faster method to get elements from an interface (Struct or Slice type) for Go.

karminski-牙医 35 May 13, 2022
Type-safe, zero-allocation sets for Go

Set Package set is a type-safe, zero-allocation port of the excellent package fatih/set. It contains sets for most of the basic types and you can gene

ScyllaDB 793 Nov 27, 2022
SliceX provides functional operations on Go slices using Go 1.18 type parameters.

SliceX provides functional operations on Go slices using Go 1.18 type parameters.

null 1 Nov 6, 2021
A slice backed binary heap with support for generic type parameters.

go-binaryheap A slice backed binary heap where the order can be customized by a comparison function. The main branch now requires go 1.18 because the

null 3 Jun 13, 2022
Probabilistic set data structure

Your basic Bloom filter Golang probabilistic set data structure A Bloom filter is a fast and space-efficient probabilistic data structure used to test

Algorithms to Go 75 Nov 20, 2022
Set is a useful collection but there is no built-in implementation in Go lang.

goset Set is a useful collection but there is no built-in implementation in Go lang. Why? The only one pkg which provides set operations now is golang

zoumo 50 Sep 26, 2022
Set data structure for Go

Archived project. No maintenance. This project is not maintained anymore and is archived.. Please create your own map[string]Type or use one of the ot

Fatih Arslan 654 Nov 21, 2022
Set data structure for Go

Archived project. No maintenance. This project is not maintained anymore and is archived.. Please create your own map[string]Type or use one of the ot

Fatih Arslan 654 Nov 21, 2022
Package mafsa implements Minimal Acyclic Finite State Automata in Go, essentially a high-speed, memory-efficient, Unicode-friendly set of strings.

MA-FSA for Go Package mafsa implements Minimal Acyclic Finite State Automata (MA-FSA) with Minimal Perfect Hashing (MPH). Basically, it's a set of str

SmartyStreets (Archives) 293 Oct 27, 2022
go/golang: fast bit set Bloom filter

package implements a fast bloom filter with real 'bitset' and JSONMarshal/JSONUnmarshal to store/reload the Bloom filter.

Andreas Briese 125 Nov 3, 2022
Disjoint Set data structure implementation in Go

dsu Implementation of the Disjoint-Set data structure. The Disjoint-Set, Also called a Union-Find or Merge-Find set, is a data structure that stores a

Iheb Haboubi 8 Sep 26, 2022
A fast (5x) string keyed read-only map for Go - particularly good for keys using a small set of nearby runes.

faststringmap faststringmap is a fast read-only string keyed map for Go (golang). For our use case it is approximately 5 times faster than using Go's

The Sensible Code Company 29 Nov 11, 2022
A close implementation of JavaScript's Set written in Go

Set The Set struct allows unique values storing of any type. Initializing a Set s := set.New() // Empty Set s := set.New("hi", 45, Person{name: "Gophe

Sergio Ríos 0 Dec 20, 2021