Golang Slice-Datenstrukturen

Einführung

Im vorangegangenen Abschnitt haben wir uns mit Arrays in Go beschäftigt. Arrays haben jedoch eine entscheidende Einschränkung: Einmal deklariert und initialisiert, kann ihre Länge nicht mehr geändert werden. Daher finden Arrays in der täglichen Programmierung eher selten Anwendung. Im Gegensatz dazu sind Slices (Ausschnitte) wesentlich gebräuchlicher, da sie eine deutlich flexiblere Datenstruktur bieten.

Lernziele:

• Definition eines Slices
• Initialisierung eines Slices
• Operationen auf Slices: Hinzufügen, Löschen, Ändern und Suchen
• Erweitern eines Slices
• Slice-Trunkierung (Teilstücke bilden)
• Mehrdimensionale Slices

Was ist ein Slice

Slices ähneln Arrays; sie sind Container, die Elemente desselben Datentyps aufnehmen. Arrays sind jedoch starr: Nach der Deklaration und Initialisierung bleibt ihre Länge fix. Obwohl Arrays ihre Daseinsberechtigung haben, fehlt ihnen die nötige Flexibilität für viele Szenarien. Daher sind Slices das Standardwerkzeug in der täglichen Go-Programmierung.

In Go werden Slices auf Basis von Arrays implementiert. Ein Slice ist im Grunde ein dynamisches Array, dessen Länge variieren kann. Wir können Operationen wie das Hinzufügen, Löschen, Ändern und Suchen von Elementen durchführen – Möglichkeiten, die ein reines Array nicht bietet.

Definition eines Slices

Die Syntax zur Initialisierung eines Slices ähnelt stark der eines Arrays. Der Hauptunterschied besteht darin, dass die Anzahl der Elemente nicht angegeben werden muss. Betrachten wir den folgenden Code:

// Deklaration eines Arrays mit der Länge 5
var a1 [5]byte
// Deklaration eines Slices
var s1 []byte

Ein Slice ist eine Referenz auf ein Array

Wenn wir ein Array vom Typ int deklarieren, ist der Standardwert (Zero Value) für jedes Element 0.

Deklarieren wir hingegen ein Slice, ist dessen Standardwert nil. Erstellen wir eine Datei namens slice.go, um dies zu überprüfen:

touch ~/project/slice.go

Geben Sie den folgenden Code ein:

package main

import "fmt"

func main() {
    var a [3]int
    var s []int

    fmt.Println(a[0] == 0) // true
    fmt.Println(s == nil)  // true
}

go run slice.go

Nach der Ausführung des Codes wird folgende Ausgabe angezeigt:

true
true

Wir haben ein Array a und ein Slice s erstellt. Wir vergleichen das erste Element des Arrays a mit Null und prüfen, ob das Slice s den Wert nil hat.

Wie wir sehen, ist der Standardwert eines deklarierten Slices nil. Das liegt daran, dass Slices selbst keine Daten speichern, sondern lediglich auf Arrays verweisen. Das Slice zeigt auf eine zugrunde liegende Array-Struktur.

Datenstruktur eines Slices

Ein Slice ist ein zusammengesetzter Datentyp, auch bekannt als Struktur (struct). Es handelt sich um einen Typ, der aus Feldern verschiedener Typen besteht. Die interne Struktur eines Slices setzt sich aus drei Elementen zusammen: einem Zeiger (Pointer), einer Länge (Length) und einer Kapazität (Capacity).

type slice struct {
    elem *type
    len  int
    cap  int
}

Wie bereits erwähnt, referenziert die Struktur das zugrunde liegende Array. Der elem-Zeiger zeigt auf das erste Element des Arrays, und type entspricht dem Typ der referenzierten Array-Elemente.

len und cap stehen für die Länge bzw. die Kapazität des Slices. Mit den Funktionen len() und cap() lassen sich diese Werte abrufen.

Die folgende Abbildung zeigt ein Slice, das auf ein zugrunde liegendes Array vom Typ int verweist, mit einer Länge von 5 und einer Kapazität von 5:

Wenn Sie ein neues Slice definieren, wird der elem-Zeiger mit dem Nullwert (also nil) initialisiert. Das Konzept der Zeiger wird in späteren Labs vertieft. Merken Sie sich vorerst, dass ein Zeiger auf die Speicheradresse eines Wertes verweist. In der obigen Abbildung zeigt der elem-Zeiger auf die Adresse des ersten Elements im zugrunde liegenden Array.

Operationen auf Slices: Hinzufügen, Löschen, Ändern und Suchen

Trunkieren von Arrays oder Slices

Da die zugrunde liegende Struktur eines Slices ein Array ist, können wir einen Teilbereich eines Arrays extrahieren, der dann als Referenz für das Slice dient. Das folgende Codebeispiel verdeutlicht dies:

package main

import "fmt"

func main() {
    // Definition eines Integer-Arrays der Länge 10
    a := [10]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

    // Deklaration eines leeren Slices
    var s1 []int

    fmt.Println("Slice s1 ist leer:", s1 == nil)

    // Array-Trunkierung verwenden, um das Slice zu füllen
    s1 = a[1:5]
    s2 := a[2:5]
    s3 := a[:]

    fmt.Println("Sind die Slices s1, s2 und s3 leer:", s1 == nil, s2 == nil, s3 == nil)
    fmt.Println("Elemente im Array a:", a)
    fmt.Println("Elemente im Slice s1:", s1)
    fmt.Println("Elemente im Slice s2:", s2)
    fmt.Println("Elemente im Slice s3:", s3)
}

Die Ausgabe lautet:

Slice s1 ist leer: true
Sind die Slices s1, s2 und s3 leer: false false false
Elemente im Array a: [0 1 2 3 4 5 6 7 8 9]
Elemente im Slice s1: [1 2 3 4]
Elemente im Slice s2: [2 3 4]
Elemente im Slice s3: [0 1 2 3 4 5 6 7 8 9]

In diesem Programm initialisieren wir zuerst das Array a und weisen dann dem leeren Slice s1 über eine Trunkierung einen Teil des Arrays zu. Dadurch entsteht ein neues Slice.

s1[1:5] erstellt einen Ausschnitt des Arrays. Der Bereich reicht von Index 1 des Arrays a bis Index 5, wobei das fünfte Element exklusive ist (also bis Index 4).

Hinweis: In der Programmierung ist das erste Element der Index 0, nicht 1. Entsprechend hat das zweite Element im Array den Index 1.

Wir nutzen den := Operator, um das trunkierte Array direkt dem Slice s2 zuzuweisen. Das Gleiche gilt für s3, wobei hier kein Bereich angegeben ist, sodass alle Elemente des Arrays übernommen werden.

Die folgende Grafik visualisiert die Trunkierung. Beachten Sie, dass der grüne Teil des Slices eine Referenz auf das blaue Array darstellt. Beide teilen sich dasselbe zugrunde liegende Array a.

Die Syntax für die Slice-Trunkierung lautet:

[start:end]

Sowohl start als auch end sind optional. Um alle Elemente zu erhalten, können beide weggelassen werden, wie bei s3 := a[:].

Um alle Elemente ab einem bestimmten Index zu erhalten, lassen wir end weg. Beispiel: a1[3:] liefert alle Elemente ab Index 3 bis zum Ende.

Um alle Elemente vor einem bestimmten Index zu erhalten, lassen wir start weg. Beispiel: a1[:4] extrahiert alle Elemente von Index 0 bis Index 4 (exklusive Index 4).

Zusätzlich zum Extrahieren aus einem Array können wir auch ein neues Slice aus einem bestehenden Slice erzeugen. Die Vorgehensweise ist identisch. Hier ein einfaches Beispiel:

package main

import "fmt"

func main() {
    // Definition eines Integer-Arrays der Länge 10
    a := [10]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

    // Initiales Slice s1 erstellen
    var s1 []int
    s1 = a[1:7]
    fmt.Printf("Slice s1: %d\tLänge: %d\tKapazität: %d\n", s1, len(s1), cap(s1))

    // Neues Slice s2 aus s1 extrahieren
    s2 := s1[2:4]
    fmt.Printf("Slice s2: %d\tLänge: %d\tKapazität: %d\n", s2, len(s2), cap(s2))
}

Die Ausgabe lautet:

Slice s1: [1 2 3 4 5 6] Länge: 6 Kapazität: 9
Slice s2: [3 4] Länge: 2 Kapazität: 7

In diesem Programm haben wir s1 durch Trunkierung von Array a erhalten (Index 1 bis 7). Danach haben wir s2 aus s1 extrahiert. Da die Trunkierung von s1 zusammenhängend ist, ist auch das neue Slice s2 zusammenhängend.

Man sieht, dass sich die Kapazität eines Slices bei der Trunkierung ändert. Es gelten folgende Regeln:

Wenn wir ein Slice mit der Kapazität c trunkieren, beträgt die Länge von s[i:j] genau j-i und die Kapazität c-i.

Für s1 ist das zugrunde liegende Array a. Die Kapazität von a[1:7] ist 9 (also 10-1).

Für s2 ist das zugrunde liegende Array dasselbe wie bei s1. Da der Ausgangspunkt für s2 bei Index 2 von s1 liegt (was Index 3 von a entspricht), verringert sich die Kapazität von 9 auf 7 (9-2).

Änderungen an Slice-Werten beeinflussen gleichzeitig das zugrunde liegende Array

Da ein Slice keine eigenen Daten speichert, sondern nur auf ein Array verweist, ändert das Modifizieren eines Slice-Werts auch den Wert im zugrunde liegenden Array. Demonstrieren wir dies:

package main

import "fmt"

func main() {
    // Definition eines Integer-Arrays der Länge 10
    a := [10]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

    s1 := a[2:5]
    s2 := a[:]

    fmt.Println("Vor der Änderung: ")
    fmt.Println("Elemente im Array a: ", a)
    fmt.Println("Elemente im Slice s1: ", s1)
    fmt.Println("Elemente im Slice s2: ", s2)

    // Wert an Index 2 von Slice s1 auf 23 ändern
    s1[2] = 23

    fmt.Println("Nach der Änderung: ")
    fmt.Println("Elemente im Array a: ", a)
    fmt.Println("Elemente im Slice s1: ", s1)
    fmt.Println("Elemente im Slice s2: ", s2)
}

Die Ausgabe lautet:

Vor der Änderung:
Elemente im Array a:  [0 1 2 3 4 5 6 7 8 9]
Elemente im Slice s1:  [2 3 4]
Elemente im Slice s2:  [0 1 2 3 4 5 6 7 8 9]
Nach der Änderung:
Elemente im Array a:  [0 1 2 3 23 5 6 7 8 9]
Elemente im Slice s1:  [2 3 23]
Elemente im Slice s2:  [0 1 2 3 23 5 6 7 8 9]

In diesem Programm referenzieren sowohl s1 als auch s2 das Array a. Wenn s1 den Wert an seinem Index 2 auf 23 ändert, werden auch das Array a und das Slice s2 aktualisiert.

Wir sehen, dass der Wert an Index 4 des Arrays auf 23 geändert wurde (da s1 := a[2:5] bedeutet: s1[0] ist a[2], s1[1] ist a[3] und s1[2] ist a[4]). Dies führt zur Änderung an Index 4 sowohl im Array a als auch im Slice s2.

Dies kann zu schwer auffindbaren Fehlern führen. Daher sollte man in der Praxis vermeiden, dass mehrere Slices unkontrolliert auf dasselbe zugrunde liegende Array verweisen.

Elemente an ein Slice anhängen

In diesem Abschnitt führen wir die Funktion append ein, mit der Elemente zu einem Slice hinzugefügt werden. Die Syntax lautet:

func append(slice []Type, elems ...Type) []Type

Das erste Argument ist das Ziel-Slice, die weiteren Argumente sind die anzuhängenden Elemente. Der Rückgabetyp []Type gibt an, dass append ein neues Slice desselben Typs zurückgibt.

Das ... bei elems bedeutet, dass es sich um einen variadischen Parameter handelt, man also ein oder mehrere Elemente übergeben kann.

Hier ein Beispiel für die Verwendung von append:

package main

import "fmt"

func main() {
    // Definition eines Integer-Arrays der Länge 10
    a := [10]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

    s1 := a[1:7]
    fmt.Printf("Initialer Wert s1: %d\tLänge: %d\tKapazität: %d\n", s1, len(s1), cap(s1))

    s1 = append(s1, 12)
    fmt.Printf("Modifizierter Wert s1: %d\tLänge: %d\tKapazität: %d\n", s1, len(s1), cap(s1))

    s1 = append(s1, 14, 14)
    fmt.Printf("Modifizierter Wert s1: %d\tLänge: %d\tKapazität: %d\n", s1, len(s1), cap(s1))
}

Die Ausgabe lautet:

Initialer Wert s1: [1 2 3 4 5 6] Länge: 6 Kapazität: 9
Modifizierter Wert s1: [1 2 3 4 5 6 12] Länge: 7 Kapazität: 9
Modifizierter Wert s1: [1 2 3 4 5 6 12 14 14] Länge: 9 Kapazität: 9

In diesem Programm erstellen wir s1 durch Trunkierung von a. Wir weisen den Rückgabewert von append wieder s1 zu. Wenn die Anzahl der Elemente die Kapazität übersteigt, wird die Kapazität des Slices automatisch angepasst.

Die Regeln für die Erweiterung sind:

• Wenn das zugrunde liegende Array genug Platz bietet, ändert sich die Kapazität nicht.
• Wenn der Platz nicht ausreicht, erstellt Go ein neues, größeres Array, kopiert die vorhandenen Werte und fügt das neue Element hinzu.

Hinweis: Die Kapazität wird nicht immer einfach verdoppelt; dies hängt von der Elementgröße, der Anzahl der Elemente und der Hardware ab.

Elemente aus einem Slice löschen

Go bietet keine direkten Schlüsselwörter zum Löschen von Elementen, aber wir können die Trunkierung nutzen, um diesen Effekt zu erzielen.

Der folgende Code löscht das Element an Index 5 im Slice s und weist das Ergebnis einem neuen Slice s1 zu:

package main

import "fmt"

func main() {
    s := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
    // Slice s vor dem Löschen ausgeben
    fmt.Println(s)

    s1 := append(s[:5], s[6:]...)
    // Slices s und s1 nach dem Löschen von Index 5 ausgeben
    fmt.Printf("%d\n%d\n", s, s1)
}

Die Ausgabe lautet:

[0 1 2 3 4 5 6 7 8 9]
[0 1 2 3 4 6 7 8 9 9]
[0 1 2 3 4 6 7 8 9]

Der Trick liegt in der append-Anweisung. Sie hängt die Elemente ab Index 6 an die Elemente vor Index 5 an.

Diese Operation entspricht einem Vorwärts-Überschreiben. Element 5 wird mit Element 6 überschrieben, Element 6 mit 7 usw. Das zugrunde liegende Array sieht danach so aus: [0 1 2 3 4 6 7 8 9 9].

Prüfen wir Länge und Kapazität von s1, sehen wir eine Länge von 9, aber eine Kapazität von 10, da s1 immer noch auf das ursprüngliche Array von s verweist.

package main

import "fmt"

func main() {
    s := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
    fmt.Println(s)

    s1 := append(s[:5], s[6:]...)
    // Länge und Kapazität von s1 prüfen
    fmt.Println(len(s1), cap(s1))
    fmt.Printf("\n%d\n%d\n\n", s, s1)

    // Slice s modifizieren
    s[3] = 22
    fmt.Printf("%d\n%d\n", s, s1)
}

Die Ausgabe lautet:

[0 1 2 3 4 5 6 7 8 9]
9 10

[0 1 2 3 4 6 7 8 9 9]
[0 1 2 3 4 6 7 8 9]

[0 1 2 22 4 6 7 8 9 9]
[0 1 2 22 4 6 7 8 9]

Übung

Neben dem Löschen einzelner Positionen können wir auch ganze Bereiche entfernen. Die Logik bleibt dieselbe.

Erstellen Sie eine Datei slice1.go. Definieren Sie ein Slice a und initialisieren Sie es wie folgt. Nutzen Sie dann Trunkierung, um ein neues Slice s zu erstellen, das keine Elemente enthält, die größer als 3 oder kleiner als 7 sind (bezogen auf die Werte im Beispiel-Array). Geben Sie das neue Slice aus.

a := []int{9, 8, 7, 6, 5, 4, 3, 2, 1, 0}

Erwartete Ausgabe:

[9 8 7 3 2 1 0]

• Hinweis: Achten Sie auf die Indizes (beginnend bei 0).
• Anforderung: Die Datei slice1.go muss im Verzeichnis ~/project liegen.

Erweitern von Slices

Ein Slice hat zwei Attribute: len (Länge) und cap (Kapazität). len gibt an, wie viele Elemente aktuell enthalten sind, cap gibt an, wie viele Elemente das Slice maximal aufnehmen kann, ohne das zugrunde liegende Array neu zu erstellen.

Was passiert, wenn wir die Kapazität überschreiten? Finden wir es heraus:

package main

import "fmt"

func main() {
    s1 := make([]int, 3)
    s2 := make([]int, 3, 5)
    fmt.Println("Vor Append in s1:", s1, "Länge:", len(s1), "Kapazität:", cap(s1))
    fmt.Println("Vor Append in s2:", s2, "Länge:", len(s2), "Kapazität:", cap(s2))

    s1 = append(s1, 12)
    s2 = append(s2, 22)
    fmt.Println("Nach Append in s1:", s1, "Länge:", len(s1), "Kapazität:", cap(s1))
    fmt.Println("Nach Append in s2:", s2, "Länge:", len(s2), "Kapazität:", cap(s2))
}

Führen Sie das Programm aus:

go run slice.go

Die Ausgabe lautet:

Vor Append in s1: [0 0 0] Länge: 3 Kapazität: 3
Vor Append in s2: [0 0 0] Länge: 3 Kapazität: 5
Nach Append in s1: [0 0 0 12] Länge: 4 Kapazität: 6
Nach Append in s2: [0 0 0 22] Länge: 4 Kapazität: 5

Wie man sieht, wird die Kapazität von s1 automatisch erhöht, da sie vorher erschöpft war. Bei s2 war noch Platz im zugrunde liegenden Array (Kapazität 5), daher blieb die Kapazität gleich.

Regeln für die Erweiterung:

• Reicht das Array aus, bleibt die Kapazität gleich.
• Reicht es nicht aus, wird ein neues, größeres Array alloziert, die Daten umgezogen und das neue Element angehängt.

Kopieren von Slices

Mit der Funktion copy können wir den Inhalt eines Slices in ein anderes übertragen. Die Syntax lautet:

func copy(dst, src []Type) int

dst ist das Ziel-Slice, src die Quelle. Der Rückgabewert int gibt die Anzahl der kopierten Elemente an (das Minimum von len(dst) und len(src)).

Hinweis: copy fügt keine neuen Plätze hinzu; das Ziel-Slice muss bereits groß genug sein.

Beispiel:

package main

import "fmt"

func main() {
    s1 := []int{0, 1, 2, 3}
    s2 := []int{8, 9}

    s3 := []int{0, 1, 2, 3}
    s4 := []int{8, 9}

    // Kopiere s1 nach s2
    n1 := copy(s2, s1)
    // Kopiere s4 nach s3
    n2 := copy(s3, s4)

    fmt.Println(n1, s1, s2)
    fmt.Println(n2, s3, s4)
}

Ausführung:

go run slice.go

Ausgabe:

2 [0 1 2 3] [0 1]
2 [8 9 2 3] [8 9]

Im ersten Fall werden nur 2 Elemente kopiert, da s2 nur Platz für 2 Elemente hat. Im zweiten Fall werden ebenfalls 2 Elemente kopiert, die die ersten beiden Stellen von s3 überschreiben.

Iterieren über Slices

Das Durchlaufen eines Slices funktioniert genau wie bei einem Array. Alle bekannten Methoden können angewendet werden.

Übung

In dieser Übung festigen wir das Wissen über das Iterieren.

Erstellen Sie eine Datei slice2.go. Deklarieren Sie ein Array a1 und ein Slice s1 mit den folgenden Werten. Iterieren Sie über beide und geben Sie jeweils Index und Wert aus.

a1 := [5]int{1, 2, 3, 9, 7}
s1 := []int{1, 8, 12, 1, 3}

Erwartete Ausgabe:

Element a1 at index 0 is 1
Element a1 at index 1 is 2
Element a1 at index 2 is 3
Element a1 at index 3 is 9
Element a1 at index 4 is 7
Element s1 at index 0 is 1
Element s1 at index 1 is 8
Element s1 at index 2 is 12
Element s1 at index 3 is 1
Element s1 at index 4 is 3

• Anforderung: Die Datei slice2.go muss im Verzeichnis ~/project liegen.
• Hinweis: Nutzen Sie die range-Schleife für eine elegante Lösung.

Zusammenfassung

In diesem Abschnitt haben wir Slices und ihre Anwendung kennengelernt. Im Vergleich zu Arrays sind Slices wesentlich flexibler und vielseitiger einsetzbar. Beim Arbeiten mit mehreren Slices, die auf dasselbe Array verweisen, ist jedoch Vorsicht geboten, um unerwünschte Seiteneffekte zu vermeiden.