为什么在golang的list/ring中使用Element和Ring结构体?

huangapple go评论117阅读模式
英文:

Why the Element and Ring structs for golang list/ring?

问题

为什么golang中的列表/环类型使用额外的结构体Element/Ring来表示各个项,而不是使用interface{}?我猜想这样做有一些好处,但我无法看出来。

编辑:我想问的是关于API的问题,而不是关于在实现中使用Element/Ring的问题。实现仍然可以使用非导出类型,但API可以使用interface{}来传递参数和返回值,那么为什么要让用户直接使用Element/Ring?

编辑2:以Back()函数为例,列表的实现可以是这样的:

func (l *List) Back() interface{} {
    if l.len == 0 {
        return nil
    }
    return l.root.prev.Value
}

在内部仍然使用Element,但是它只是一个非导出类型,因为它不会返回Element本身,只返回其值。

英文:

Why do the list/ring types in golang use the extra structs Element/Ring for the individual items and not interface{} ? I am assuming there is some benefit but I cannot see it.

Edit: I meant to ask about the api and NOT about the use of Element/Ring in the implementation. The implementation could still use a non exported type but have the api give and take an interface{}, so why make the users go in and out of Element/Ring?

Edit2: As an example the list Back() function could be like

func (l *List) Back() interface{} {
    if l.len == 0 {
        return nil
    }
    return l.root.prev.Value
}

Where the list still uses Element internally but it would be just element (unexported) since it wouldn't return it but only return the value.

答案1

得分: 4

container/list是一个链表,因此拥有一个可以对整个链表进行操作并跟踪链表开头和结尾的List结构体将会很有益处。

由于它是一个链表,你希望能够将项目链接在一起并从一个项目导航到下一个或上一个项目。这需要一个结构体,它保存指向下一个和上一个项目的指针,并允许你导航到这些项目(使用Next()和Prev()函数)。Element结构体就是为此目的而设计的,它包含指向下一个/上一个项目和实际值的指针。

下面是这些结构体的定义,它们还有各种成员函数:

type List struct {
    root Element // 哨兵元素,只使用 &root、root.prev 和 root.next
    len  int     // 当前链表长度,不包括(这个)哨兵元素
}

type Element struct {
    // 双向链表中的下一个和上一个指针。
    // 为了简化实现,内部将链表 l 实现为一个环,使得 &l.root 既是最后一个列表元素(l.Back())的下一个元素,也是第一个列表元素(l.Front())的上一个元素。
    next, prev *Element

    // 此元素所属的链表。
    list *List

    // 存储在此元素中的值。
    Value interface{}
}

container/ring并没有像你所暗示的那样有一个“额外”的结构体。只有Ring结构体,它将一个项目链接到下一个/上一个项目,并保存值。Ring没有开始/结束的概念,因此不需要有一个操作整个Ring或跟踪开始的结构体。

type Ring struct {
    next, prev *Ring
    Value      interface{} // 供客户端使用;本库不修改该值
}
英文:

container/list is linked list, so it'll be beneficial to have List struct that can operate on the list as a whole and keep track of the beginning and end of a list.

Since it's a linked list, you want to be able to link items together and navigate from one item to the next or the previous item. That requires a struct that hold pointers to the next and the previous item as well as allowing you to navigate to those items (with the Next() and Prev() functions). The Element struct serves that purpose, it contains pointers to the next/previous item, and the actual value.

Here's how the struct's are defined, and they have various member functions as well

type List struct {
    root Element // sentinel list element, only &root, root.prev, and root.next are used
    len  int     // current list length excluding (this) sentinel element
}

type Element struct {
    // Next and previous pointers in the doubly-linked list of elements.
    // To simplify the implementation, internally a list l is implemented
    // as a ring, such that &l.root is both the next element of the last
    // list element (l.Back()) and the previous element of the first list
    // element (l.Front()).
    next, prev *Element

    // The list to which this element belongs.
    list *List

    // The value stored with this element.
    Value interface{}
}

container/ring does not have an "extra" struct as you imply. There's only the Ring struct which links one item to the next/previous item and also holds the value. There's no start/end of a Ring, so there's no need to have a struct that operates on a ring as a whole or keeps track of the start.

type Ring struct {
    next, prev *Ring
    Value      interface{} // for use by client; untouched by this library
}

答案2

得分: 3

它们包含过滤或未导出的字段。


Package list

文件 list.go:

// Package list 实现了一个双向链表。

// Element 是链表的一个元素。
type Element struct {
    // 在双向链表中的下一个和上一个元素的指针。
    // 为了简化实现,列表 l 在内部被实现为一个环,
    // 这样 &l.root 既是最后一个列表元素(l.Back())的下一个元素,
    // 也是第一个列表元素(l.Front())的上一个元素。
    next, prev *Element

    // 此元素所属的列表。
    list *List

    // 存储在此元素中的值。
    Value interface{}
}

Package ring

文件 ring.go:

// Package ring 实现了环形链表的操作。

// Ring 是环形链表的一个元素。
// 环形链表没有开始或结束;对任何环形链表元素的指针都可以作为整个环形链表的引用。
// 空环形链表表示为 nil Ring 指针。Ring 的零值是一个具有 nil Value 的单元素环形链表。
//
type Ring struct {
    next, prev *Ring
    Value      interface{} // 供客户端使用;此库不修改其值
}

显然,ElementRing 的类型不能是 interface{},因为这没有意义。你不能在接口类型上定义方法。

> Go 编程语言规范
>
> 方法声明
>
> 方法是带有接收器的函数。方法声明将标识符(方法名)绑定到方法,并将方法与接收器的基本类型关联起来。
>
> MethodDecl = "func" Receiver MethodName ( Function | Signature ) .
> Receiver = "(" [ identifier ] [ "*" ] BaseTypeName ")" .
> BaseTypeName = identifier .
>
> 接收器类型必须是 T 或 *T 的形式,其中 T 是类型名。
> T 所表示的类型称为接收器的基本类型;它不能是指针或接口类型,并且必须在与方法相同的包中声明。
> 该方法被绑定到基本类型,并且方法名仅在该类型的选择器中可见。

英文:

They contain filtered or unexported fields.


Package list

File list.go:

// Package list implements a doubly linked list.

// Element is an element of a linked list.
type Element struct {
	// Next and previous pointers in the doubly-linked list of elements.
	// To simplify the implementation, internally a list l is implemented
	// as a ring, such that &l.root is both the next element of the last
	// list element (l.Back()) and the previous element of the first list
	// element (l.Front()).
	next, prev *Element

	// The list to which this element belongs.
	list *List

	// The value stored with this element.
	Value interface{}
}

Package ring

File ring.go:

// Package ring implements operations on circular lists.

// A Ring is an element of a circular list, or ring.
// Rings do not have a beginning or end; a pointer to any ring element
// serves as reference to the entire ring. Empty rings are represented
// as nil Ring pointers. The zero value for a Ring is a one-element
// ring with a nil Value.
//
type Ring struct {
	next, prev *Ring
	Value      interface{} // for use by client; untouched by this library
}

Obviously, the type of Element and Ring can't be interface{} because it would make no sense. You can't have a method on an interface type.

> The Go Programming Language Specification
>
> Method declarations
>
> A method is a function with a receiver. A method declaration binds an
> identifier, the method name, to a method, and associates the method
> with the receiver's base type.
>
> MethodDecl = "func" Receiver MethodName ( Function | Signature ) .
> Receiver = "(" [ identifier ] [ "*" ] BaseTypeName ")" .
> BaseTypeName = identifier .
>
> The receiver type must be of the form T or *T where T is a type name.
> The type denoted by T is called the receiver base type; it must not be
> a pointer or interface type and it must be declared in the same
> package as the method. The method is said to be bound to the base type
> and the method name is visible only within selectors for that type.

huangapple
  • 本文由 发表于 2014年6月18日 04:32:10
  • 转载请务必保留本文链接:https://go.coder-hub.com/24272789.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定