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

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.

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?

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

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](?)

This revision incorporates a number of minor improvements to code and documentation quality. The result passes go vet, misspell, and golint. To celebrate, the README file now includes a badge pointing to the Go Report Card for golang-set.

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

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.

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.

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

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.

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.

old

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

in my opinion, the last return badly impacts readability.

refactored

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

• improved readability.
• no usage of named returns since they weren't actually used, they existed as a hack to return default values.

test results

$ go test ./... -cover -race
ok      github.com/deckarep/golang-set/v2       79.012s coverage: 94.8% of statements

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

• 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

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.

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