Salta al contenuto
Note per Studenti Esercizio - Array stile C, vector e la classe MyArray (terzo appello 2022-23, teoria)

Esercizio - Array stile C, vector e la classe MyArray (terzo appello 2022-23, teoria)

Esame
In questa pagina 3

Domanda aperta 1 del terzo appello 2022-23 del corso di Laboratorio di Programmazione, Ing. Informatica UniPD. Teoria: C++ - puntatori, array e castun puntatore è una variabile che contiene un indirizzo di memoria e sa il tipo dell'oggetto puntato (T*); si ottiene l'indirizzo con & e si accede al dato con * (dereference, un lvalue), nullptr indica nessun oggetto e due puntatori a tipi diversi sono tipi diversi; void* è un puntatore a memoria grezza (accetta qualsiasi puntatore ma non si dereferenzia) e i cast (static_cast, reinterpret_cast, const_cast) servono per interfacciarsi con hardware e codice non modificabile; il puntatore, a differenza della reference, si può spostare, può essere nullptr e va dereferenziato, e assegnarlo copia l'indirizzo (shallow copy) mentre assegnare una reference copia l'oggetto; un array C è una sequenza contigua di elementi dello stesso tipo, con dimensione costante, senza controllo dei limiti, che passato a una funzione decade in un puntatore al primo elemento; l'aritmetica dei puntatori somma o sottrae interi spostando di n elementi (non di n byte) e la differenza fra puntatori è in elementi; gli errori classici sono nullptr, puntatori non inizializzati, accessi fuori dai limiti e puntatori a oggetti usciti dallo scope.C++ - puntatori, array e cast →, C++ - allocazione dinamica della memoria con new e deletela memoria dinamica si prende dal free store (heap) con new, che restituisce un puntatore all'oggetto o al primo elemento dell'array (new T, new T[n], con inizializzatori {}), e si restituisce con delete (per new) e delete[] (per new[]); il puntatore non sa quanti elementi ci sono, la memoria non ha nome e non ha controllo dei limiti; in C++ non c'è garbage collector (scelta per efficienza e controllo), quindi un'area che perde ogni riferimento diventa garbage e produce un memory leak, e gli errori tipici sono la doppia cancellazione e il dangling pointer (si mette il puntatore a nullptr dopo delete); il distruttore ~T() è chiamato dal compilatore quando l'oggetto esce dallo scope o con delete e libera le risorse, per cui una classe come vector acquisisce la memoria nel costruttore e la rilascia nel distruttore; new alloca e chiama il costruttore, delete chiama il distruttore e libera; operator[] con due versioni (T& e const) dà accesso in lettura e scrittura al buffer; si alloca dinamicamente solo se serve davvero (memoria grande, dimensione nota a run-time, durata controllata).C++ - allocazione dinamica della memoria con new e delete →, STL - sequenze, iteratori e container (vector, list, string)La STL (Standard Template Library) fornisce contenitori (vector, list, map, ...) e algoritmi generici (sort, find, accumulate, ...) tenuti insieme da una interfaccia unificata: la sequenza, un intervallo [begin, end) di elementi gestito tramite iteratori (oggetti che identificano un elemento: * dereferenzia, ++ avanza, == e != confrontano; end è il primo elemento dopo l'ultimo, quindi una sequenza vuota ha begin == end). Gli algoritmi conoscono solo gli iteratori e i contenitori espongono solo iteratori, così i due mondi sono disaccoppiati e cambiare contenitore non cambia l'algoritmo. Un iteratore di lista è una classe annidata con un puntatore al nodo; auto deduce il tipo dell'iteratore. vector (contiguo, [] e at(), insert/erase costosi e che invalidano gli iteratori), string (un vector di char con + e +=), list (nodi concatenati, insert/erase senza spostare gli altri elementi, niente []) e char[] (array C: dimensione fissa, niente iteratori, == confronta i puntatori) a confronto.STL - sequenze, iteratori e container (vector, list, string) →. La versione completa è Esercizio - MyVector 2.0 con buffer ridimensionabile (laboratorio 4).

Testo. Si descriva la differenza tra un array stile C e uno std::vector. In particolare: a) Quali sono le differenze nell'organizzazione e salvataggio in memoria dei dati? b) Quali sono le differenze nei metadati? Implementare una classe MyArray che mima il comportamento di std::vector fornendo solo le seguenti funzionalità: c) push_back(); d) pop_back().

a) Organizzazione dei dati in memoria

array stile C std::vector
elementi contigui, stesso tipo contigui, stesso tipo
dove stanno dove è dichiarato: globale (data/BSS), locale (stack), o heap se allocato con new[] gli elementi stanno sempre in un buffer sull'heap (free store), gestito dal vector
dimensione fissa, costante nota a tempo di compilazione (per gli array automatici); non si può cambiare dinamica: cresce con push_back; il buffer è più grande del numero di elementi (capacity maggiore di size)
l'oggetto è il blocco di elementi stesso un oggetto piccolo (tipicamente tre puntatori o puntatore + due interi) sullo stack o dove è dichiarato, che punta al buffer sull'heap
gestione della memoria a carico del programmatore se allocato con new[] (delete[]); automatica se locale automatica (RAII): il distruttore libera il buffer
copia x = y tra array non si può fare (il nome è un puntatore costante); per copiare serve un ciclo o std::copy copia e assegnamento profondi: copia gli elementi
passaggio a funzione decade a puntatore al primo elemento per valore (copia), per & o const&

b) Metadati

I metadati sono i dati sulla collezione, oltre agli elementi.

metadato array C std::vector
numero di elementi non lo conosce (passato a funzione si perde: sizeof dà la dimensione del puntatore) size()
capacità del buffer non esiste capacity(), reserve()
inizio e fine a mano (a, a + n) begin(), end() (iteratori)
controllo dei limiti nessuno at(i) con eccezione out_of_range ([] no)
elementi aggiungibili o rimovibili no push_back, pop_back, insert, erase
confronto == confronta i puntatori == confronta gli elementi

Un array C è soltanto memoria; un vector è un oggetto che ne gestisce una, con sz (elementi), capacity e puntatore. Per questo un vector può conoscere la propria dimensione e crescere; l'array no.

c) e d) La classe MyArray

Rappresentazione come in un vector: un buffer sull'heap più due numeri, size_ (elementi in uso) e capacity_ (posti allocati). Invarianti: 0≤0 \le size_ ≤\le capacity_; data_ ha capacity_ posti (o è nullptr se zero).

  • push_back(value): se size_ == capacity_ il buffer è pieno: si rialloca raddoppiando la capacità (da 0 a 2, poi 2, 4, 8, ...), cioè: alloca il nuovo buffer, copia i size_ elementi, libera il vecchio, aggiorna puntatore e capacità. Poi scrive in data_[size_] e incrementa size_. Il raddoppio dà un costo ammortizzato costante per inserimento (Esercizio - MyVector 2.0 con buffer ridimensionabile (laboratorio 4)).
  • pop_back(): decrementa size_; la capacità non cambia. Su un array vuoto lancia out_of_range (con std::vector sarebbe comportamento indefinito).
  • Distruttore: delete[] data_;, indispensabile.
  • Copia: vietata con = delete (la copia di default copierebbe il puntatore: doppia delete[]); la richiesta è solo di push_back e pop_back, ma una classe con un puntatore che possiede memoria non può lasciare la copia di default.
  • size(), capacity() e operator[] sono aggiunti solo per provarla.
myarray.cppcpp
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <stdexcept>
using namespace std;

// Una versione ridotta di std::vector<int>: solo push_back() e pop_back() (piu' gli accessori per provarla).
// Invarianti: 0 <= size_ <= capacity_; data_ ha capacity_ posti allocati (nullptr se capacity_ == 0).
class MyArray {
public:
    MyArray() : size_{0}, capacity_{0}, data_{nullptr} {}
    ~MyArray() { delete[] data_; }
    MyArray(const MyArray&) = delete;               // niente copia: la copia di default farebbe due delete[]
    MyArray& operator=(const MyArray&) = delete;    // (copia e spostamento veri: laboratorio 4)

    // c) push_back: se il buffer e' pieno si rialloca raddoppiando la capacita'
    void push_back(int value)
    {
        if (size_ == capacity_) {
            size_t nuova = capacity_ == 0 ? 2 : 2 * capacity_;
            int* nuovo = new int[nuova];                         // 1. nuovo buffer piu' grande
            copy(data_, data_ + size_, nuovo);                   // 2. copia degli elementi in uso
            delete[] data_;                                      // 3. libera il vecchio
            data_ = nuovo;                                       // 4. cambia i membri
            capacity_ = nuova;
        }
        data_[size_] = value;
        ++size_;
    }

    // d) pop_back: toglie l'ultimo elemento (la capacita' non cambia)
    void pop_back()
    {
        if (size_ == 0) throw out_of_range("pop_back su MyArray vuoto");
        --size_;
    }

    size_t size() const { return size_; }
    size_t capacity() const { return capacity_; }
    int& operator[](size_t i) { return data_[i]; }
    int operator[](size_t i) const { return data_[i]; }

private:
    size_t size_;
    size_t capacity_;
    int* data_;
};

int main()
{
    MyArray a;
    for (int i = 1; i <= 5; ++i) {
        a.push_back(i * i);
        cout << "push_back(" << i * i << "): size " << a.size() << ", capacity " << a.capacity() << '\n';
    }
    a.pop_back();
    a.pop_back();
    cout << "dopo due pop_back: size " << a.size() << ", capacity " << a.capacity() << ", elementi:";
    for (size_t i = 0; i < a.size(); ++i) cout << ' ' << a[i];
    cout << '\n';
    return 0;
}
push_back(1): size 1, capacity 2
push_back(4): size 2, capacity 2
push_back(9): size 3, capacity 4
push_back(16): size 4, capacity 4
push_back(25): size 5, capacity 8
dopo due pop_back: size 3, capacity 8, elementi: 1 4 9

Lettura: i primi due push_back portano la capacità a 2 (da 0), il terzo la raddoppia a 4, il quinto a 8; due pop_back riducono size a 3 ma non la capacità; gli elementi restano 1,4,91, 4, 9.

Versione ripasso

  • a) Memoria: array C = elementi contigui dove è dichiarato (data/BSS, stack, o heap con new[]), dimensione fissa costante, nessuna copia con x = y, passato a funzione decade a puntatore; vector = oggetto piccolo (puntatore, size, capacity) con elementi contigui sull'heap, dimensione dinamica, memoria automatica (RAII), copia profonda.
  • b) Metadati:
array C vector
numero di elementi non lo conosce size()
capacità no capacity(), reserve()
inizio/fine a mano begin(), end()
limiti nessun controllo at() (eccezione)
== confronta i puntatori confronta gli elementi
  • c, d) MyArray: buffer data_ + size_ + capacity_ (0≤0 \le size_ ≤\le capacity_); copia vietata; distruttore delete[] data_.
cpp
void push_back(int value)
{ if (size_ == capacity_) {                            // pieno: rialloca raddoppiando
      size_t nuova = capacity_ == 0 ? 2 : 2 * capacity_;
      int* nuovo = new int[nuova];
      copy(data_, data_ + size_, nuovo);  delete[] data_;
      data_ = nuovo;  capacity_ = nuova; }
  data_[size_++] = value; }
void pop_back() { if (size_ == 0) throw out_of_range("..."); --size_; }   // la capacita' non cambia
  • Prova: capacità 2, 2, 4, 4, 8 con 5 push_back (1, 4, 9, 16, 25); due pop_back →\to size 3, capacity 8, elementi 1 4 9.
  • Errori tipici: dire che il vector sta nello stack; credere che sizeof di un parametro array dia la lunghezza; liberare il vecchio buffer prima di copiare; capacità che cresce di 1; dimenticare il distruttore.
  • Dichiarazione di MyArray: class MyArray { public: MyArray(); ~MyArray(); MyArray(const MyArray&) = delete; MyArray& operator=(const MyArray&) = delete; void push_back(int value); void pop_back(); size_t size() const; size_t capacity() const; int& operator[](size_t i); private: size_t size_, capacity_; int* data_; }; Capacità: 0 →\to 2 →\to 4 →\to 8: il raddoppio dà un costo ammortizzato costante per push_back.

Esercizi su questo argomento

Teoria collegata