泛型

最初的Go是没有泛型这一说法的，但自从诞生以来，社区关于Go呼声最高的事情就是希望加入泛型。终于Go在1.18版本加入了对泛型的支持，不过有一点怪。

示例

在开始之前，先来看一个简单的例子。

func Sum(a, b int) int {
   return a + b
}

这是一个功能十分简单的函数，作用就是将两个int类型的整数相加并返回结果，倘若想要传入两个float64类型的浮点数求和的话，显然是不可以的，因为类型不匹配。一种解决办法就是再定义一个新的函数，如下

func SumFloat64(a, b float64) float64 {
	return a + b
}

那么问题来了，如果开发一个数学工具包，计算所有数字类型的两数之和，难道要每一个类型都要编写一个函数吗？显然是不太可能的，或者也可以使用any类型加反射来判断，如下

func SumAny(a, b any) (any, error) {
	tA, tB := reflect.ValueOf(a), reflect.ValueOf(b)
	if tA.Kind() != tB.Kind() {
		return nil, errors.New("disMatch type")
	}

	switch tA.Kind() {
	case reflect.Int:
	case reflect.Int32:
		...
	}
}

但是这样写会显得十分复杂，而且性能低下。但是Sum函数的逻辑都是一模一样的，都只不过是将两个数相加而已，这时候就需要用到了泛型，所以为什么需要泛型，泛型是为了解决执行逻辑与类型无关的问题，这类问题不关心给出的类型是什么，只需要完成对应的操作就足够。所以泛型的写法如下

func Sum[T int | float64](a, b T) T {
   return a + b
}

类型形参：T就是一个类型形参，形参具体是什么类型取决于传进来什么类型

类型约束：int | float64构成了一个类型约束，这个类型约束内规定了哪些类型是允许的，约束了类型形参的类型范围

类型实参：Sum[int](1,2)，手动指定了int类型，int就是类型实参。

第一种用法，显式的指明使用哪种类型，如下

Sum[int](2012, 2022)

第二种用法，不指定类型，让编译器自行推断，如下

Sum(3.1415926, 1.114514)

看到这里后，应该对为什么要使用泛型，以及泛型解决了哪种问题有了一个大概的了解。将泛型引入项目后，开发上确实会比较方便，随之而来的是项目复杂度的增加，毫无节制的使用泛型会使得代码难以维护，所以应该在正确的地方使用泛型，而不是为了泛型而泛型。

泛型结构

这是一个泛型切片，类型约束为int | int32 | int64

type GenericSlice[T int | int32 | int64] []T

这里使用时就不能省略掉类型实参

GenericSlice[int]{1, 2, 3}

这是一个泛型哈希表，键的类型必须是可比较的，所以使用comparable接口，值的类型约束为V int | string | byte

type GenericMap[K comparable, V int | string | byte] map[K]V

使用

gmap1 := GenericMap[int, string]{1: "hello world"}
gmap2 := make(GenericMap[string, byte], 0)

这是一个泛型结构体，类型约束为T int | string

type GenericStruct[T int | string] struct {
   Name string
   Id   T
}

使用

GenericStruct[int]{
   Name: "jack",
   Id:   1024,
}
GenericStruct[string]{
   Name: "Mike",
   Id:   "1024",
}

这是一个泛型切片形参的例子

type Company[T int | string, S []T] struct {
   Name  string
   Id    T
   Stuff S
}

//也可以如下
type Company[T int | string, S []int | string] struct {
	Name  string
	Id    T
	Stuff S
}

使用

Company[int, []int]{
   Name:  "lili",
   Id:    1,
   Stuff: []int{1},
}

提示

在泛型结构体中，更推荐这种写法

type Company[T int | string, S int | string] struct {
	Name  string
	Id    T
	Stuff []S
}

SayAble是一个泛型接口，Person实现了该接口。

type SayAble[T int | string] interface {
   Say() T
}

type Person[T int | string] struct {
   msg T
}

func (p Person[T]) Say() T {
   return p.msg
}

func main() {
	var s SayAble[string]
	s = Person[string]{"hello world"}
	fmt.Println(s.Say())
}

泛型结构注意点

泛型不能作为一个类型的基本类型

以下写法是错误的，泛型形参T是不能作为基础类型的

type GenericType[T int | int32 | int64] T

虽然下列的写法是允许的，不过毫无意义而且可能会造成数值溢出的问题，虽然并不推荐

type GenericType[T int | int32 | int64] int

泛型类型无法使用类型断言

对泛型类型使用类型断言将会无法通过编译，泛型要解决的问题是类型无关的，如果一个问题需要根据不同类型做出不同的逻辑，那么就根本不应该使用泛型，应该使用interface{}或者any。

func Sum[T int | float64](a, b T) T {
   ints,ok := a.(int) // 不被允许
   switch a.(type) { // 不被允许
   case int:
   case bool:
      ...
   }
   return a + b
}

匿名结构不支持泛型

匿名结构体是不支持泛型的，如下的代码将无法通过编译

testStruct := struct[T int | string] {
   Name string
   Id T
}[int]{
   Name: "jack",
   Id: 1  
}

匿名函数不支持自定义泛型

以下两种写法都将无法通过编译

var sum[T int | string] func (a, b T) T
sum := func[T int | string](a,b T) T{
    ...
}

但是可以使用已有的泛型类型，例如闭包中

func Sum[T int | float64](a, b T) T {
	sub := func(c, d T) T {
		return c - d
	}
	return sub(a,b) + a + b
}

不支持泛型方法

方法是不能拥有泛型形参的，但是receiver可以拥有泛型形参。如下的代码将会无法通过编译

type GenericStruct[T int | string] struct {
   Name string
   Id   T
}

func (g GenericStruct[T]) name[S int | float64](a S) S {
   return a
}

类型集

在1.18以后，接口的定义变为了类型集(type set)，含有类型集的接口又称为General interfaces即通用接口。

An interface type defines a type set

类型集主要用于类型约束，不能用作类型声明，既然是集合，就会有空集，并集，交集，接下来将会讲解这三种情况。

并集

接口类型SignedInt是一个类型集，有符号整数类型的并集就是SignedInt，反过来SignedInt就是它们的超集。

type SignedInt interface {
   int8 | int16 | int | int32 | int64
}

基本数据类型如此，对待其它通用接口也是如此

type SignedInt interface {
	int8 | int16 | int | int32 | int64
}

type UnSignedInt interface {
	uint8 | uint16 | uint32 | uint64
}

type Integer interface {
	SignedInt | UnSignedInt
}

交集

非空接口的类型集是其所有元素的类型集的交集，翻译成人话就是：如果一个接口包含多个非空类型集，那么该接口就是这些类型集的交集，例子如下

type SignedInt interface {
   int8 | int16 | int | int32 | int64
}

type Integer interface {
   int8 | int16 | int | int32 | int64 | uint8 | uint16 | uint | uint32 | uint64
}

type Number interface {
	SignedInt
	Integer
}

例子中的交集肯定就是SignedInt，

func Do[T Number](n T) T {
   return n
}

Do[int](2)
DO[uint](2) //无法通过编译

空集

空集就是没有交集，例子如下，下面例子中的Integer就是一个类型空集。

type SignedInt interface {
	int8 | int16 | int | int32 | int64
}

type UnsignedInt interface {
	uint8 | uint16 | uint | uint32 | uint64
}

type Integer interface {
	SignedInt
	UnsignedInt
}

因为无符号整数和有符号整数两个肯定没有交集，所以交集就是个空集，下方例子中不管传什么类型都无法通过编译。

Do[Integer](1)
Do[Integer](-100)

空接口

空接口与空集并不同，空接口是所有类型集的集合，即包含所有类型。

func Do[T interface{}](n T) T {
   return n
}

func main() {
   Do[struct{}](struct{}{})
   Do[any]("abc")
}

底层类型

当使用type关键字声明了一个新的类型时，即便其底层类型包含在类型集内，当传入时也依旧会无法通过编译。

type Int interface {
   int8 | int16 | int | int32 | int64 | uint8 | uint16 | uint | uint32 | uint64
}

type TinyInt int8

func Do[T Int](n T) T {
   return n
}

func main() {
   Do[TinyInt](1) // 无法通过编译，即便其底层类型属于Int类型集的范围内
}

有两种解决办法，第一种是往类型集中并入该类型，但是这毫无意义，因为TinyInt与int8底层类型就是一致的，所以就有了第二种解决办法。

type Int interface {
   int8 | int16 | int | int32 | int64 | uint8 | uint16 | uint | uint32 | uint64 | TinyInt
}

使用~符号，来表示底层类型，如果一个类型的底层类型属于该类型集，那么该类型就属于该类型集，如下所示

type Int interface {
   ~int8 | ~int16 | ~int | ~int32 | ~int64 | ~uint8 | ~uint16 | ~uint | ~uint32 | ~uint64
}

修改过后就可以通过编译了。

func main() {
   Do[TinyInt](1) // 可以通过编译，因为TinyInt在类型集Int内
}

类型集注意点

带有方法集的接口无法并入类型集

只要是带有方法集的接口，不论是基本接口，泛型接口，又或者是通用接口，都无法并入类型集中，同样的也无法在类型约束中并入。以下两种写法都是错误的，都无法通过编译。

type Integer interface {
	Sum(int, int) int
	Sub(int, int) int
}

type SignedInt interface {
   int8 | int16 | int | int32 | int64 | Integer
}

func Do[T Integer | float64](n T) T {
	return n
}

类型集无法当作类型实参使用

只要是带有类型集的接口，都无法当作类型实参。

type SignedInt interface {
	int8 | int16 | int | int32 | int64
}

func Do[T SignedInt](n T) T {
   return n
}

func main() {
   Do[SignedInt](1) // 无法通过编译
}

类型集中的交集问题

对于非接口类型，类型并集中不能有交集，例如下例中的TinyInt与~int8有交集。

type Int interface {
   ~int8 | ~int16 | ~int | ~int32 | ~int64 | ~uint8 | ~uint16 | ~uint | ~uint32 | ~uint64 | TinyInt // 无法通过编译
}

type TinyInt int8

但是对于接口类型的话，就允许有交集，如下例

type Int interface {
   ~int8 | ~int16 | ~int | ~int32 | ~int64 | ~uint8 | ~uint16 | ~uint | ~uint32 | ~uint64 | TinyInt // 可以通过编译
}

type TinyInt interface {
	int8
}

类型集不能直接或间接的并入自身

以下示例中，Floats 直接的并入了自身，而Double又并入了Floats，所以又间接的并入了自身。

type Floats interface {  // 代码无法通过编译
   Floats | Double
}

type Double interface {
   Floats
}

comparable接口无法并入类型集

同样的，也无法并入类型约束中，所以基本上都是单独使用。

func Do[T comparable | Integer](n T) T { //无法通过编译
   return n
}

type Number interface { // 无法通过编译
	Integer | comparable
}

type Comparable interface { // 可以通过编译但是毫无意义
	comparable
}

使用

数据结构是泛型最常见的使用场景，下面借由两个数据结构来展示下泛型如何使用。

队列

下面用泛型实现一个简单的队列，首先声明队列类型，队列中的元素类型可以是任意的，所以类型约束为any

type Queue[T any] []T

总共只有四个方法Pop ，Peek，Push，Size，代码如下。

type Queue[T any] []T

func (q *Queue[T]) Push(e T) {
	*q = append(*q, e)
}

func (q *Queue[T]) Pop(e T) (_ T) {
	if q.Size() > 0 {
		res := q.Peek()
		*q = (*q)[1:]
		return res
	}
	return
}

func (q *Queue[T]) Peek() (_ T) {
	if q.Size() > 0 {
		return (*q)[0]
	}
	return
}

func (q *Queue[T]) Size() int {
	return len(*q)
}

在Pop和Peek方法中，可以看到返回值是_ T，这是具名返回值的使用方式，但是又采用了下划线_表示这是匿名的，这并非多此一举，而是为了表示泛型零值。由于采用了泛型，当队列为空时，需要返回零值，但由于类型未知，不可能返回具体的类型，借由上面的那种方式就可以返回泛型零值。也可以声明泛型变量的方式来解决零值问题，对于一个泛型变量，其默认的值就是该类型的零值，如下

func (q *Queue[T]) Pop(e T) T {
    var res T
	if q.Size() > 0 {
		res = q.Peek()
		*q = (*q)[1:]
		return res
	}
	return res
}

堆

上面队列的例子，由于对元素没有任何的要求，所以类型约束为any。但堆就不一样了，堆是一种特殊的数据结构，它可以在O(1)的时间内判断最大或最小值，所以它对元素有一个要求，那就是必须是可以排序的类型，但内置的可排序类型只有数字和字符串，并且go的泛型约束不允许存在带方法的接口，所以在堆的初始化时，需要传入一个自定义的比较器，比较器由使用者提供，比较器也必须使用泛型，如下

type Comparator[T any] func(a, b T) int

下面是一个简单的二项最小堆的实现，先声明泛型结构体，依旧采用any进行约束，这样可以存放任意类型

type Comparator[T any] func(a, b T) int

type BinaryHeap[T any] struct {
	s []T
	c Comparator[T]
}

几个方法实现

func (heap *BinaryHeap[T]) Peek() (_ T) {
	if heap.Size() > 0 {
		return heap.s[0]
	}
	return
}

func (heap *BinaryHeap[T]) Pop() (_ T) {
	size := heap.Size()
	if size > 0 {
		res := heap.s[0]
		heap.s[0], heap.s[size-1] = heap.s[size-1], heap.s[0]
		heap.s = heap.s[:size-1]
		heap.down(0)
		return res
	}
	return
}

func (heap *BinaryHeap[T]) Push(e T) {
	heap.s = append(heap.s, e)
	heap.up(heap.Size() - 1)
}

func (heap *BinaryHeap[T]) up(i int) {
	if heap.Size() == 0 || i < 0 || i >= heap.Size() {
		return
	}
	for parentIndex := i>>1 - 1; parentIndex >= 0; parentIndex = i>>1 - 1 {
		// greater than or equal to
		if heap.compare(heap.s[i], heap.s[parentIndex]) >= 0 {
			break
		}
		heap.s[i], heap.s[parentIndex] = heap.s[parentIndex], heap.s[i]
		i = parentIndex
	}
}

func (heap *BinaryHeap[T]) down(i int) {
	if heap.Size() == 0 || i < 0 || i >= heap.Size() {
		return
	}
	size := heap.Size()
	for lsonIndex := i<<1 + 1; lsonIndex < size; lsonIndex = i<<1 + 1 {
		rsonIndex := lsonIndex + 1

		if rsonIndex < size && heap.compare(heap.s[rsonIndex], heap.s[lsonIndex]) < 0 {
			lsonIndex = rsonIndex
		}

		// less than or equal to
		if heap.compare(heap.s[i], heap.s[lsonIndex]) <= 0 {
			break
		}
		heap.s[i], heap.s[lsonIndex] = heap.s[lsonIndex], heap.s[i]
		i = lsonIndex
	}
}

func (heap *BinaryHeap[T]) Size() int {
	return len(heap.s)
}

使用起来如下

type Person struct {
	Age  int
	Name string
}

func main() {
	heap := NewHeap[Person](10, func(a, b Person) int {
		return cmp.Compare(a.Age, b.Age)
	})
	heap.Push(Person{Age: 10, Name: "John"})
	heap.Push(Person{Age: 18, Name: "mike"})
	heap.Push(Person{Age: 9, Name: "lili"})
	heap.Push(Person{Age: 32, Name: "miki"})
	fmt.Println(heap.Peek())
	fmt.Println(heap.Pop())
	fmt.Println(heap.Peek())
}

输出

{9 lili}
{9 lili} 
{10 John}

有泛型的加持，原本不可排序的类型传入比较器后也可以使用堆了，这样做肯定比以前使用interface{}来进行类型转换和断言要优雅和方便很多。

小结

go的一大特点就是编译速度非常快，编译快是因为编译期做的优化少，泛型的加入会导致编译器的工作量增加，工作更加复杂，这必然会导致编译速度变慢，事实上当初go1.18刚推出泛型的时候确实导致编译更慢了，go团队既想加入泛型又不想太拖累编译速度，开发者用的顺手，编译器就难受，反过来编译器轻松了（最轻松的当然是直接不要泛型），开发者就难受了，现如今的泛型就是这两者之间妥协后的产物。

提示

如果想要了解更多关于泛型的实际案例，可以看看这个泛型数据结构库246859/containers: base data structure in go genericity (github.com)。如果想要了解更多关于泛型的一些设计理念和细节，可以前往Type Parameters Proposal (googlesource.com)。