Thinking and Analysis on Implementation of Set in Go Language

Sometimes we need to set containers during Go development, but Go itself does not have this data container built-in, so we often need to implement it ourselves, but the implementation is also very simple.

Attached, recommended reading:/Visforest/goset

map[xxx]struct{}

The most commonly used and easiest implementation is to usemap,like:

type StrSet struct{
    data map[string]struct{}
}

mapThe value part is designed asstruct{}Types are to save memory space.

map[interface{}]struct{}

The above implementation is a string set. If you want other types of sets, you have to define it again.Int8Set、IntSet、Float32SetWait, it's very cumbersome.

Many people may choose to implement this:

type Set struct {
	data map[interface{}]struct{}
}

// New creates a new Set
func New(v ...interface{}) *Set {
	s := &Set{data: map[interface{}]struct{}{}}
	for _, ele := range v {
		[ele] = struct{}{}
	}
	return s
}

// ...

// ToList returns data slice
func (s *Set) ToList() []interface{} {
	var data = make([]interface{}, len())
	var i int
	for d := range  {
		data[i] = d
		i++
	}
	return data
}

There are several problems with this method:

Execute the following code:

func main() {
	var l1 = []int{1, 2, 3}
	var l2 = []int{4, 5, 6}
	var s = NewSet(l1, l2)
	for _, e := range () {
		(e)
	}
}

Error:

panic: runtime error: hash of unhashable type []int

The reason is very simple,[]intIt cannot be calculated by hash, that is, it cannot be used as the key of the map. Readers can check the types allowed by the map key.interface{}This kind of "panacea" may also be inappropriate.

Observe the following code

func main() {
	var s = NewSet("a", "b", "c")
	var tmp []string
	for _, e := range () {
		tmp = append(tmp, e.(string))
	}
	test(tmp)
}

testThe function cannot be taken directly()As an entry parameter, it must be()Convert to[]string, the reason is self-evident.

The encoding efficiency and execution efficiency are significantly lost every time.

map[T comparable]struct{}

The above disadvantages can be solved by generics.

definition:

type Set[T comparable] struct {
	data map[T]struct{}
}

// New creates a new Set
func NewSet[T comparable](v ...T) *Set[T] {
	s := &Set[T]{data: map[T]struct{}{}}
	for _, ele := range v {
		[ele] = struct{}{}
	}
	return s
}

func (s *Set[T]) Add(v ...T) {
	for _, ele := range v {
		[ele] = struct{}{}
	}
}

// ...

// ToList returns data slice
func (s *Set[T]) ToList() []T {
	var data = make([]T, len())
	var i int
	for d := range  {
		data[i] = d
		i++
	}
	return data
}

use:

func test1(data []string) {
	// ...
}

func test2(data []float64) {
	// ...
}

func main() {
	var s1 = NewSet("a", "b", "c")
	test1(())

	var s2 = NewSet(1.3, 2.2, 3)
	test2(())
}

type IntSet = Set[int]

The Set above is a general set, and you may be misled when using the types. We can define sets of special data types, and the code does not require much.

type IntSet = Set[int]

func NewIntSet(v ...int) *IntSet {
	return NewSet[int](v...)
}

use:

func main() {
	var s = NewIntSet(1, 2, 3)
	test3(())

	// Compile error	// ("a", "b", "c")
}

fifo set

Usually set is disordered, and the above implementations are also disordered, but in some scenarios we need an ordered set, such as fifo set and sorted set. Here we take fifo set as an example to discuss its implementation.

To take into account the search efficiency and orderly characteristics, you can usemap + array / double linkedlist, considering the addition, deletion and memory usage of data,double linkedlistThere is a comparisonarraySignificant advantages.

type setNode[T comparable] struct {
	val  T
	pre  *setNode[T]
	next *setNode[T]
}

type FifoSet[T comparable] struct {
	head *setNode[T]
	tail *setNode[T]
	data map[T]*setNode[T]
}

// add data, make it first in first out
func (l *FifoSet[T]) Add(v ...T) {
	if len(v) == 0 {
		return
	}

	var i int
	if  == nil {
		// first node
		n := &setNode[T]{
			val: v[i],
		}
		 = n
		 = n
		[v[i]] = n
		i++
	}
	for ; i < len(v); i++ {
		if _, ok := [v[i]]; !ok {
            // when missing, insert
			n := &setNode[T]{
				val:  v[i],
				pre:  ,
				next: nil,
			}
			 = n
			 = n
			[v[i]] = n
		}
	}
}

use:

func main() {
	var s = NewFifoSet[string]()
	("e", "a", "b", "a", "c", "b")
	// e
	// a
    // b
	// c
	for _, v := range () {
		(v)
	}
}

sorted set

In fact, sorted set is very similar to fifo set implementations, but there is a slight difference, so I will skip it here.

If you are interested, please read the author's/Visforest/goset, or try to implement it yourself.

The above is the detailed content of the implementation of set in Go language. For more information about Go set, please pay attention to my other related articles!