#list #go
#Список #Вперед
Вопрос:
Почему типы списков / колец в golang используют дополнительные структуры Element / Ring для отдельных элементов, а не interface{} ? Я предполагаю, что есть какая-то выгода, но я ее не вижу.
Редактировать: я хотел спросить об api, а НЕ об использовании Element / Ring в реализации. Реализация все равно может использовать неэкспортируемый тип, но api предоставляет и принимает интерфейс {}, так зачем заставлять пользователей входить и выходить из элемента / кольца?
Edit2: В качестве примера функция list Back() может быть такой
func (l *List) Back() interface{} {
if l.len == 0 {
return nil
}
return l.root.prev.Value
}
Где список по-прежнему использует элемент внутри, но это будет просто элемент (неэкспортированный), поскольку он не вернет его, а только вернет значение.
Ответ №1:
контейнер / список — это связанный список, поэтому будет полезно иметь List
структуру, которая может работать со списком в целом и отслеживать начало и конец списка.
Поскольку это связанный список, вы хотите иметь возможность связывать элементы вместе и переходить от одного элемента к следующему или предыдущему элементу. Для этого требуется структура, которая содержит указатели на следующий и предыдущий элемент, а также позволяет вам переходить к этим элементам (с помощью функций Next() и Prev()).). Element
Структура служит этой цели, она содержит указатели на следующий / предыдущий элемент и фактическое значение.
Вот как определяются структуры, и у них также есть различные функции-члены
type List struct {
root Element // sentinel list element, only amp;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 amp;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{}
}
контейнер / кольцо не имеет «дополнительной» структуры, как вы подразумеваете. Существует только структура кольца, которая связывает один элемент со следующим / предыдущим элементом, а также содержит значение. У кольца нет начала / конца, поэтому нет необходимости иметь структуру, которая работает с кольцом в целом или отслеживает начало.
type Ring struct {
next, prev *Ring
Value interface{} // for use by client; untouched by this library
}
Комментарии:
1. @cellige Как бы вы получили следующий / предыдущий элемент любым разумным способом в этом случае? Если вы находитесь на определенном узле и хотите получить следующий узел, вам нужно будет передать «текущее» значение в список. И реализация списка должна была бы линейно сканировать список, чтобы найти элемент, содержащий «текущее» значение, и возвращает его следующий указатель, что довольно ужасно.
2. @nos: реализации не нужно ничего сканировать линейно. Он может видеть неэкспортированные поля и использовать их напрямую для получения следующего или предыдущего узла.
3. @nos: кольцевая структура предоставляет указатели next и prev, используя методы в кольцевой структуре. Это позволяет реализации гарантировать, что никто не изменит указатели таким образом, чтобы нарушить инварианты контейнера.
4. @KenBloom Я говорю о случае, когда OP хочет, чтобы API напрямую принимал интерфейс {}, это звучит так, как будто он хочет иметь дело со значением напрямую, а не со структурой, которая переносит значение. (Или, скорее, какой смысл иметь дело с интерфейсом {} вместо элемента, если этот интерфейс {} действительно был просто элементом ?)
5. Да, @nos правильно понял мое значение. Мне интересно, почему они заставляют пользователя работать со значением внутри элемента, а не просто возвращать interface{} и использовать interface{} для функций push. Все еще использую element внутренне для отслеживания указателей.
Ответ №2:
Они содержат отфильтрованные или неэкспортированные поля.
Файл 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 amp;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{}
}
Файл 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
}
Очевидно, что тип Element
и Ring
не может быть interface{}
, потому что это не имело бы смысла. У вас не может быть метода для типа интерфейса.
Спецификация языка программирования Go
Метод — это функция с получателем. Объявление метода привязывает идентификатор, имя метода, к методу и связывает метод с базовым типом получателя.
MethodDecl = "func" Receiver MethodName ( Function | Signature ) . Receiver = "(" [ identifier ] [ "*" ] BaseTypeName ")" . BaseTypeName = identifier .
Тип получателя должен иметь вид T или *T, где T — имя типа.
Тип, обозначаемый T, называется базовым типом получателя; он не должен быть
типом указателя или интерфейса и должен быть объявлен в том же
пакете, что и метод. Говорят, что метод привязан к базовому типу
, и имя метода отображается только в селекторах для этого типа.
Комментарии:
1. @cellige: Это не прояснило. Приведите конкретный пример с кодом того, что вы хотите сделать и как это должно работать. Как будет выглядеть и работать ваш API?
2. Пример находится на вершине, сэр!