Вступление
Одна из самых общих возможностей процедурных языков программирования, это концепция массива. Массивы могут показаться чем-то простым, но с другой стороны, перед их добавлением в язык требуется решить несколько вопросов, таких как:
- Фиксированный или переменный размер?
- Размер это часть типа?
- Что из себя будут представлеть многомерные массивы?
- Что из себя представляем понятие пустого массива?
Ответы на эти вопросы определят массивы как простую возможность языка, или как основную часть его дизайна.
Во времена ранней разработки Go, поиск ответов на эти вопросы потребовал годы обсуждений, прежде чем их концепция стала выглядеть так, как мы посчитали нужным. Ключевым шагом стало создание концепции срезов (slices), которые основаны на массивах фиксированного размера, дабы создать гибкую и расширяемую структуру данных. Однако, многие новички в Go спотыкаются о принципы работы срезов, возможно это происходит из-за того, что их опыт работы с другими языками оставил свой след.
В этой публикации мы постараемся развеять все эти недоразумения. Добьемся мы этого по кусочкам объясняя как работает функция append, и почему она работает именно так и никак иначе.
Массивы
Массивы это важный кусочек языка Go, но, как и фундамент здания, он спрятан под более видимыми частями. Мы должны ввести вас в курс дела, прежде чем перейти к более интересным, мощным и заметным особенностям срезов.
Массивы не часто встретишь в программах на Go, потому что в тип массива входит его размер, что ограничивает возможности использование.
Например объявление:
var buffer [256]byte
создает переменную buffer, которая содержит 256 байт. Тип переменной buffer включает в себя размер и выглядит так: [256]byte. Массив из 512 байт будет иметь тип [512]byte.
Данные связанные с массивом это просто массив элементов. Схематически, наш буфер в памяти будет иметь примерно следующий вид:
buffer: byte byte byte ... 256 times ... byte byte byte
То есть, переменная содержит 256 байт данных и ничего более. Мы можем получить доступ к элементам с помощью привычного синтаксиса индексации buffer[0], buffer[1], и так до buffer[255] (индекс от 0 до 255 охватывает 256 элементов). Попытка выйти за пределы этого диапазона приведет к аварийной остановке программы.
Существует встроенная функция len, которая возвращает количество элементов массива, среза и некоторых других типов. Очевидно, что именно вернет len для массива. В нашем случае len(buffer) вернет значение 256.
Для массивов можно найти свое место применения. Например они хороши, для преобразования матриц, но наиболее частое их применение в Go это хранение срезов.
Срезы: Заголовок среза
Срезы там, где происходит что-то интересное, но перед тем как приступить к их использованию, потребуется понять их надобность и то, что-же они делают.
Срез это структура данных описывающая множественное разделение массива и хранящееся отдельно от переменной. Срез это не массив. Срез описывает часть массива.
Если мы возьмем массив buffer из предыдущего раздела, то мы можем создать срез, который будет описывать элементы от 100 до 150 (если быть точным, то от 100 до 149 включительно) путем нарезания массива:
var slice []byte = buffer[100:150]
В этом куске кода, чтобы быть точными, мы использовали полное объявление переменной. Переменная slice имеет тип []byte, читается как «срез байтов» (slice of bytes) и создана из массива buffer, путем нарезания начиная с элемента 100 (включительно) до 150 (исключительно). В более «идиоматическом» (от пер. читай «намекающем», «сокращенном») синтаксисе, то мы бы опустили тип, который будет определен в процессе инициализации:
var slice = buffer[100:150]
А внутри функции мы бы использовали короткую форму объявления:
slice := buffer[100:150]
Что же из себя представляет срез? Это не полное описание, но с этого момента думайте о срезе как о небольшой структуре, состоящей из двух элементов: длинны и указателя на элемент массива. Считайте что «за кулисами» это выглядит примерно так:
type sliceHeader struct {
Length int
ZerothElement *byte
}
slice := sliceHeader{
Length: 50,
ZerothElement: &buffer[100],
}
Конечно, это лишь иллюстрация. Несмотря на это, из этого примера можно понять то, что структура sliceHeader недоступна программисту, а тип указателя зависит от типа элементов, однако он дает возможность понять основную идею механики работы срезов.
До сих пор мы использовали операцию нарезания массива, однако мы можем нарезать и срез:
slice2 := slice[5:10]
Точно так-же как и прежде, эта операция создает новый срез, но в этом случае из элементов с 5 до 9 (включительно) относительно оригинального среза, что означает элементы с 105 по 109 оригинального массива. Базовая структура sliceHeader для переменной slice2 будет выглядеть так:
slice2 := sliceHeader{
Length: 5,
ZerothElement: &buffer[105],
}
Обратите внимание, что заголовок до сих пор указывает на базовый массив, находящийся в переменной buffer.
Мы так-же можем перенарезать, что означает нарезать срез и сохранить результат в структуре нарезаемого среза. Т.е. после:
slice = slice[5:10]
структура sliceHeader для переменной slice будет выглядеть так-же как и для переменной slice2. Вы будете часто видеть перенарезку, например для сокращения среза. В этом примере будет опущен первый и последний элемент нашего среза:
slice = slice[1:len(slice)-1]
Вы можете часто слышать от опытных Go программистов о «заголовке среза», т.к. это и есть то, что хранится в переменной среза. Например, когда вы вызываете функцию которая берет срез как аргумент, такая как bytes.IndexRune, то в функцию будет передана заголовок. В этом примере:
slashPos := bytes.IndexRune(slice, '/')
аргумент slice будет передан в функцию IndexRune и, по факту, это лишь «заголовок среза».
Есть еще один элемент данных в «заголовке среза» о котором мы поговорим ниже, но сначала давайте взглянем на то, что значит «заголовок среза», когда вы пишете программу использующую срезы.
Передача срезов в функции
Очень важно понять то, что даже если срез содержит указатель, сам по себе он является значением. Под капотом, это структура содержащая указатель и длину. Это не указатель на структуру.
Это важно.
Когда мы вызываем IndexRune в предыдущем примере, она принимает копию «верхушки заголовка». Такое поведение имеет важное последствие.
Рассмотрим простую функцию:
func AddOneToEachElement(slice []byte) {
for i := range slice {
slice[i]++
}
}
Она делает именно то, что написано в названии, т.е. обходит все элементы среза (используя цикл for range), увеличивая его элементы.
Попробуйте:
func main() {
slice := buffer[10:20]
for i := 0; i < len(slice); i++ {
slice[i] = byte(i)
}
fmt.Println("before", slice)
AddOneToEachElement(slice)
fmt.Println("after", slice)
}
Несмотря на то что «заголовок среза» передается в функцию, она включает указатель на элементы массива, поэтому оригинальная заголовок среза и его копия описывают один и тот-же массив. Как следствие, когда функция завершается, измененные элементы можно увидеть через исходный срез.
Аргумент функции на самом деле копия, и данный пример это показывает:
func SubtractOneFromLength(slice []byte) []byte {
slice = slice[0 : len(slice)-1]
return slice
}
func main() {
fmt.Println("Before: len(slice) =", len(slice))
newSlice := SubtractOneFromLength(slice)
fmt.Println("After: len(slice) =", len(slice))
fmt.Println("After: len(newSlice) =", len(newSlice))
}
Здесь мы видим что содержимое аргумента может быть изменено через функцию, но не его заголовок. Длинна сохранена в переменной slice и не изменяется в результате вызова функции, т. к. в функцию передается копия заголовка среза, а не исходный. Таким образом, если мы хотим написать функцию которая изменяет заголовок, мы должны вернуть его, как мы это сделали в примере. Переменная slice не изменяется, но возвращаемое значение имеет новую длину, которая сохранена в newSlice.
Указатели на срезы: Методы получения
Существует и другой путь написания функции которая изменяет заголовок среза, и это передача в функцию указатель на срез. Вот вариация нашего примера, для демонстрации данной возможности:
func PtrSubtractOneFromLength(slicePtr *[]byte) {
slice := *slicePtr
*slicePtr = slice[0 : len(slice)-1]
}
func main() {
fmt.Println("Before: len(slice) =", len(slice))
PtrSubtractOneFromLength(&slice)
fmt.Println("After: len(slice) =", len(slice))
}
Пример может показаться немного неуклюжим, учитывая дополнительный уровень абстракции (временная переменная), но есть один случай, где вы будете применять указатели на срезы. Принято использование указателя в качестве приемника при написании метода, который изменяет срез.
Скажем, мы захотели метод который ликвидирует последний слэш. Мы можем написать его примерно так:
type path []byte
func (p *path) TruncateAtFinalSlash() {
i := bytes.LastIndex(*p, []byte("/"))
if i >= 0 {
*p = (*p)[0:i]
}
}
func main() {
pathName := path("/usr/bin/tso") // Преобразование из строки в path
pathName.TruncateAtFinalSlash()
fmt.Printf("%sn", pathName)
}
Если вы запустите пример, то вы увидите, что произойдет то, что требовалось, т. е. метод изменит срез.
С другой стороны, если мы захотим написать метод для path, который устанавливает верхний регистр ASCII символов (с не Английские буквами поведение не определено), то метод может оперировать значением, а не указателем, потому что значение приемника все еще указывает на нужный нам массив.
type path []byte
func (p path) ToUpper() {
for i, b := range p {
if 'a' <= b && b <= 'z' {
p[i] = b + 'A' - 'a'
}
}
}
func main() {
pathName := path("/usr/bin/tso")
pathName.ToUpper()
fmt.Printf("%sn", pathName)
}
Здесь метод ToUpper использует две переменных в for range для того, чтобы использовать индекс элемента и, непосредственно, сам элемент среза. Это позволит избежать повторной записи в p[i].
Мощность
Рассмотрим следующую функцию, которая увеличивает срез ints на один элемент:
func Extend(slice []int, element int) []int {
n := len(slice)
slice = slice[0 : n+1]
slice[n] = element
return slice
}
Теперь запустим:
func main() {
var iBuffer [10]int
slice := iBuffer[0:0]
for i := 0; i < 20; i++ {
slice = Extend(slice, i)
fmt.Println(slice)
}
}
Посмотрим как срез растет до тех пор пока… он не растет.
Пришло время поговорить о третьем компоненте заголовка среза: его мощности. Помимо указателя на массив и его длинны, заголовок срез содержит его мощность:
type sliceHeader struct {
Length int
Capacity int
ZerothElement *byte
}
Поле Capacity содержит запись о том, сколько места занимает массив на самом деле – это максимальное значение, которое может достигнуть Length. Попытка увеличения среза выше его мощности приведет к выходу за пределы массива и вызовет экстренное завершение программы.
В этом примере создается срез
slice := iBuffer[0:0]
и его заголовок выглядит как:
slice := sliceHeader{
Length: 0,
Capacity: 10,
ZerothElement: &iBuffer[0],
}
Поле Capacity эквивалентно длине оригинального массива минус индекс элемента массива, который является первым элементом среза (в данном случае ноль). Если вы хотите узнать мощность среза, то используйте функцию cap:
if cap(slice) == len(slice) {
fmt.Println("slice is full!")
}
Make
Что если мы захотим увеличить срез больше чем его мощность? Мы не можем! По определению мощность это предел роста. Но вы можете получить тот-же результат путем создания нового массива, копирования данных и изменения среза описывающего новый массив.
Давайте начнем с выделения. Мы можем использовать функцию new для выделения большего массива и в результате большего среза, но будет проще использовать функцию make. Она выделяет новый массив и создает заголовок среза. Функция make имеет три аргумента: тип среза, начальная длинна и его мощность, где длина массива это то, что make выделяет для данных среза. В результате этот вызов функции создает срез длинной 10 и возможностью расширения на 5 (15-10), что вы можете увидеть запустив это:
slice := make([]int, 10, 15)
fmt.Printf("len: %d, cap: %dn", len(slice), cap(slice))
Этот фрагмент удваивает мощность нашего int среза, но оставляет такую-же длину:
slice := make([]int, 10, 15)
fmt.Printf("len: %d, cap: %dn", len(slice), cap(slice))
newSlice := make([]int, len(slice), 2*cap(slice))
for i := range slice {
newSlice[i] = slice[i]
}
slice = newSlice
fmt.Printf("len: %d, cap: %dn", len(slice), cap(slice))
После этого срез имеет гораздо больше места для роста перед тем, как ему потребуется еще одно перераспределение.
При создании срезов часто бывает что длинна и мощность это одно и тоже. Функция make имеет сокращенный вариант. Длинна по умолчанию становится мощностью, поэтому вы можете указать их в одном значении. После
gophers := make([]Gopher, 10)
у среза gophers длинна и мощность будет равна 10.
Копирование
После того как мы удвоили мощность нашего среза в предыдущем разделе, мы переписали цикл для копирования старых данных в новый срез. В Go есть встроенная функция copy, которая упрощает эту задачу. Её аргументы это два среза и она копирует данные из правого в левый срез. Вот наш пример переписанный на использование copy:
newSlice := make([]int, len(slice), 2*cap(slice))
copy(newSlice, slice)
Функция copy умная. Она копирует только то, что может, обращая внимание на длину обоих аргументов. Другими словами, количество элементов, которые будут скопированы, равно минимальной из длин обоих срезов. Это может сэкономить немного «бюрократии». Кроме того, copy возвращает целочисленное значение – количество элементов, которые были скопированы, хотя это не всегда стоит проверки.
Функция copy так-же учитывает случаи, когда источник и приемник пересекаются (прим. пер. это как memmove() в C), это означает что функция может быть использована для перемещения элементов внутри одного среза. Ниже пример того, как с помощью функции copy вставить значение в середину среза.
// Вставляет вставляемое значение в срез по указанному индексу,
// который должен быть из определенного диапазона.
// Срез должен иметь свободное место для нового элемента.
func Insert(slice []int, index, value int) []int {
// Увеличиваем срез на один элемент
slice = slice[0 : len(slice)+1]
// Используем copy для перемещения верхней части среза наружу и создания пустого места
copy(slice[index+1:], slice[index:])
// Записываем новое значение.
slice[index] = value
// Возвращаем результат.
return slice
}
Есть несколько моментов, которые вы можете заметить в этой функции. Во первых, что очевидно, она должна вернуть срез, потому что его длинна изменилась. Во вторых, используется удобное сокращение. Выражение
slice[i:]
означает тоже самое, что и
slice[i:len(slice)]
Кроме того, мы не использовали еще один трюк, мы так-же можем оставить первый элемент выражения пустым; по умолчанию это будет ноль. Таким образом
slice[:]
Означает просто срез самого себя, что полезно при нарезании массива. Это выражение самый короткий пусть сказать: «срез, описывающий все элементы массива»:
array[:]
Но это было между делом, давайте испытаем нашу функцию Insert.
slice := make([]int, 10, 20) // Заметим, что capacity > length: есть место для вставки элемента.
for i := range slice {
slice[i] = i
}
fmt.Println(slice)
slice = Insert(slice, 5, 99)
fmt.Println(slice)
Вставка: Пример
Несколько разделов назад, мы написали функцию Extend, которая расширяла срез на один элемент. Она была неправильной, хотя бы по той причине, что в случае, когда мощность среза была слишком маленькой, функция могла завершиться с ошибкой (в нашем примере функция Insert подвержена такой-же проблеме). Теперь мы знаем как это исправить, поэтому давайте напишем надежную реализацию функции Extend для целочисленных срезов.
func Extend(slice []int, element int) []int {
n := len(slice)
if n == cap(slice) {
// срез полон; должны расти.
// Мы удвоили его размер и добавили 1, поэтому если размер равен нулю, мы по прежнему можем вырасти
newSlice := make([]int, len(slice), 2*len(slice)+1)
copy(newSlice, slice)
slice = newSlice
}
slice = slice[0 : n+1]
slice[n] = element
return slice
}
В данном случае особенно важно вернуть срез, т. к. когда мы перераспределили его, срез который у нас получился описывает совершенно другой массив. Вот небольшой кусочек для демонстрации что произойдет, если срез заполнится:
slice := make([]int, 0, 5)
for i := 0; i < 10; i++ {
slice = Extend(slice, i)
fmt.Printf("len=%d cap=%d slice=%vn", len(slice), cap(slice), slice)
fmt.Println("address of 0th element:", &slice[0])
}
Обратите внимание на перераспределение, когда первоначальный массив размера 5 заполняется. Мощность и адрес нулевого элемента изменяются, когда выделяется новый массив.
Используя надежную функцию Extend в качестве основы, мы можем написать еще более лучшую функцию, которая позволит нам расширить срез несколькими элементами. Для этого воспользуемся возможностью Go по обращению списка аргументов в массив. То есть, мы используем возможность Go использовать переменное количество аргументов функции.
Давайте назовем функцию Append. Для первой версии, мы можем просто вызывать Extend до тех пор, пока не закончатся аргументы функции. Прототип функции Append выглядит так:
func Append(slice []int, items ...int) []int
Это говорит нам о том, что Append берет один аргумент – срез, а за ним следует от нуля до бесконечности аргументов типа int. Эти элементы будущие кусочки срез, как вы можете увидеть:
// Append добавляет элементы в срез.
// Первая версия: просто циклически вызываем Extend.
func Append(slice []int, items ...int) []int {
for _, item := range items {
slice = Extend(slice, item)
}
return slice
}
Заметьте что цикл for range выполняется для каждого элемента аргумента items, который имеет тип []int. Так-же заметьте использование пустого идентификатора _, который отбрасывает индекс, т. к. в цикле он нам не нужен.
Попробуйте это:
slice := []int{0, 1, 2, 3, 4}
fmt.Println(slice)
slice = Append(slice, 5, 6, 7, 8)
fmt.Println(slice)
Другой новый прием в этом примере это то, что инициализация срез производится составным литералом, который состоит из типа и элементов среза, заключенных в фигурные скобки:
slice := []int{0, 1, 2, 3, 4}
Функция Append так-же интересна по другой причине. Мы можем не просто добавлять элементы, мы можем передавить в качестве аргументов функции целые срезы используя …:
slice1 := []int{0, 1, 2, 3, 4}
slice2 := []int{55, 66, 77}
fmt.Println(slice1)
slice1 = Append(slice1, slice2...) // '...' обязательно!
fmt.Println(slice1)
Конечно, мы можем сделать Append более эффективной, путем единичного выделения, опираясь на Extend:
// Append добавляет элементы в срез.
// Эффективная версия.
func Append(slice []int, elements ...int) []int {
n := len(slice)
total := len(slice) + len(elements)
if total > cap(slice) {
// Перераспределение. Увеличим размер в 1.5 раза, что позволит нам расти дальше.
newSize := total*3/2 + 1
newSlice := make([]int, total, newSize)
copy(newSlice, slice)
slice = newSlice
}
slice = slice[:total]
copy(slice[n:], elements)
return slice
}
Обратите внимание, что здесь мы дважды используем copy, чтобы переместить срез данных в новый участок памяти и затем скопировать добавленные элементы в конец старых данных.
Попробуйте, поведение такое-же, как и прежде:
slice1 := []int{0, 1, 2, 3, 4}
slice2 := []int{55, 66, 77}
fmt.Println(slice1)
slice1 = Append(slice1, slice2...) // '...' обязательно!
fmt.Println(slice1)
Append: Встроенная функция
Итак, мы пришли к выводу, что в Go нужно добавить встроенную функцию append. Она делает то-же самое, что и наша функция Append из примера, с одинаковой эффективностью, но работает для любого типа срезов.
Слабость Go заключается в том, что любая операция определенная на «общем-типе» должна быть предоставлена во время выполнения. Когда-нибудь это может измениться, но сейчас, дабы упростить работу со срезами, Go предоставляет встроенную общую функцию append. Она работает так-же как и наша целочисленная версия, но для любого типа среза.
Помните что поскольку заголовок среза обновляется каждый раз при вызове append, вам необходимо сохранить полученный срез после вызова. На самом деле, компилятор не позволит вам вызвать append без сохранения результата.
Вот некоторые однострочечники с выводом. Попробуйте их, изменяйте и исследуйте:
// Создаем пару начальных срезов.
slice := []int{1, 2, 3}
slice2 := []int{55, 66, 77}
fmt.Println("Start slice: ", slice)
fmt.Println("Start slice2:", slice2)
// Добавляем элемент в срез.
slice = append(slice, 4)
fmt.Println("Add one item:", slice)
// Добавляем один срез в другой.
slice = append(slice, slice2...)
fmt.Println("Add one slice:", slice)
// Делаем копию среза (int).
slice3 := append([]int(nil), slice...)
fmt.Println("Copy a slice:", slice3)
// Копируем срез в конец самого себя.
fmt.Println("Before append to self:", slice)
slice = append(slice, slice...)
fmt.Println("After append to self:", slice)
Стоит остановится и подумать о последних строчках примера и понять как дизайн срезов позволяет делать такие простые вызовы правильными.
Существует множество примеров в вики (созданной сообществом) "Slice Tricks", использующих append, copy и других путей использования срезов.
Nil
Кроме того, используя новоприобретенные знания мы можем понять что из себя представляет «нулевой» (nil) срез. Естественно, это нулевое значение заголовок среза:
sliceHeader{
Length: 0,
Capacity: 0,
ZerothElement: nil,
}
или просто
sliceHeader{}
Ключевым является то, что указатель тоже равен nil. Данный срез
array[0:0]
имеет нулевую длину (и может даже нулевую мощность), но его указатель не nil, поэтому это все еще не нулевой срез.
Очевидно, что пустой срез может расти (предполагая что он не нулевой мощности), но «нулевой» (nil) срез не содержит массива, куда можно положить значения и не может вырасти, даже для того, чтобы содержать хоть один элемент.
Стоит отметить, что «нулевой» (nil) срез, по сути дела, эквивалентен срезу нулевой длины, даже если он ни на что не указывает. Он имеет нулевую длину и в него можно что-нибудь добавить с выделением. В качестве примера, посмотрите на несколько строчек выше, где копируется срез, добавляя «нулевой» (nil) срез.
Строки
Теперь кратко о строках в Go в контексте срезов.
На самом деле, строки очень просты: это срезы байт только для чтения, с небольшой дополнительной синтаксической поддержкой со стороны языка.
Так как они только для чтения, у них нет мощности (вы не можете увеличить их), однако в большинстве случаев вы можете обращаться с ними как срезами байт.
Для начала, мы можем использовать индексацию, для доступа к отдельным байтам:
slash := "/usr/ken"[0] // записывает байт '/'
Мы можем нарезать строку для создания подстроки:
usr := "/usr/ken"[0:4] // записывает строку "/usr"
Должно быть очевидным то, что происходит за занавесом, когда мы нарезаем строку.
Так-же мы можем взять обычный срез байт и создать из него строку, путем простого преобразования:
str := string(slice)
а так-же из строки сделать срез байт:
slice := []byte(usr)
Массив лежащий в основе строк скрыт от глаз, нет никакого способа получить к нему доступ, кроме как через строку. Это значит, что когда мы делаем эти преобразования должна быть создана копия массива. Go берет на себя эту работу, так-что не волнуйтесь об этом. После любого подобного преобразования, изменение массива лежащего в основе среза байт не влияет на соответствующую строку.
Важным следствием похожего поведения строк как срезов заключается в том, что создание подстроки происходит очень эффективно. Все что требуется, это создание двух верхушек строк. Так как строка только для чтения, то исходная строка и строка полученная в результате нарезки могут безопасно разделять один и тот-же массив.
Историческая справка: Ранние реализации строк всегда отдельно выделялись, но с тех пор в языке появились срезы, которые предоставили возможность создания более эффективной работы со строками. Некоторые бенчмарки стали показывать огромный прирост скорости.
Конечно, есть много еще того что стоит рассказать о строках, но эта тема для другой публикации.
Заключение
Понимание принципов работы срезов, помогает понять как они сделаны. Есть небольшая структура данных, заголовок среза, связанная с переменной типа срез и эта заголовок описывает часть отдельно выделенного массива. Когда мы создаем срез, то заголовок копируется, но массив всегда разделяется.
После того, как вы оцените их работу, срезы станут не только простыми в использовании, но мощными и выразительными, особенно с помощью встроенных функций copy и append.
Оригинальная публикация — blog.golang.org/slices
Автор: BratSinot
