出于学习目的,我正在Go中进行简单的链表实现。元素的定义如下:
type Element struct {
next, prev *Element
Value interface{}
}
如您所见,值可以是满足空接口的任何值。现在,作为一项新功能,我要使其成为新功能,以便在将新元素插入列表时,它以排序方式插入它-每个元素将是<=下一个。
为了做到这一点,我编写了以下方法:
func (l *LinkedList) Add(val interface{}) *Element {
this := &l.Root
e := Element{Value: val}
for {
if this.next.Value != nil && this.next.Value < val { // <-comparison here
this = this.next
} else {
return l.insert(&e, this)
}
}
}
编译器抱怨operator < not defined on interface
这是公平的。因此,我知道在Element typedef中,我应该将Value限制为可以使用<
运算符进行比较的类型。在研究Go不支持运算符重载的问题时,我学到了这一点-我不是在尝试这样做。相反,我只是试图确保Element.Value是可以使用<
运算符进行比较的类型。我该怎么做?
在我看来,基于内置函数简单定义一个新类型可能并不难,可以通过某些功能进行比较。所以我写了这个烂摊子(以及尝试做同一件事的其他方法):
type Comparable interface {
LessThan(j interface{}) bool // tried (j Comparable), (j MyInt), etc
EqualTo(j interface{}) bool // tried (j Comparable), (j MyInt), etc
}
type MyInt int
func (i MyInt) LessThan(j MyInt) bool {
return i < j
}
func (i MyInt) EqualTo(j MyInt) bool {
return i == j
}
type Element struct {
next, prev *Element
Value Comparable
}
我真正想要的是定义一个接口,如果为一个类型实现,则提供函数LessThan
和EqualTo
,该函数在该类型的两个实例上运行并提供布尔值-类似于LessThan(i, j WhatEvers) bool
这样的接口代替<
。我意识到下面它是作为实例方法实现的-我已经尝试了两种方法,但没有成功。通过以上操作,我将使用类似:Add函数中的this.next.Value.LessThan(val)
。我得到:
linkedlist.MyInt does not implement linkedlist.Comparable (wrong type for EqualTo method)
have EqualTo(linkedlist.MyInt) bool
want EqualTo(interface {}) bool
或
linkedlist.MyInt does not implement linkedlist.Comparable (wrong type for EqualTo method)
have EqualTo(linkedlist.MyInt) bool
want EqualTo(linkedlist.Comparable) bool
是否有可能使用接口来要求必须存在对自定义类型的两个实例进行操作的某个函数,或者仅用于方法?
编辑:考虑此用户类型:
type userType struct {
frequency int
value rune
}
并且假设您要将以下类型添加到链接列表中:并应首先按频率排序,然后如果频率相同,请查看char值。因此Compare
功能为:
func (a userType) Compare(b userType) int {
if a.frequency > b.frequency {
return 1
}
if a.frequency < b.frequency {
return -1
}
if a.value > b.value {
return 1
}
if a.value < b.value {
return -1
}
return 0
}
满足此接口:
type Comparer interface {
Compare(b userType) int
}
现在将这些{1,'d'} {2,'b'} {3,'c'} {4,'a'} {4,'b'} {4,'c'}
类型添加到LinkeList:示例代码:
package main
import (
"container/list"
"fmt"
)
type Comparer interface {
Compare(b userType) int
}
type userType struct {
frequency int
value rune
}
// it should sort by frequency first, then if the frequencies are the same, look at the char value.
func (a userType) Compare(b userType) int {
if a.frequency > b.frequency {
return 1
}
if a.frequency < b.frequency {
return -1
}
if a.value > b.value {
return 1
}
if a.value < b.value {
return -1
}
return 0
}
func Insert(val userType, l *list.List) {
e := l.Front()
if e == nil {
l.PushFront(val)
return
}
for ; e != nil; e = e.Next() {
var ut userType = e.Value.(userType)
if val.Compare(ut) < 0 {
l.InsertBefore(val, e)
return
}
}
l.PushBack(val)
}
func main() {
l := list.New()
Insert(userType{4, 'c'}, l)
Insert(userType{4, 'a'}, l)
Insert(userType{4, 'b'}, l)
Insert(userType{2, 'b'}, l)
Insert(userType{3, 'c'}, l)
Insert(userType{1, 'd'}, l)
for e := l.Front(); e != nil; e = e.Next() {
ut := e.Value.(userType)
fmt.Printf("{%d,%q} ", ut.frequency, ut.value)
}
fmt.Println()
var t interface{} = userType{4, 'c'}
i, ok := t.(Comparer)
fmt.Println(i, ok)
}
和输出:
{1,'d'} {2,'b'} {3,'c'} {4,'a'} {4,'b'} {4,'c'}
{4 99} true
因此,如果您准备使用已知类型(例如int
),请参见以下示例:
package main
import (
"container/list"
"fmt"
)
func Insert(val int, l *list.List) {
e := l.Front()
if e == nil {
l.PushFront(val)
return
}
for ; e != nil; e = e.Next() {
v := e.Value.(int)
if val < v {
l.InsertBefore(val, e)
return
}
}
l.PushBack(val)
}
func main() {
l := list.New()
Insert(4, l)
Insert(2, l)
Insert(3, l)
Insert(1, l)
for e := l.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value, " ") // 1 2 3 4
}
fmt.Println()
}
旧:
Go中没有这样的界面。您可以编写此Less
函数来比较您的类型:
func Less(a, b interface{}) bool {
switch a.(type) {
case int:
if ai, ok := a.(int); ok {
if bi, ok := b.(int); ok {
return ai < bi
}
}
case string:
if ai, ok := a.(string); ok {
if bi, ok := b.(string); ok {
return ai < bi
}
}
// ...
default:
panic("Unknown")
}
return false
}
测试示例代码:
package main
import (
"container/list"
"fmt"
)
func Less(a, b interface{}) bool {
switch a.(type) {
case int:
if ai, ok := a.(int); ok {
if bi, ok := b.(int); ok {
return ai < bi
}
}
case string:
if ai, ok := a.(string); ok {
if bi, ok := b.(string); ok {
return ai < bi
}
}
default:
panic("Unknown")
}
return false
}
func Insert(val interface{}, l *list.List) *list.Element {
e := l.Front()
if e == nil {
return l.PushFront(val)
}
for ; e != nil; e = e.Next() {
if Less(val, e.Value) {
return l.InsertBefore(val, e)
}
}
return l.PushBack(val)
}
func main() {
l := list.New()
Insert(4, l)
Insert(2, l)
Insert(3, l)
Insert(1, l)
for e := l.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value, " ")
}
fmt.Println()
Insert("C", l)
Insert("A", l)
Insert("AB", l)
Insert("C", l)
Insert("C2", l)
Insert("C1", l)
for e := l.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value, " ")
}
fmt.Println()
}
输出:
1 2 3 4
1 2 3 4 A AB C C C1 C2
这是我已经可以做的一个可能的答案,但是它是如此丑陋,(减少了对一个int值的每次比较-可能适用于字符串,但对于其他类型却很费力)-我不想接受它:
type MyInt int
type Valuer interface {
ValueOf() int
}
func LessThan(i, j Valuer) bool {
return i.ValueOf() < j.ValueOf()
}
func EqualTo(i, j Valuer) bool {
return i.ValueOf() == j.ValueOf()
}
func (i MyInt) ValueOf() int {
return int(i)
}
type Element struct {
next, prev *Element
Value Valuer
}
有人请告诉我,还有更好的方法!