闽公网安备 35020302035485号


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.如果因为指针接收者搞出很复杂的泛型函数签名,不妨退一步,改用接口值。