Esercizio - MyVector 2.0 con buffer ridimensionabile (laboratorio 4)

Quarto laboratorio del corso di Laboratorio di Programmazione, Ing. Informatica UniPD: una versione di std::vector per double con tutte le operazioni essenziali. Teoria: C++ - allocazione dinamica della memoria con new e delete, C++ - costruttori, inizializzazione, copia e spostamento; la versione generica è il Esercizio - MyVector 2.0 con template (laboratorio 5); il punto di partenza è Esercizio - MyVector con memoria dinamica (laboratorio 3).

Testo. Implementare la classe MyVector che gestisce vettori di elementi double in modo analogo a std::vector. I dati devono essere gestiti tramite allocazione dinamica. Il buffer è progettato per essere più grande dell'effettivo numero di elementi (come negli array parzialmente riempiti): MyVector tiene conto di due valori, il numero di elementi effettivamente salvati e il massimo numero di elementi gestibile col buffer corrente. Aggiungere elementi oltre lo spazio disponibile comporta la riallocazione di un buffer più grande e la copia degli elementi: le riallocazioni sono pesanti, quindi serve una buona politica di gestione della memoria. Devono essere presenti: le operazioni essenziali illustrate a lezione; l'accesso con il doppio overloading di operator[]; l'accesso con controllo dei limiti at() (con overloading per lettura/scrittura e gestione del fuori limite con un'eccezione); push_back(); pop_back(); reserve() (impone una dimensione minima del buffer; se il buffer corrente è già maggiore del valore passato, non fa nulla).

Progetto

Dati e invarianti. size_ (elementi in uso), capacity_ (elementi allocati), buffer_ (puntatore). Invarianti: $0 \le$ size_ $\le$ capacity_; il buffer ha capacity_ elementi; se capacity_ == 0 allora buffer_ == nullptr. Gli elementi validi sono buffer_[0..size_-1]; il resto è spazio non inizializzato a disposizione dei prossimi push_back.

elemento	scelta
tipo degli indici	`std::size_t` come `std::vector`: attenzione, essendo senza segno `size() - 1` su un vettore vuoto è un numero enorme
costruttori	vuoto (`MyVector()`, nessuna allocazione), `explicit MyVector(size_t n)` (n zeri), `initializer_list<double>` (`MyVector v {1.5, 2.5}`)
copia (profonda)	costruttore e assegnamento di copia; la copia ha `capacity_ = size_` (lo spazio extra non va duplicato)
spostamento	costruttore e assegnamento `noexcept`: rubano il buffer e svuotano la sorgente
`operator[]`	`double&` e `const double&`, senza controllo (veloce)
`at(i)`	idem, ma lancia `out_of_range` se $i \ge$ `size_`
`push_back`	se `size_ == capacity_` rialloca con `reserve(capacity_ == 0 ? 4 : 2 * capacity_)`
`pop_back`	decrementa `size_`; la capacità non cambia; su vettore vuoto lancia `out_of_range`
`reserve(n)`	se `n <= capacity_` non fa nulla; altrimenti alloca `n`, copia gli `size_` elementi, libera il vecchio

La politica di crescita

Ogni riallocazione copia tutti gli elementi esistenti, quindi la politica con cui cresce capacity_ decide il costo totale. Il programma seguente conta le copie fatte durante $N$ chiamate consecutive a push_back, per tre politiche (aggiungere 1 posto, aggiungere 10 posti, raddoppiare):

lab4_crescita.cppcpp

#include <iostream>
using namespace std;

// Simula N push_back e conta quanti elementi vengono copiati in totale durante le riallocazioni
long long copie(int N, int politica)           // politica: 0 = +1, 1 = +10, 2 = raddoppio
{
    long long totale = 0;
    int size = 0, capacity = 0;
    for (int i = 0; i < N; ++i) {
        if (size == capacity) {
            totale += size;               // la riallocazione copia i size elementi esistenti
            if (politica == 0) capacity += 1;
            else if (politica == 1) capacity += 10;
            else capacity = capacity == 0 ? 4 : 2 * capacity;
        }
        ++size;
    }
    return totale;
}

int main()
{
    for (int N : {100, 1000, 100000}) {
        cout << "N = " << N << ":  +1 -> " << copie(N, 0) << " copie,  +10 -> " << copie(N, 1)
             << " copie,  x2 -> " << copie(N, 2) << " copie\n";
    }
    return 0;
}

N = 100:  +1 -> 4950 copie,  +10 -> 450 copie,  x2 -> 124 copie
N = 1000:  +1 -> 499500 copie,  +10 -> 49500 copie,  x2 -> 1020 copie
N = 100000:  +1 -> 4999950000 copie,  +10 -> 499950000 copie,  x2 -> 131068 copie

politica	copie per $N$ inserimenti	ordine di grandezza
+1	$0 + 1 + \dots + (N-1) = N(N-1)/2$ (4 999 950 000 per $N = 10^5$ )	$O(N^2)$
+10	circa $N^2/20$	$O(N^2)$ (solo costante più piccola)
raddoppio	$\le 2N$ (131 068 per $N = 10^5$ )	$O(N)$ : costo ammortizzato costante per inserimento

Con il raddoppio le riallocazioni sono rare e i costi si sommano come $4 + 8 + 16 + \dots < 2N$ . Costo: fino a metà della memoria può restare inutilizzata. È la politica di std::vector. L'implementazione parte da 4 per non fare tante riallocazioni minuscole all'inizio.

Il codice

myvector.hcpp

#ifndef MYVECTOR_H
#define MYVECTOR_H

#include <cstddef>
#include <initializer_list>

// Vettore di double con buffer piu' grande del numero di elementi (come un array parzialmente riempito).
// Invarianti: 0 <= size_ <= capacity_; il buffer ha capacity_ elementi allocati; se capacity_ == 0, buffer_ == nullptr.
class MyVector {
public:
    // --- le operazioni essenziali ---
    MyVector();                                         // vettore vuoto
    explicit MyVector(std::size_t n);                   // n elementi a 0.0
    MyVector(std::initializer_list<double> lst);        // MyVector v {1.5, 2.5}
    MyVector(const MyVector& other);                    // copia profonda
    MyVector& operator=(const MyVector& other);         // assegnamento di copia
    MyVector(MyVector&& other) noexcept;                // spostamento: ruba il buffer
    MyVector& operator=(MyVector&& other) noexcept;
    ~MyVector();

    // --- accesso ---
    double& operator[](std::size_t i);                  // senza controllo
    const double& operator[](std::size_t i) const;
    double& at(std::size_t i);                          // con controllo: out_of_range
    const double& at(std::size_t i) const;

    // --- dimensione e modifica ---
    std::size_t size() const { return size_; }
    std::size_t capacity() const { return capacity_; }
    bool empty() const { return size_ == 0; }
    void push_back(double value);                       // aggiunge in fondo; rialloca se il buffer e' pieno
    void pop_back();                                    // toglie l'ultimo elemento
    void reserve(std::size_t new_capacity);             // buffer di almeno new_capacity; mai in diminuzione

private:
    std::size_t size_;
    std::size_t capacity_;
    double* buffer_;
};

#endif // MYVECTOR_H

myvector.cppcpp

#include "myvector.h"

#include <algorithm>
#include <stdexcept>
#include <utility>

MyVector::MyVector() : size_{0}, capacity_{0}, buffer_{nullptr} {}

MyVector::MyVector(std::size_t n)
    : size_{n}, capacity_{n}, buffer_{n > 0 ? new double[n] : nullptr}
{
    std::fill(buffer_, buffer_ + size_, 0.0);
}

MyVector::MyVector(std::initializer_list<double> lst)
    : size_{lst.size()}, capacity_{lst.size()}, buffer_{lst.size() > 0 ? new double[lst.size()] : nullptr}
{
    std::copy(lst.begin(), lst.end(), buffer_);
}

MyVector::MyVector(const MyVector& other)
    : size_{other.size_}, capacity_{other.size_},        // la copia non ha bisogno dello spazio extra
      buffer_{other.size_ > 0 ? new double[other.size_] : nullptr}
{
    std::copy(other.buffer_, other.buffer_ + size_, buffer_);
}

MyVector& MyVector::operator=(const MyVector& other)
{
    if (this == &other) return *this;                    // auto-assegnamento: non c'e' niente da fare
    double* nuovo = other.size_ > 0 ? new double[other.size_] : nullptr;   // 1. alloca (se fallisce, *this e' intatto)
    std::copy(other.buffer_, other.buffer_ + other.size_, nuovo);          // 2. copia
    delete[] buffer_;                                                      // 3. libera il vecchio
    buffer_ = nuovo;                                                       // 4. sostituisce
    size_ = capacity_ = other.size_;
    return *this;
}

MyVector::MyVector(MyVector&& other) noexcept
    : size_{other.size_}, capacity_{other.capacity_}, buffer_{other.buffer_}
{
    other.size_ = 0;                                     // la sorgente resta valida ma vuota
    other.capacity_ = 0;
    other.buffer_ = nullptr;
}

MyVector& MyVector::operator=(MyVector&& other) noexcept
{
    if (this != &other) {
        delete[] buffer_;
        size_ = other.size_;
        capacity_ = other.capacity_;
        buffer_ = other.buffer_;
        other.size_ = 0;
        other.capacity_ = 0;
        other.buffer_ = nullptr;
    }
    return *this;
}

MyVector::~MyVector()
{
    delete[] buffer_;                                    // delete[] su nullptr non fa nulla
}

double& MyVector::operator[](std::size_t i) { return buffer_[i]; }
const double& MyVector::operator[](std::size_t i) const { return buffer_[i]; }

double& MyVector::at(std::size_t i)
{
    if (i >= size_) throw std::out_of_range("MyVector::at: indice fuori dai limiti");
    return buffer_[i];
}

const double& MyVector::at(std::size_t i) const
{
    if (i >= size_) throw std::out_of_range("MyVector::at: indice fuori dai limiti");
    return buffer_[i];
}

void MyVector::reserve(std::size_t new_capacity)
{
    if (new_capacity <= capacity_) return;               // se il buffer e' gia' abbastanza grande non fa nulla
    double* nuovo = new double[new_capacity];
    std::copy(buffer_, buffer_ + size_, nuovo);          // copia solo gli elementi in uso
    delete[] buffer_;
    buffer_ = nuovo;
    capacity_ = new_capacity;
}

void MyVector::push_back(double value)
{
    if (size_ == capacity_)                              // buffer pieno: politica di crescita GEOMETRICA
        reserve(capacity_ == 0 ? 4 : 2 * capacity_);
    buffer_[size_] = value;
    ++size_;
}

void MyVector::pop_back()
{
    if (size_ == 0) throw std::out_of_range("MyVector::pop_back: vettore vuoto");
    --size_;                                             // la capacita' non cambia: lo spazio resta a disposizione
}

Punti da notare:

Assegnamento di copia: prima si alloca nuovo (se new fallisce, *this non è stato toccato: garanzia forte), poi si copia, solo dopo si libera il vecchio buffer e si sostituisce. Il controllo this == &other evita lavoro inutile nell'auto-assegnamento (che comunque funzionerebbe).
Copia con capacity_ = size_: la copia ha tanto spazio quanto elementi; il primo push_back rialloca. Si poteva copiare anche la capacità; è una scelta di politica.
Spostamento: la sorgente è lasciata vuota ma valida (size_ = capacity_ = 0, buffer_ = nullptr), perché sarà comunque distrutta e delete[] nullptr non fa nulla; noexcept perché la STL sposta invece di copiare solo se lo spostamento non può lanciare.
reserve copia solo size_ elementi (non capacity_): il resto del buffer è spazio libero.
Il distruttore è l'unico punto che libera il buffer; tutte le operazioni che cambiano buffer_ liberano il vecchio.

Programma di prova

main.cppcpp

#include <iostream>
#include <stdexcept>
#include <utility>
#include "myvector.h"
using namespace std;

void stampa(const char* nome, const MyVector& v)
{
    cout << nome << " [size " << v.size() << ", capacity " << v.capacity() << "]:";
    for (size_t i = 0; i < v.size(); ++i) cout << ' ' << v[i];
    cout << '\n';
}

int main()
{
    MyVector v;                                          // vuoto: nessuna allocazione
    stampa("v", v);
    for (int i = 1; i <= 9; ++i) {
        v.push_back(i * 1.5);
        cout << "dopo push_back(" << i * 1.5 << "): size " << v.size() << ", capacity " << v.capacity() << '\n';
    }
    v.pop_back();                                        // size scende, capacity resta
    stampa("dopo pop_back", v);

    v.reserve(40);                                       // richiesta piu' grande: rialloca
    stampa("dopo reserve(40)", v);
    v.reserve(10);                                       // richiesta piu' piccola: non fa nulla
    stampa("dopo reserve(10)", v);

    MyVector w {1.5, 2.5, 3.5};                          // initializer_list
    MyVector copia = w;                                  // costruttore di copia
    copia[0] = 99;                                       // non tocca w: buffer separati
    stampa("w", w);
    stampa("copia", copia);

    copia = v;                                           // assegnamento di copia
    MyVector spostato = std::move(w);                    // costruttore di spostamento
    stampa("spostato", spostato);
    stampa("w dopo lo spostamento", w);

    const MyVector& cv = spostato;
    cout << "cv[1] = " << cv[1] << ", cv.at(2) = " << cv.at(2) << '\n';

    try {
        cout << spostato.at(3) << '\n';                  // fuori dai limiti: eccezione
    }
    catch (out_of_range&) {
        cout << "at(3): indice fuori dai limiti\n";
    }
    return 0;
}

Il programma usa try/catch: in WebAssembly le eccezioni non funzionano, quindi l'uscita è ricavata a mano e confermata eseguendo una copia in cui throw stampa e termina.

v [size 0, capacity 0]:
dopo push_back(1.5): size 1, capacity 4
dopo push_back(3): size 2, capacity 4
dopo push_back(4.5): size 3, capacity 4
dopo push_back(6): size 4, capacity 4
dopo push_back(7.5): size 5, capacity 8
dopo push_back(9): size 6, capacity 8
dopo push_back(10.5): size 7, capacity 8
dopo push_back(12): size 8, capacity 8
dopo push_back(13.5): size 9, capacity 16
dopo pop_back [size 8, capacity 16]: 1.5 3 4.5 6 7.5 9 10.5 12
dopo reserve(40) [size 8, capacity 40]: 1.5 3 4.5 6 7.5 9 10.5 12
dopo reserve(10) [size 8, capacity 40]: 1.5 3 4.5 6 7.5 9 10.5 12
w [size 3, capacity 3]: 1.5 2.5 3.5
copia [size 3, capacity 3]: 99 2.5 3.5
spostato [size 3, capacity 3]: 1.5 2.5 3.5
w dopo lo spostamento [size 0, capacity 0]:
cv[1] = 2.5, cv.at(2) = 3.5
at(3): indice fuori dai limiti

Si legge così:

il vettore vuoto non ha allocato nulla (capacity 0); il primo push_back porta la capacità a 4, il quinto a 8, il nono a 16: $4 \to 8 \to 16$ , raddoppi;
pop_back riduce size da 9 a 8 ma lascia capacity 16;
reserve(40) rialloca (capacity 40, stessi elementi), reserve(10) non fa nulla;
copia[0] = 99 non tocca w: la copia è profonda;
std::move(w) svuota w (size 0, capacity 0) e spostato ha gli elementi;
cv (una reference const) usa gli overload const di operator[] e at; at(3) su un vettore di 3 elementi lancia l'eccezione.

Versione ripasso

Dati: size_ (in uso), capacity_ (allocati), buffer_. Invarianti: $0 \le$ size_ $\le$ capacity_; capacity_ == 0 $\Rightarrow$ buffer_ == nullptr. Indici std::size_t (senza segno: size() - 1 su vuoto è enorme).
Operazioni essenziali: costruttori (vuoto, explicit con $n$ , initializer_list<double>), copia profonda (la copia ha capacity_ = size_), assegnamento di copia (alloca, copia, libera il vecchio, sostituisce; this == &other), spostamento noexcept (ruba il buffer, svuota la sorgente), distruttore delete[] buffer_.

cpp

void MyVector::reserve(std::size_t n)
{ if (n <= capacity_) return;
  double* nuovo = new double[n]; std::copy(buffer_, buffer_ + size_, nuovo);
  delete[] buffer_; buffer_ = nuovo; capacity_ = n; }
void MyVector::push_back(double v)
{ if (size_ == capacity_) reserve(capacity_ == 0 ? 4 : 2 * capacity_);
  buffer_[size_++] = v; }

Accesso: operator[] (double& e const double&, senza controllo); at(i) stesse due versioni, lancia out_of_range se $i \ge$ size_. pop_back decrementa size_ (la capacità resta; su vuoto out_of_range).
Politica di crescita: +1 $\to$ $N(N-1)/2$ copie, +10 $\to$ circa $N^2/20$ (entrambe $O(N^2)$ ), raddoppio $\to$ meno di $2N$ copie ( $O(N)$ totale, costo ammortizzato costante); $N = 10^5$ : 4 999 950 000, 499 950 000, 131 068.
Uscita del test: capacità 0, poi 4 (1° push_back), 8 (5°), 16 (9°); pop_back $\to$ size 8, capacity 16; reserve(40) $\to$ capacity 40, reserve(10) nessun effetto; la copia (copia[0] = 99) non tocca w; dopo std::move(w): w size 0, capacity 0; cv[1] = 2.5, cv.at(2) = 3.5; at(3) $\to$ out_of_range.
Copia e spostamento in breve:

cpp

MyVector::MyVector(const MyVector& o)                  // copia profonda: capacity_ = size_
    : size_{o.size_}, capacity_{o.size_}, buffer_{o.size_ > 0 ? new double[o.size_] : nullptr}
{ std::copy(o.buffer_, o.buffer_ + size_, buffer_); }
MyVector::MyVector(MyVector&& o) noexcept              // ruba e svuota la sorgente
    : size_{o.size_}, capacity_{o.capacity_}, buffer_{o.buffer_}
{ o.size_ = 0; o.capacity_ = 0; o.buffer_ = nullptr; }
double& MyVector::at(std::size_t i)
{ if (i >= size_) throw std::out_of_range("MyVector::at: indice fuori dai limiti"); return buffer_[i]; }
void MyVector::pop_back()
{ if (size_ == 0) throw std::out_of_range("MyVector::pop_back: vettore vuoto"); --size_; }

Assegnamento di copia: if (this == &other) return *this; poi nuovo = new double[other.size_] (1), std::copy (2), delete[] buffer_ (3), buffer_ = nuovo (4), size_ = capacity_ = other.size_; se new lancia, *this è intatto (garanzia forte). Assegnamento di spostamento: delete[] buffer_, prende i tre membri, azzera la sorgente.
Costruttori: vuoto (size_ = capacity_ = 0, buffer_ = nullptr, nessuna allocazione); explicit MyVector(size_t n) con std::fill(..., 0.0); initializer_list<double> con std::copy(lst.begin(), lst.end(), buffer_).
Test, righe chiave: dopo push_back(1.5): size 1, capacity 4, dopo push_back(7.5): size 5, capacity 8, dopo push_back(13.5): size 9, capacity 16; dopo pop_back [size 8, capacity 16]; dopo reserve(40) [size 8, capacity 40]; w dopo lo spostamento [size 0, capacity 0].
Errori tipici: copiare capacity_ elementi invece di size_; liberare prima di aver copiato (assegnamento); dimenticare noexcept e l'annullamento della sorgente; politica di crescita "+1"; reserve che riduce il buffer; usare int per gli indici e confrontare con size().
Garanzie: push_back con reserve alloca il nuovo buffer prima di liberare il vecchio: se new lancia, il vettore è intatto; pop_back e at segnalano gli errori con out_of_range (così il fuori limite non passa inosservato come con operator[]); lo spazio extra (capacity_ - size_) non è inizializzato né copiato.
Verso il laboratorio 5: la stessa classe con double sostituito da T: Esercizio - MyVector 2.0 con template (laboratorio 5).

Esercizio - MyVector 2.0 con buffer ridimensionabile (laboratorio 4)

Progetto

La politica di crescita

Il codice

Programma di prova

Esercizi su questo argomento

Teoria collegata