在 Go 中构建您自己的全功能 Set 类型

很多人学习 Go 时发现的一件更令人沮丧的事情是缺少集合类型，例如 Sets 及其常用操作。在本文中，我们将展示 Go 1.19 中泛型的引入如何让我们能够构建自己的功能齐全的 Set 类型。

您可能熟悉非常有用的数据收集类型 Set。Set 是唯一项的无序集合。通常集合是使用 Hashmap 实现的，Hashmap 查找值的时间复杂度为 O(1)（假设没有哈希冲突）。集合有 4 个主要操作，使它们特别有用：

  1. Union ( A ⋃ B ) — 并集是包含集合 A 和 B 中所有元素的集合。
  2. Intersection ( A ∩ B ) — 交集是包含集合 A 和 B 中相交元素的集合。
  3. Complement ( A c) — 补集是通用集合 S 中但不在 A 中的元素集合。我们将忽略补集，因为它由 Difference 处理。
  4. Difference ( A − B ) — 差集是 A 中但不在 B 中的元素的集合。

让我们开始在 Go 中定义我们的 Set 类型。首先，我们要定义 Set 是什么，使用泛型我们可以利用约束轻松扩展 Set 类型以处理大量数据类型。

package collections

// A collection of unique comparable items. Uses a map with only true values
// to accomplish set functionality.
type Set[T comparable] map[T]bool

// Create a new empty set with the specified initial size.
func NewSet[T comparable](size int) Set[T] {
    return make(Set[T], size)
}

// Add a new key to the set
func (s Set[T]) Add(key T) {
    s[key] = true
}

// Remove a key from the set. If the key is not in the set then noop
func (s Set[T]) Remove(key T) {
    delete(s, key)
}

// Check if Set s contains key
func (s Set[T]) Contains(key T) bool {
    return s[key]
}

在第一部分中，我们创建了使用内置地图类型的 Set 类型。我们将映射的键限制为 Comparable 类型。从文档中，我们知道 Comparable 类型包括

（布尔值、数字、字符串、指针、通道、可比较类型的数组、字段都是可比较类型的结构）

Difference
// A difference B | NOTE: A-B != B-A
func (a Set[T]) Difference(b Set[T]) Set[T] {
    resultSet := NewSet[T](0)
    for key := range a {
        if !b.Contains(key) {
             resultSet.Add(key)
        }
    }
    return resultSet
}

AB
UnionIntersection
// A union B
func (a Set[T]) Union(b Set[T]) Set[T] {
    small, large := smallLarge(a, b)
    
    for key := range small {
        large.Add(key)
    }
    return large
}

// A intersect B
func (a Set[T]) Intersection(b Set[T]) Set[T] {
    small, large := smallLarge(a, b)
    
    resultSet := NewSet[T](0)
    for key := range small {
        if large.Contains(key) {
            resultSet.Add(key)
        }
    }
    return resultSet
}

// returns the small and large sets according to their len
func smallLarge[T comparable](a, b Set[T]) (Set[T], Set[T]) {
    small, large := b, a
    if len(b) > len(a) {
        small, large = a, b
    }
    
    return small, large
}

UnionIntersectionAB
smallLarge(a, b)

但是，在 Union 中，我们正在覆盖可能是 A 或 B 的大集合。如果我们想在合并时保留原始集合，我们将不得不循环遍历两个集合。

我们现在有一个功能齐全的 Set 包。通过更多的工作，我们可以为切片添加帮助器并添加更多实用方法，例如检查是否相等。

// A == B (all elements of A are in B and vice versa)
func (a Set[T]) Equals(b Set[T]) bool {
    return len(a.Difference(b)) == 0 && len(b.Difference(a)) == 0
}

// Create a Set from a slice.
func SliceToSet[T comparable](s []T) Set[T] {
   set := NewSet[T](len(s))
   for _, item := range s {
       set.Add(item)
   }
   return set
}

// Union two slices. The provided slices do not need to be unique. Order not guaranteed.
func SliceUnion[T comparable](a, b []T) []T {
   aSet, bSet := SliceToSet(a), SliceToSet(b)
   union := aSet.Union(bSet)
   return union.ToSlice()
}

// Intersection of two slices. The provided slices do not need to be unique. Order not guaranteed.
func SliceIntersection[T comparable](a, b []T) []T {
   aSet, bSet := SliceToSet(a), SliceToSet(b)
   intersection := aSet.Intersection(bSet)
   return intersection.ToSlice()
}

通过以上所有工作，我们能够执行如下所示的操作：

func TestSets(t *testing.T) {
   A := SliceToSet([]int{1, 3, 5})
   B := SliceToSet([]int{0, 1, 2, 3, 4})
  
   union := A.Union(B)
   fmt.Println(union) // map[0:true 1:true 2:true 3:true 4:true 5:true]
  
   C := SliceToSet([]string{"a", "b", "noah"})
   D := SliceToSet([]string{"a", "noah"})
   intersection := C.Intersection(D)
   fmt.Println(intersection) // map[a:true noah:true]
  
   fmt.Println(C.Equals(D)) // false
}

我希望你发现这篇文章有帮助！同样，所有代码都可以在 GitHub 上找到。

欢迎点赞，关注，转发，Happy Coding。