Памятка по слайсам в Go #

Эта памятка в основном показывает использование пакета “slices”. Версия без пакета “slices” показана, если она выглядит просто.

• пакет “slices” добавлен в Go 1.21 и содержит generic-функции для обработки слайсов
• generic-функции появились в Go 1.18, но пакета “slices” тогда ещё не было
• в более ранних версиях Go приходилось обрабатывать слайсы с помощью цикла for

Другие источники #

• наглядная шпаргалка Go Slice Tricks Cheat Sheet
  • в ней не показаны возможности пакета slices
• документация пакета slices
• внутренняя структура слайсов Go Slices: usage and internals

Что такое слайс #

Слайс указывает на массив и по сути хранит в себе три поля:

1. ptr — указатель на массив
2. len — размер слайса
3. cap — ёмкость слайса (размер низлежащего массива)

В сумме это 16 байт на 64-битных платформах.

Допустим, мы объявили массив и слайс так:

// Массив из 6 элементов.
a := [6]int{1, 2, 3, 4, 5, 6}

// Слайс указывает на срез длиной 2, начиная со 2 элемента.
s := a[2:4]

Так будут выглядеть слайс и массив в памяти:

package slices

import (
	"testing"

	"github.com/stretchr/testify/require"
)

func TestSlices(t *testing.T) {
	// Массив из 6 элементов.
	a := [6]int{1, 2, 3, 4, 5, 6}

	// Слайс указывает на срез длиной 2, начиная со 2 элемента.
	s := a[2:4]

	// Длина слайса 2, а ёмкость - 4 (остаток массива).
	require.Equal(t, 2, len(s))
	require.Equal(t, 4, cap(s))
	require.Equal(t, s, []int{3, 4})

	// Добавляя в слайс, мы перезаписываем массив - ёмкость не кончилась.
	s = append(s, 10)
	require.Equal(t, 3, len(s))
	require.Equal(t, 4, cap(s))
	require.Equal(t, s, []int{3, 4, 10})
	require.Equal(t, a, [6]int{1, 2, 3, 4, 10, 6})

	// Мы снова перезаписываем массив - ёмкость не кончилась.
	s = append(s, 11)
	require.Equal(t, 4, len(s))
	require.Equal(t, 4, cap(s))
	require.Equal(t, s, []int{3, 4, 10, 11})
	require.Equal(t, a, [6]int{1, 2, 3, 4, 10, 11})

	// Для 5-го элемента слайса в хвосте массива места не было.
	// Теперь слайс указывает на новый массив с удвоенным capacity,
	//  но и старый массив сохранился, потому что есть ссылка на него.
	s = append(s, 12)
	require.Equal(t, 5, len(s))
	require.Equal(t, 8, cap(s))
	require.Equal(t, s, []int{3, 4, 10, 11, 12})
	require.Equal(t, a, [6]int{1, 2, 3, 4, 10, 11})
}

Встроенные функции #

Получение подслайса #

Общий синтаксис: slice[start:end], где

• start — индекс первого элемента нового слайса (включается в результат)
• end — индекс первого элемента после нового слайса (не включается в результат)

Конкретные примеры:

// новый слайс содержит элементы от i-го до конца слайса
tail := values[i:]

// новый слайс содержит элементы от 0-го до i-го (не включая i-й)
head := values[:i]

// не слайс, а i-й элемент слайса
value := values[i]

Изменение слайса #

Добавление в конец слайса #

Добавить элемент можно функцией append:

// Добавление элемента в конец слайса
values = append(values, v)

// Добавление элементов слайса other в конец слайса
values = append(values, other...)

Функция append имеет известные особенности:

• старая ссылка на слайс инвалидируется — согласно семантике языка, пользоваться ей нельзя
• на практике старая ссылка инвалидируется именно тогда, когда для добавления элемента ёмкость слайса пришлось повысить до следующей степени двойки

Вставка в начало или середину слайса #

Добавить элементы в заданной позиции со сдвигом элементов правее них можно функцией slices.Insert:

func TestInsert(t *testing.T) {
	nums := []int{10, 20, 50}
	// Вставляет значения 30 и 40
	nums = slices.Insert(nums, 2, 30, 40)
	require.Equal(t, []int{10, 20, 30, 40, 50}, nums)
}

Удаление элемента слайса #

Можно использовать функцию slices.Delete:

func TestDelete(t *testing.T) {
	nums := []int{10, 20, 30, 40, 50, 60, 70}
	// Удаляет значения 30 и 40 (индексы со 2 по 3-й, не включая 4-й)
	nums = slices.Delete(nums, 2, 4)
	require.Equal(t, []int{10, 20, 50, 60, 70}, nums)
}

Удалить элемент слайса со сдвигом элементов правее него влево можно либо путём получения подслайса:

// удаление последнего элемента слайса
values = values[:len(values)-1]

// удаление i-го элемента слайса
values = append(values[:i], values[i+1:]...)

// удаление элементов слайса с i-го по j-й, не включая j-й
values = append(values[:i], values[j:]...)

Если сохранение порядка не важно, то можно удалить элемент без сдвига, поменяв местами с последним элементом:

values[i] = values[len(values)-1]
values = values[:len(values)-1]

Сортировка и бинарный поиск #

Сортировка слайса #

Сортировать одномерный слайс можно функцией slices.Sort. Эта функция принимает встроенные типы, у которых есть оператор “<”:

func TestSortStrings(t *testing.T) {
	results := []string{"Mike", "Alice", "Bob", "Antony"}

    // Сортировка за счёт сравнения строк оператором "<".
	slices.Sort(results)

	require.Equal(t, results, []string{"Alice", "Antony", "Bob", "Mike"})
}

В других случаях можно использовать slices.SortFunc. Например, так можно отсортировать строки двумерной матрицы чисел:

func TestSortIntMatrix(t *testing.T) {
	matrix := [][]int{
		{3, 1, 2},
		{1, 2, 3},
		{2, 1, 3},
	}

    // Сортировка за счёт сравнения строк матрицы функцией `slices.Compare`,
    //  которая выполняет лексикографическое сравнение строк матрицы (слайсов []int).
	slices.SortFunc(matrix, slices.Compare)

	require.Equal(t, [][]int{
		{1, 2, 3},
		{2, 1, 3},
		{3, 1, 2},
	}, matrix)
}

Бинарный поиск #

Бинарный поиск в сортированном массиве имеет вычислительную сложность O(log(N)).

Функция slices.BinarySearch находит элемент либо позицию для его вставки:

func TestBinarySearch(t *testing.T) {
	nums := []int{10, 20, 30}

	// Число 20 находится по индексу 1.
	n, found := slices.BinarySearch(nums, 20)
	require.Equal(t, 1, n)
	require.True(t, found)

	// Числа 12 нет, но его можно вставить по индексу 1.
	n, found = slices.BinarySearch(nums, 12)
	require.Equal(t, 1, n)
	require.False(t, found)
}