Strutture dati in C/C++

L'array dinamico e std::vector in C e C++

In questa lezione implementerai in C un array dinamico che cresce da solo quando aggiungi elementi e lo confronterai con std::vector del C++.

Introduzione

Un array dinamico (dynamic array) è un array che può crescere quando serve. Distingue due concetti: il numero di elementi contenuti (size) e lo spazio allocato (capacity). Quando l'array è pieno, il programma alloca un'area più grande, di solito il doppio, e vi sposta i dati.

Punti importanti

Definisci le condizioni che devono essere sempre vere (invarianti) prima di scrivere le operazioni.
Gestisci i casi di struttura vuota, piena e di allocazione di memoria fallita.
Valuta insieme la complessità e la gestione della memoria di ogni operazione.

Guarda come funziona

Premi push_back più volte. Quando l'array è pieno, alloca un blocco grande il doppio e ci copia tutto.

Esempi di codice C e C++

Esegui →

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);
}

Risultato dell'esecuzione

size=5 capacity=8 last=25

C++

Esegui →

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';
}

Risultato dell'esecuzione

size=5 last=25

Confronto tra C e C++

Nella versione in C, quando size raggiunge capacity, il programma raddoppia capacity e chiama realloc per ampliare la memoria. Il risultato di realloc viene assegnato a un puntatore temporaneo, grown, così che la vecchia memoria si possa ancora liberare se l'allocazione fallisce. std::vector del C++ incapsula proprio questa strategia di crescita e in più libera da solo la memoria, supporta gli iteratori ed è sicuro in caso di eccezioni.

I dati (struct) e le operazioni sono separati, e la memoria viene allocata e liberata a mano.

C++

Classi e contenitori proteggono la coerenza dei dati e gestiscono da soli le proprie risorse.

Esercizi di approfondimento

Esegui entrambe le versioni e poi modifica il codice per osservare la differenza di sicurezza che offre ciascun linguaggio.

Aggiungi test per la struttura vuota e per quando raggiunge la capacità massima.
Scrivi la liberazione della memoria e controlla che non ci siano perdite.
Confronta la complessità con il contenitore equivalente della libreria standard.

Esercitati con una sfida

Usa ciò che questa lezione spiega per risolvere un problema reale. Ogni sfida gira nel browser, con test immediati e una revisione dell'IA.

Tutte le sfide