Go 实现简单的 Set


需求
对于 Set 类型的数据结构,其实本质上跟 List 没什么多大的区别。无非是 Set 不能含有重复的 Item 的特性,Set 有初始化、Add、Clear、Remove、Contains 等操作。

Go中Map的数据结构,Key是不允许重复的:

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

程序会直接报错,提示重复 Key 值,这样就非常符合 Set 的特性需求了。

定义
前面分析出 Set 的 Value 为固定的值,用一个常量替代即可。但是笔者分析的实现源码,用的是一个空结构体来实现的,如下所示:

// 空结构体
var Exists = struct{}{}
// Set is the main interface
type Set struct {
    // struct 为结构体类型的变量
    m map[interface{}]struct{}
}

为了解决上面为什么用空结构体来做常量 Value,先看下面的是测试:

import (
    "fmt"
    "unsafe"
)

// 定义非空结构体
type S struct {
    a uint16
    b uint32
}

func main() {
    var s S
    // prints 8, not 6
    fmt.Println(unsafe.Sizeof(s))
    var s2 struct{}
    // prints 0
    fmt.Println(unsafe.Sizeof(s2))
}

打印出空结构体变量的内存占用大小为0,再看看下面这个测试:

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

很有趣,a 和 b 竟然相等,并且 a 和 b 的地址也是一样的。

初始化
Set 类型数据结构的初始化操作,在声明的同时可以选择传入或者不传入进去。声明 Map 切片的时候,Key 可以为任意类型的数据,用空接口来实现即可。Value 的话按照上面的分析,用空结构体即可:

func New(items ...interface{}) *Set {
    // 获取 Set 的地址
    s := &Set{}
    // 声明 map 类型的数据结构
    s.m = make(map[interface{}]struct{})
    s.Add(items...)
    return s
}

添加
简化操作可以添加不定个数的元素进入到Set中,用变长参数的特性来实现这个需求即可,因为Map不允许Key值相同,所以不必有排重操作。同时将Value数值指定为空结构体类型。

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

包含
Contains操作其实就是查询操作,看看有没有对应的Item存在,可以利用Map的特性来实现,但是由于不需要Value的数值,所以可以用 _,ok来达到目的:

func (s *Set) Contains(item interface{}) bool {

_, ok := s.m[item]
return ok

}
长度和清除
获取Set长度很简单,只需要获取底层实现的Map的长度即可:

func (s *Set) Size() int {

return len(s.m)

}
清除操作的话,可以通过重新初始化Set来实现,如下即为实现过程:

func (s *Set) Clear() {

s.m = make(map[interface{}]struct{})

}
相等
判断两个Set是否相等,可以通过循环遍历来实现,即将A中的每一个元素,查询在B中是否存在,只要有一个不存在,A和B就不相等,实现方式如下所示:

func (s Set) Equal(other Set) bool {
// 如果两者Size不相等,就不用比较了

if s.Size() != other.Size() {
    return false
}

// 迭代查询遍历

for key := range s.m {
    // 只要有一个不存在就返回false
    if !other.Contains(key) {
        return false
    }
}
return true

}
子集
判断A是不是B的子集,也是循环遍历的过程,具体分析在上面已经讲述过,实现方式如下所示:

func (s Set) IsSubset(other Set) bool {

// s的size长于other,不用说了
if s.Size() > other.Size() {
    return false
}
// 迭代遍历
for key := range s.m {
    if !other.Contains(key) {
        return false
    }
}
return true

}

分享:

评论