Datenstrukturen in C/C++

Dynamisches Array und std::vector in C und C++

In dieser Lektion implementierst du in C ein dynamisches Array, das beim Hinzufügen von Elementen selbst wächst, und vergleichst es mit std::vector in C++.

Einführung

Ein dynamisches Array (dynamic array) ist ein Array, das bei Bedarf wachsen kann. Es unterscheidet zwei Größen: die Anzahl der enthaltenen Elemente (size) und den reservierten Platz (capacity). Ist das Array voll, reserviert das Programm einen größeren Speicherbereich, meist doppelt so groß, und verschiebt die Daten dorthin.

Wichtige Punkte

Lege fest, welche Bedingungen in der Datenstruktur immer gelten müssen (Invarianten), bevor du die Operationen schreibst.
Behandle die Fälle leer, voll und fehlgeschlagene Speicherreservierung vollständig.
Bewerte bei jeder Operation Komplexität und Speicherverwaltung gemeinsam.

So funktioniert es

Klicke mehrmals auf push_back. Ist das Array voll, reserviert es einen doppelt so großen Block und kopiert alles hinüber.

Codebeispiele in C und C++

Code ausführen →

main.c

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    size_t size = 0, capacity = 2;
    int *values = malloc(capacity * sizeof *values);
    if (!values) return 1;
    for (int value = 1; value <= 5; ++value) {
        if (size == capacity) {
            capacity *= 2;
            int *grown = realloc(values, capacity * sizeof *values);
            if (!grown) {
                free(values);
                return 1;
            }
            values = grown;
        }
        values[size++] = value * value;
    }
    printf("size=%zu capacity=%zu last=%d\n",
           size, capacity, values[size - 1]);
    free(values);
}

Ergebnis der Ausführung

size=5 capacity=8 last=25

C++

Code ausführen →

main.cpp

#include <iostream>
#include <vector>

int main() {
    std::vector<int> values;
    for (int value = 1; value <= 5; ++value) {
        values.push_back(value * value);
    }
    std::cout << "size=" << values.size()
              << " last=" << values.back() << '\n';
}

Ergebnis der Ausführung

size=5 last=25

C und C++ im Vergleich

In der C-Version verdoppelt das Programm capacity, sobald size gleich capacity ist, und ruft realloc auf, um den Speicher zu vergrößern. Das Ergebnis von realloc wird einem temporären Zeiger grown zugewiesen, damit der alte Speicher noch freigegeben werden kann, falls die Reservierung fehlschlägt. std::vector in C++ kapselt genau diese Wachstumsstrategie und gibt den Speicher zusätzlich selbst frei, unterstützt Iteratoren und ist ausnahmesicher.

Daten (struct) und Operationen sind getrennt, und Speicher wird von Hand reserviert und freigegeben.

C++

Klassen und Container schützen die Korrektheit der Daten und verwalten ihre Ressourcen selbst.

Übungen zur Vertiefung

Führe beide Versionen aus und ändere dann den Code, um zu beobachten, welche Sicherheit jede Sprache bietet.

Ergänze Tests für den leeren Zustand und für das Erreichen der Kapazitätsgrenze.
Schreibe die Speicherfreigabe und prüfe auf Speicherlecks.
Vergleiche die Komplexität mit dem entsprechenden Container der Standardbibliothek.

Mit einer Challenge üben

Nutze den Inhalt dieser Lektion, um ein echtes Problem zu lösen. Jede Challenge läuft im Browser, mit sofortigen Tests und einem KI-Review.

Alle Challenges