This article focuses on how to use the syntax features of the Go language to implement Set type data structures.

demand

For a data structure of type Set, it’s essentially not that different from a List. A Set can initialize, Add, Clear, Remove, and Contains items. Let’s look at the specific implementation analysis.

implementation

In Java, it is easy to know that the underlying implementation of HashSet is HashMap. The core is to use a constant to fill the Value option in the Map key-value pair. In addition, pay attention to the data structure of Map in Go. Keys are not allowed to be duplicated, as shown below:

m := map[string]string{
		"1": "one",
		"2": "two",
		"1": "one",
		"3": "three",
	}
	fmt.Println(m)
Copy the code

The program will directly report the error, prompting the duplicate Key value, which is very consistent with the Set feature requirements.

define

The Value of Set is fixed and can be replaced by a constant. But the author analysis of the implementation of the source code, using an empty structure to achieve, as shown below:

Var Exists = struct{}{} // Set is the main interface type Set struct{// struct is a type of variable m map[interface{}]struct{} }Copy the code

To solve the problem of using an empty structure as a constant Value, let’s look at the following test:

Import (" FMT ""unsafe") // Define non-empty struct type S struct {a uint16 b uint32} func main() {var S S fmt.Println(unsafe.Sizeof(s)) // prints 8, not 6 var s2 struct{} fmt.Println(unsafe.Sizeof(s2)) // prints 0 }Copy the code

Print the empty struct variable with a memory footprint of 0, and look at the following test:

a := struct{}{}
b := struct{}{}
fmt.Println(a == b) // true
fmt.Printf("%p, %p\n", &a, &b) // 0x55a988, 0x55a988
Copy the code

It is interesting that A and B are equal, and the addresses of a and B are the same. Now you can see why:

var Exists = struct{}{}
Copy the code

This constant also fills all Map values, Go is wonderful!!

Initialize the

Initialization of a data structure of type Set, optionally passed in or out of the declaration. When declaring a Map slice, the Key can be any type of data and can be implemented using an empty interface. Void struct (Value);

func New(items ... S := &set {} s.m = make(map[interface{}]struct{}) s.dd (items...) return s }Copy the code

add

A simplified operation can add an indefinite number of elements to a Set. This can be achieved by using the variable length parameter property. Since the Map does not allow the same Key value, there is no need for the rearrangement operation. The Value Value is also specified as an empty structure type.

func (s *Set) Add(items ... interface{}) error { for _, item := range items { s.m[item] = Exists } return nil }Copy the code

contains

Contains is a query operation to see if the corresponding Item exists. It can be implemented using Map features, but since it does not need a Value, it can be done using _ and OK:

func (s *Set) Contains(item interface{}) bool {
	_, ok := s.m[item]
	return ok
}
Copy the code

Length and clearance

Getting the Set length is as simple as getting the Map length of the underlying implementation:

func (s *Set) Size() int {
	return len(s.m)
}
Copy the code

The clearing operation can be achieved by re-initializing Set, as follows:

func (s *Set) Clear() {
	s.m = make(map[interface{}]struct{})
}
Copy the code

equal

To determine whether two sets are equal or not can be realized by loop iteration, that is, each element in A can be queried to see if it exists in B. As long as one element does not exist, A and B are not equal, as follows:

Func (s *Set) Equal(other *Set) bool {// if s.size ()! = other.size () {return false} for key := range s.m {// Return false if one does not exist. other.Contains(key) { return false } } return true }Copy the code

A subset of

Judging whether A is A subset of B is also A process of cyclic traversal, and specific analysis has been described above. The implementation method is as follows:

Subset(s *Set) IsSubset(other *Set) bool {// S is longer than other, If s.size () > other.size () {return false} for key := range s.m {if! other.Contains(key) { return false } } return true }Copy the code

Ok, so that’s the main implementation of Set in Go, and it’s interesting. Keep it up.