Slice w Golang: append, make, len a cap i błąd współdzielenia

Slice w jednym przykładzie

Slice to rosnący widok na tablicę. Tworzysz go literałem albo przez make, powiększasz przez append, a rozmiar odczytujesz przez len.

package main

import "fmt"

func main() {
	langs := []string{"Go", "Rust"}
	langs = append(langs, "Zig", "C")
	fmt.Println(langs, len(langs))

	for i, l := range langs {
		fmt.Println(i, l)
	}

	fmt.Println(langs[1:3]) // elements 1 and 2
}

[]string nie ma długości w nawiasach. Tym różni się od typu tablicy, takiego jak [4]string, którego rozmiar jest stały.

Czym jest slice

Wartość slice'a to mały nagłówek z trzema polami:

• wskaźnik na element w tablicy bazowej
• długość: ile elementów widzi slice
• pojemność: ile elementów istnieje od tego wskaźnika do końca tablicy bazowej

Kopiowanie slice'a (przypisanie, przekazanie do funkcji) kopiuje tylko ten nagłówek. Obie kopie wskazują na te same elementy. Prawie każda niespodzianka ze slice'ami wynika z zapomnienia o tym.

make: długość i pojemność

make([]T, len, cap) alokuje tablicę bazową i zwraca slice na niej. Pojemność jest opcjonalna i domyślnie równa długości.

package main

import "fmt"

func main() {
	a := make([]int, 3) // len 3, cap 3, all zeros
	fmt.Println(a, len(a), cap(a))

	b := make([]int, 0, 10) // len 0, room for 10
	fmt.Println(b, len(b), cap(b))

	for i := range 5 {
		b = append(b, i*i)
	}
	fmt.Println(b, len(b), cap(b)) // no reallocation happened
}

Częsta pomyłka: make([]int, 5), a po nim pięć wywołań append, daje dziesięć elementów, z których pierwsze pięć to zera. Użyj make([]int, 0, 5), gdy planujesz dopisywać, albo make([]int, 5), gdy planujesz przypisywać po indeksie.

Rezerwowanie pojemności, gdy znasz końcowy rozmiar, pozwala uniknąć wielokrotnego powiększania. To optymalizacja, a nie wymóg.

append i wzrost

append dodaje elementy za bieżącą długością. Jeśli pojemność wystarcza, zapisuje w miejscu. Jeśli nie, alokuje większą tablicę, kopiuje do niej stare elementy i zwraca slice wskazujący na nową tablicę.

package main

import "fmt"

func main() {
	var s []int
	prevCap := cap(s)
	for i := range 2000 {
		s = append(s, i)
		if cap(s) != prevCap {
			fmt.Printf("len %4d  cap %4d\n", len(s), cap(s))
			prevCap = cap(s)
		}
	}
}

Pojemność mniej więcej się podwaja, dopóki slice jest mały, a po przekroczeniu 256 elementów rośnie wolniej (zbliżając się do 1,25x). Dokładne liczby to szczegół runtime'u, który zmieniał się między wersjami Go, więc nigdy nie pisz kodu, który od nich zależy.

Ponieważ append może zwrócić inną tablicę, musisz użyć jego wyniku:

append(s, 4)     // compile error: append(s, 4) (value of type []int) is not used
s = append(s, 4) // correct

Dopisanie całego slice'a używa składni rozwinięcia: s = append(s, other...).

Wycinanie współdzieli tablicę bazową

s[low:high] tworzy nowy nagłówek slice'a na tej samej tablicy, obejmujący indeksy od low do high, bez high. Każdą z granic można pominąć. Żadne elementy nie są kopiowane.

package main

import "fmt"

func main() {
	nums := []int{10, 20, 30, 40, 50}
	mid := nums[1:4] // 20 30 40
	mid[0] = 99
	fmt.Println(nums) // the write shows up in nums

	fmt.Println(len(mid), cap(mid)) // cap runs to the end of nums
}

Wynik:

[10 99 30 40 50]
3 4

To współdzielenie sprawia, że wycinanie jest tanie. Jest też źródłem najsłynniejszego błędu ze slice'ami.

Błąd aliasingu przy append

Gdy podslice ma wolną pojemność, dopisywanie do niego zapisuje w tablicy rodzica, nadpisując elementy, których rodzic nadal używa.

package main

import "fmt"

func main() {
	base := []int{1, 2, 3, 4, 5}
	first := base[:2] // [1 2], cap 5

	first = append(first, 100) // fits in capacity: overwrites base[2]
	fmt.Println(base)
	fmt.Println(first)

	// Two slices built from the same prefix clobber each other.
	prefix := make([]string, 0, 4)
	prefix = append(prefix, "cmd")
	a := append(prefix, "build")
	b := append(prefix, "test")
	fmt.Println(a, b) // both print test
}

Wynik:

[1 2 100 4 5]
[1 2 100]
[cmd test] [cmd test]

a i b współdzielą miejsce w tablicy za "cmd", więc drugie dopisanie nadpisało pierwsze. Kod wygląda dobrze i działa za każdym razem, gdy pojemność akurat jest pełna, dlatego ten błąd pojawia się tylko czasami.

Dwa sposoby naprawy:

1. Pełne wyrażenie wycinania s[low:high:max] ogranicza pojemność do max-low. Bez wolnej pojemności następny append musi alokować. first := base[:2:2] sprawia, że pierwszy przykład jest bezpieczny.
2. Jawne kopiowanie, gdy slice przeżyje wywołanie albo będzie niezależnie rozszerzany: slices.Clone(prefix) lub append([]string(nil), prefix...).

Pokrewna pułapka: mały slice ogromnej tablicy utrzymuje dla garbage collectora całą tablicę przy życiu. Jeśli wczytasz plik 100 MB i zachowasz data[:10], całe 100 MB zostaje w pamięci. Sklonuj fragment, który zachowujesz.

copy

Wbudowana funkcja copy(dst, src) kopiuje min(len(dst), len(src)) elementów i zwraca ich liczbę. Nigdy nie powiększa dst.

package main

import (
	"fmt"
	"slices"
)

func main() {
	src := []int{1, 2, 3}

	dst := make([]int, len(src))
	n := copy(dst, src)
	dst[0] = 100
	fmt.Println(n, src, dst) // independent

	var empty []int
	fmt.Println(copy(empty, src)) // 0: dst has no length

	c := slices.Clone(src) // the one-line version (Go 1.21)
	fmt.Println(c)
}

copy poprawnie obsługuje nakładające się źródło i cel, więc copy(s[1:], s) przesuwa elementy w prawo bez uszkodzenia danych.

Pakiet slices

Od Go 1.21 standardowy pakiet slices ma generyczne funkcje pomocnicze do operacji, które kiedyś pisało się ręcznie.

package main

import (
	"fmt"
	"slices"
)

func main() {
	s := []int{5, 2, 8, 2, 9}

	fmt.Println(slices.Contains(s, 8)) // true
	fmt.Println(slices.Index(s, 2))    // 1
	fmt.Println(slices.Max(s), slices.Min(s))

	slices.Sort(s)
	fmt.Println(s)
	i, found := slices.BinarySearch(s, 8)
	fmt.Println(i, found)

	s = slices.Compact(s) // drop adjacent duplicates
	fmt.Println(s)

	s = slices.Delete(s, 1, 2) // remove index 1
	fmt.Println(s)

	s = slices.Insert(s, 1, 3, 4)
	fmt.Println(s)

	slices.Reverse(s)
	fmt.Println(s, slices.Equal(s, []int{9, 8, 4, 3, 2}))
}

Delete i Insert zwracają slice, który musisz przypisać, tak jak append. Sortowanie ma własną stronę: sortowanie.

Usuwanie elementów podczas pętli po indeksach pomija elementy. Użyj zamiast tego slices.DeleteFunc:

s = slices.DeleteFunc(s, func(n int) bool { return n%2 == 0 }) // drop evens

Slice'y 2D

Slice slice'ów daje siatkę, w której wiersze mogą mieć różną długość. Każdy wiersz trzeba zaalokować osobno.

package main

import "fmt"

func main() {
	rows, cols := 3, 4
	grid := make([][]int, rows)
	for r := range grid {
		grid[r] = make([]int, cols)
	}
	grid[1][2] = 7

	for _, row := range grid {
		fmt.Println(row)
	}

	// Rows of different lengths are fine.
	triangle := [][]int{{1}, {1, 1}, {1, 2, 1}}
	fmt.Println(triangle)
}

Pominięcie wewnętrznego make zostawia każdy wiersz jako nil, a grid[1][2] = 7 wywołuje panic z komunikatem index out of range [2] with length 0.

Slice'y nil i puste slice'y

package main

import (
	"encoding/json"
	"fmt"
)

func main() {
	var a []int  // nil
	b := []int{} // empty, not nil

	fmt.Println(len(a), len(b), a == nil, b == nil)

	a = append(a, 1) // append works on nil
	fmt.Println(a)

	ja, _ := json.Marshal(struct{ Items []int }{})
	jb, _ := json.Marshal(struct{ Items []int }{Items: []int{}})
	fmt.Println(string(ja), string(jb))
}

Slice nil zachowuje się jak pusty przy len, cap, range i append, więc jako stan zerowy wybieraj var s []T. Inicjalizuj do []T{} tylko wtedy, gdy różnica ma znaczenie, czyli głównie przy wyjściu JSON (null a []). Pustość sprawdzaj przez len(s) == 0, a nie s == nil.

Slice'y i funkcje

Funkcja, która dostaje slice, może zmieniać jego elementy, a wywołujący widzi te zmiany. Nie może zmienić długości slice'a wywołującego, bo dostała kopię nagłówka. Funkcja, która dopisuje elementy, musi zwrócić nowy slice:

func addAll(s []int, vals ...int) []int {
	return append(s, vals...)
}

Dlatego append, slices.Delete i slices.Insert zwracają slice.

Typowe błędy

• Ignorowanie wyniku append. Całkowite odrzucenie wyniku się nie kompiluje, ale przypisanie append(s, x) do innej zmiennej niż ta, której dalej używasz, to błąd logiczny.
• Dwa dopisania do jednej bazy. Mogą współdzielić pamięć. Sklonuj bazę albo użyj pełnego wyrażenia wycinania.
• make([]T, n), a potem append. Zostawia n zer na początku.
• Indeks poza zakresem. s[len(s)] wywołuje panic. Ostatni element to s[len(s)-1].
• Porównywanie slice'ów przez ==. Kompiluje się tylko s == nil. Użyj slices.Equal.