type Tree[E cmp.Ordered] struct { root *node[E] } func (t *Tree[E]) Insert(element E) { t.root = t.root.insert(element) } type node[E cmp.Ordered] struct { value E left *node[E] right *node[E] } func (n *node[E]) insert(element E) *node[E] { if n == nil { return &node[E]{value: element} } switch { case element < n.value: n.left = n.left.insert(element) case element > n.value: n.right = n.right.insert(element) } return n }这样写很直观,但有个问题:它只适用于内置可比较的类型(int、string 等)。如果我想存 time.Time 呢?就用不了了。
type FuncTree[E any] struct { root *funcNode[E] cmp func(E, E) int } func NewFuncTree[E any](cmp func(E, E) int) *FuncTree[E] { return &FuncTree[E]{cmp: cmp} } // 堆代码 duidaima.com func (t *FuncTree[E]) Insert(element E) { t.root = t.root.insert(t.cmp, element) }这当然能跑,但有两个缺点:
type Comparer interface { Compare(Comparer) int }看似不错,但写起来很尴尬:方法参数是 Comparer,每个类型都要强转回来,非常不 Go。
type Comparer[T any] interface { Compare(T) int }这样就好多了。比如 time.Time 有个 Compare(Time) int 方法,自然就实现了 Comparer[time.Time]。进一步,我们就能写一个支持自比较的树:
type MethodTree[E Comparer[E]] struct { root *methodNode[E] } func (t *MethodTree[E]) Insert(element E) { t.root = t.root.insert(element) } type methodNode[E Comparer[E]] struct { value E left *methodNode[E] right *methodNode[E] } func (n *methodNode[E]) insert(element E) *methodNode[E] { if n == nil { return &methodNode[E]{value: element} } sign := element.Compare(n.value) switch { case sign < 0: n.left = n.left.insert(element) case sign > 0: n.right = n.right.insert(element) } return n }好处是:
2.容器仍然支持零值初始化。
type OrderedSet[E Comparer[E]] struct { tree MethodTree[E] elements map[E]bool } func (s *OrderedSet[E]) Has(e E) bool { return s.elements[e] }结果编译报错:
invalid map key type E (missing comparable constraint)因为 Go 要求 map key 必须是 comparable。
type OrderedSet[E interface { comparable Comparer[E] }] struct { ... }哪种方式用,看团队习惯,但推荐避免不必要的全局约束,尽量在具体类型上加。
type Set[E any] interface { Insert(E) Delete(E) Has(E) bool All() iter.Seq[E] }这里的泛型参数最好只约束成 any,而不是强加 comparable 或 Comparer,因为不同实现有不同需求。例如基于 map 的实现必须要求 comparable,而基于 Tree 的则不需要。
type PtrToSet[S, E any] interface { *S Set[E] } func Unique[E, S any, PS PtrToSet[S, E]](...) { ... }这样写虽然麻烦,但至少能表达出“S 的指针实现了 Set”这个语义。Go 编译器还能帮我们推断最后一个参数,使用时还算顺手。
func InsertAll[E any](set Set[E], seq iter.Seq[E]) { for v := range seq { set.Insert(v) } }这样简单明了,还能让不同实现的 Set 都能复用。
type HashSet[E comparable] map[E]bool func (s HashSet[E]) Insert(v E) { s[v] = true } func (s HashSet[E]) Delete(v E) { delete(s, v) } func (s HashSet[E]) Has(v E) bool { return s[v] } func (s HashSet[E]) All() iter.Seq[E] { return maps.Keys(s) }用接口值,而不是复杂约束,往往更容易读懂,也更灵活。
4.如果因为指针接收者搞出很复杂的泛型函数签名,不妨退一步,改用接口值。