This article mainly talks about how to use the syntax characteristics of Go language to implement Set type data structures.
need
For Set type data structures, they are actually not much different from List in essence. It's nothing more than that Set cannot contain duplicate Item features. Set has operations such as initialization, Add, Clear, Remove, Contains, etc. Let’s take a look at the specific implementation analysis.
accomplish
Still, based on existing programming experience, how to implement the basic Set function is as follows. It is easy to know in Java 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, focus on 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",
}
(m)
The program will directly report an error, prompting to repeat the Key value, which is very consistent with the characteristics of Set.
definition
The previous analysis shows that Set's Value is a fixed value, and just use a constant instead. However, the author analyzed the implementation source code using an empty structure to implement it, as shown below:
// Empty structurevar Exists = struct{}{}
// Set is the main interface
type Set struct {
// struct is a variable of the structure type m map[interface{}]struct{}
}
In order to solve the above why the empty structure is used to make constant value, first look at the following test:
import (
"fmt"
"unsafe"
)
// Define non-empty structuretype S struct {
a uint16
b uint32
}
func main() {
var s S
((s)) // prints 8, not 6
var s2 struct{}
((s2)) // prints 0
}
Print out the memory footprint of the empty structure variable is 0, and then take a look at the following test:
a := struct{}{}
b := struct{}{}
(a == b) // true
("%p, %p\n", &a, &b) // 0x55a988, 0x55a988
It's very interesting that a and b are equal, and the addresses of a and b are the same. Now you should understand why:
var Exists = struct{}{}
Such constants can also fill the values of all maps. Go is really exciting! ! !
initialization
The initialization operation of Set type data structure can be used to pass in or not to pass in while declaring it. When declaring a Map slice, the Key can be any type of data and can be implemented using an empty interface. If Value is analyzed above, use an empty structure:
func New(items ...interface{}) *Set {
// Get the Set's address s := &Set{}
// Declare the data structure of map type = make(map[interface{}]struct{})
(items...)
return s
}
Add to
Simplified operations can add undetermined elements into the Set, and use the characteristics of variable-length parameters to achieve this requirement, because the Map does not allow the same Key values, so there is no need to have a re-scheduling operation. At the same time, specify the Value value as the empty structure type.
func (s *Set) Add(items ...interface{}) error {
for _, item := range items {
[item] = Exists
}
return nil
}
Include
The Contains operation is actually a query operation to see if there is a corresponding Item. It can be implemented using the Map feature, but since the value of Value is not required, you can use _, ok to achieve the purpose:
func (s *Set) Contains(item interface{}) bool {
_, ok := [item]
return ok
}
Length and clearance
It is very simple to get the Set length, you only need to get the length of the underlying Map:
func (s *Set) Size() int {
return len()
}
For clearing operations, you can implement it by reinitializing Set, as follows:
func (s *Set) Clear() {
= make(map[interface{}]struct{})
}
equal
To determine whether the two Sets are equal, it can be implemented through loop traversal. That is, to query whether each element in A exists in B. As long as one does not exist, A and B are not equal. The implementation method is as follows:
func (s *Set) Equal(other *Set) bool {
// If the Sizes of the two are not equal, there is no need to compare if () != () {
return false
}
// Iterative query traversal for key := range {
// Return false as long as there is no existence if !(key) {
return false
}
}
return true
}
Subset
Deciding whether A is a subset of B is also a process of cyclic traversal. The specific analysis has been described above, and the implementation method is as follows:
func (s *Set) IsSubset(other *Set) bool {
// s' size is longer than other, needless to say if () > () {
return false
}
// Iterative traversal for key := range {
if !(key) {
return false
}
}
return true
}
Ok, the above is the main function implementation method of Set in Go, which is still very interesting. Keep working hard. I also hope everyone supports me.