pro2::Vector<T>

Aquest tema explica com implementar una classe pro2::Vector<T>, que és una versió més senzilla de std::vector<T>, però preservant els conceptes més importants.

C++ té característiques que ens ajuden a implementar Vector<T>

En aquesta secció veurem característiques de C++ que permeten implementar el Vector<T> amb més facilitat.

using és una versió de typedef però més potent

L'ús que hem fet fins ara de typedef era per donar un nom a un tipus:

typedef vector<vector<int>> Matriu;

Però en el cas de punters, el typedef ens queda petit, i farem servir using, que tindrà el mateix significat: "donar un nom diferent a un tipus que ja existeix". Per exemple, la línia anterior amb typedef s'escriu així amb using:

using Matriu = vector<vector<int>>;

En general, la sintaxi és: using NomDelTipus = ...;, a on el nom és lliure, i el tipus és qualsevol, incloent punters. Per exemple:

using my_pointer = int *;
using my_ref = int &;

Aquest últim cas de punters amb typedef és més confús, i la sintaxi de using, en canvi, és molt més natural.

El Destructor

Quan creem objectes d'una classe, sabem que s'ha de cridar un constructor, que garanteix que l'objecte tingui un estat vàlid (el cas d'un rellotge o una data són força clars). Però hi ha objectes que en el constructor fan una cosa que, després, un cop l'objecte ja no hi és, caldria desfer.

El cas de la memòria és molt clar, si un constructor reserva memòria amb new quan l'objecte neix per poder emmagatzemar les seves dades, després quan l'objecte desapareix, caldria alliberar aquella memòria.

Això dóna la pista que només amb el constructor no en tenim prou, necessitem també un altre mètode especial que s'encarregui de la "desaparició ordenada" de l'objecte.

El destructor d'una classe C té un nom estàndard, també. Així com el constructor es diu exactament com la classe, el destructor té el nom ~C, és a dir, la tilde seguida del nom de la classe:

class C {
     x_;
:
    () { cout <<  << endl; }

    
    ~() { cout <<  << endl; }
};

Semblant al cas del constructor, el destructor no el cridem nosaltres directament, sinó que C++ s'encarrega de veure quan l'objecte ja no existirà i crida per si sol al destructor. En general, les variables "viuen" mentre el programa estigui dins del parell de claus en les que estan incloses. Per exemple:

int f() {
    C obj_c;
    cout << "sóc f" << endl;
}

int main() {
    f();
    f();
}

aquest programa mostrarà per pantalla

He nascut!
sóc f
M'he mort :(
He nascut!
sóc f
M'he mort :(

Quan cridem la funció f, es crea l'objecte obj_c, i es crida al constructor. Tot seguit, es mostra "sóc f", i, quan la funció acaba es crida el destructor de obj_c. Cada cop que es crida f passa tot això per tant el programa sencer és una repetició del mateix patró.

C++ permet redefinir els operadors

En C++, quan apliquem un operador, en realitat C++ ho entén d'una forma molt especial. Una expressió com a + b en realitat té, internament, dues interpretacions possibles:

operacio_suma(a, b);
a.operacio_suma(b);

És a dir, C++ espera una funció global operacio_suma que rebi a i b i retorni el resultat de la operació o bé considerem a com un objecte i cridem a operacio_suma com a mètode de la classe i li passem només b.

En realitat, el nom de la funció que C++ espera no és exactament aquest (en parlem a la propera secció) però la idea és que, si existeix alguna de les funcions esmentades, C++ les cridarà automàticament. Això ens permet redefinir el significat dels operadors clàssics!

operator... és el nom estàndard de la funció que C++ busca per operar

En realitat, a on abans hem posat operacio_suma el nom no era estàndard, el nom correcte és operator+. Els noms operator... en C++ són els noms especials que tenen tots els operadors (incloent el *, el ->, i l'accés indexat []).

Fem una taula de la traducció d'algunes expressions perquè s'entengui:

Curiositat 💎: donat que hi ha el pre-increment ++a i el post-increment a++, C++ es va haver d'inventar una forma de distingir-los, i és declarar un paràmetre int a l'operator++, que no s'acaba fent servir, ni rep cap valor (donat que l'increment és un operador unari). Així doncs:

Les regles de selecció d'un operador en C++ són complexes, però bàsicament, si es troba una funció global, es fa servir, i si no, es busca un mètode. Si es tria el cas c.operator*(d), per exemple, implica que l'operador de multiplicació entre c i d està definit a la classe de l'objecte c, i no com a funció.

C++ ja té definits els operadors bàsics

Per a tipus bàsics, els operadors ja existeixen, o sigui C++ ja sap com operar amb int, char, double i bool. Però, per exemple, la suma de strings és un operador definit per la classe string! De fet té dues versions, una a on se suma un string amb un altre string, i una a on se suma un string i un char.

Definir un operador nou és només fer la funció que C++ espera i posar el nom corresponent

Per definir un operador entre tipus que C++ no coneix internament, és suficient amb definir una funció, pensar bé els paràmetres que portarà (segons l'operador que sigui, tot i que la majoria són binaris, és a dir de dos operands), i posar-li el nom adequat a l'operador que toca. Per exemple, per incrementar una data (classe Data), si la classe Data ja té un mètode avansa(k) que avança k dies:

void operator++(Data& d) {
    d.avansa(1);
}

Això permetrà escriure programes fent servir l'operador ++ directament, en comptes d'haver de cridar a avansa:

Data d;
++d;

Per poder mostrar qualsevol vector per pantalla, podem definir la funció:

template<typename T>
ostream& operator<<(ostream& o, const vector<T>& v) {
    o << "[";
    if (!v.empty()) {
        o << v[0];
        for (int i = 1; i < v.size(); i++) {
            o << ", " << v[i];
        }
    }
    o << "]";
    return o;
}

I llavors, al programa principal, es pot fer:

int main() {
    vector<int> primers = {2, 3, 5, 7, 11, 13};
    cout << primers << endl;
}

i obtindrem [2, 3, 5, 7, 11, 13] per pantalla.

En la classe vector, escriurem una versió de l'operator[] per poder implementar què cal fer quan en un vector v s'accedeix a una casella amb v[i].

La classe Vector<T>

El plantejament de la classe vector és el següent:

• Reservarem caselles, però en blocs.
• En tot moment haurem de saber quantes caselles fem servir i quantes ens queden de reserva.
• Quan el vector creixi i ens quedem sense espai, reservarem una nova zona de memòria, del doble de tamany que l'anterior, i copiarem tots els elements a la nova zona.

Alhora, hem de fer servir el destructor per alliberar la memòria quan el vector desaparegui, i també utilitzar l'operador [] per l'accés a caselles.

Capçalera

Escriurem cada part del fitxer vector.hh i comentant les parts importants.

#ifndef VECTOR_HH
#define VECTOR_HH

namespace pro2 {

template <typename T>
class Vector {

Camps

Els camps són:

private:
    T *data_;
    int size_;       // Tamany utilitzat
    int capacity_;   // Tamany reservat

que, com hem dit, tenen un punter a l'inici de les dades, i dos enters per gestionar la quantitat d'espai i quant d'aquest s'utilitza realment.

Abans de tancar la part privada inicial també definim una constant interna al Vector que ens diu quin és el tamany mínim d'un vector no buit:

    static constexpr int initial_capacity_ = 4;

static ens diu que el membre initial_capacity_ és una propietat de la classe, no de cada objecte (per tant, Vector<T>::initial_capacity_), i constexpr ens diu que és una constant real.

Aquest tamany és dependent del comportament del programa, i no és bona idea fer suposicions, aquí. Es poden fer experiments amb l'execució del programa en les seves condicions típiques per veure si ajustant-lo s'obté algun tipus de benefici, ja sigui en menys ús de memòria o CPU.

Constructor per defecte

El constructor per defecte és senzill, posar el punter nullptr i els enters a 0. Un vector buit.

public:
    Vector() : data_(nullptr), size_(0), capacity_(0) {}

Constructor amb un tamany

El constructor més típic, en què demanem un tamany n, consisteix només en reservar l'espai demanat, i apuntar-nos que aquesta és la capacitat i que es fa servir tota:

    Vector(int n) {
        assert(n >= 0, "Vector::Vector(int): mida negativa!");
        data_ = new T[n];
        size_ = n;
        capacity_ = n;
    }

La resta de constructors són més llargs i no els definirem inline:

    Vector(int n, const T& x);   // tamany + valor inicial
    Vector(const Vector& other); // de còpia

Destructor

El destructor no és complex, simplement cal recordar d'alliberar el punter data_:

    ~Vector() {
        delete[] data_;
    }

Accés a caselles amb []

Aquí apliquem el fet que aquest operador té el nom operator[] i que rep un enter. Haurem de fer dues versions, perquè en un cas retornem una referència normal i en l'altre cas una referència const:

    T& operator[](int i) {
        assert(i >= 0 && i < size_,
               "Vector::operator[]: índex fora de rang!");
        return data_[i];
    }

    const T& operator[](int i) const {
        assert(i >= 0 && i < size_,
               "Vector::operator[]: índex fora de rang!");
        return data_[i];
    }

Com es veu, tenim un assert que impedeix que el programa accedeixi a caselles fora del rang, tot i que fer aquesta comprovació cada cop és costós.

El fet que calgui posar dos operadors que són idèntics és perquè necessitem poder accedir a les caselles tant quan el vector és modificable com quan no ho és (per exemple, si es passa com a paràmetre const d'una funció).

El fet que aquests mètodes retornin una referència implica que estan retornant la "variable" original, no una còpia. Per tant, es pot fer això:

Vector<int> v(4);
v.operator[](3) = 5; // perquè v.operator[](3) és un int&

que és el mateix que: v[3] = 5;. En el cas d'un Vector const no podem modificar els valors, per tant es retorna un const T&, que implica que no podrem modificar el T.

size, empty, i capacity

Aquests 3 mètodes simplement retornen un camp directament:

    int size()     const { return size_; }
    int capacity() const { return capacity_; }
    bool empty()   const { return size_ == 0; }

però és perquè la nostra representació ho permet. Amb una altra representació potser seria diferent.

Iteradors

Ara, per poder tenir Vector<int>::iterator que ens permetrà ordenar el nostre vector amb sort i utilitzar la resta d'algorismes de la STL, declararem els tipus de l'iterador i el const iterador amb using:

public:
    using iterator = T *;
    using const_iterator = const T *;

La definició clarament diu que un iterador a un Vector és simplement un punter, tant amb const com sense.

begin i end

Ara és senzill implementar begin i end, tot i que torna a passar que necessitem dues versions, amb const i sense const.

    iterator begin()             { return data_; }
    const_iterator begin() const { return data_; }
    iterator end()               { return data_ + size_; }
    const_iterator end()   const { return data_ + size_; }

clear

El mètode clear també és força senzill: alliberem la memòria (perquè el Vector es buidarà), i posem els tamanys a 0.

    void clear() {
        // Una alternativa seria simplement posar `size_` a 0 sense
        // alliberar la memòria, mantenint la capacitat per a futures
        // insercions (que és el que fa `std::vector::clear()`).
        delete[] data_;
        data_ = nullptr;
        size_ = 0;
        capacity_ = 0;
    }

Després del més bàsic, venen mètodes auxiliars i altres més complexos, que primer declararem, perquè no són inline, i després implementarem fora de la classe mateixa.

private:
    // Mètode privat per reservar un nou bloc,
    // copiant els elements existents.
    void reallocate_(int new_capacity);

public:
    void push_back(const T& x);
    void pop_back();
    void resize(int n);
    void reserve(int n);

    // Operador d'assignació
    Vector& operator=(const Vector& other);
};

reallocate_

En aquest mètode és on es demana una nova capacitat, que pot ser menor o major. Tant si és major com menor, cal copiar els elements del vector, però llavors s'ha de veure si cal copiar-los tots o no. Si la capacitat és menor, només cal copiar fins new_capacity; si és major, tots els elements, és a dir size_. El min(new_capacity, size_) dóna aquest resultat.

template <typename T>
void Vector<T>::reallocate_(int new_capacity) {
    T *new_data = new T[new_capacity];
    int new_size = min(new_capacity, size_);
    for (int i = 0; i < new_size; ++i) {
        new_data[i] = data_[i];
    }
    delete[] data_;
    data_ = new_data;
    capacity_ = new_capacity;
    size_ = new_size;
}

Constructor que omple amb un valor

Aquest constructor és pràcticament igual que el seu homòleg però afegint un for que omple les caselles:

template <typename T>
Vector<T>::Vector(int n, const T& x) {
    assert(n >= 0, "Vector::Vector(int, const T&): mida negativa!");
    data_ = new T[n];
    size_ = n;
    capacity_ = n;
    for (int i = 0; i < n; ++i) {
        data_[i] = x;
    }
}

Constructor de còpia

Aquest constructor és molt important, ja que si no es fa, C++ en proporciona un que funcionaria malament i donaria lloc a un doble delete[], ja que el constructor de còpia per defecte simplement copia els camps directament i per tant hi hauria dos punters apuntant a la mateixa zona de memòria, que un cop es destruïssin, donarien lloc al doble delete[].

Per tant, el constructor de còpia realment ha de reservar memòria, i copiar tots i cadascún dels elements.

template <typename T>
Vector<T>::Vector(const Vector& other)
    : data_(new T[other.capacity_]),
      size_(other.size_),
      capacity_(other.capacity_)
{
    for (int i = 0; i < size_; ++i) {
        data_[i] = other.data_[i];
    }
}

Si recordeu, a PRO1 sempre hem escrit les funcions que reben els vectors de la STL com f1 o f2 en l'exemple següent:

void f1(std::vector<int>& v) { ... }
void f2(const std::vector<int>& v) { ... }

Les dues funcions reben el vector per referència, i la raó era per evitar la còpia, que crida el constructor i per tant té un cost $O(n)$, sent $n$ el tamany del vector!

Operador d'assignació

L'operador d'assignació té encara més feina, perquè fa una cosa semblant que el constructor de còpia, però parteix d'un vector que potser ja té contingut, per tant el primer que cal fer és esborrar el que hi havia (o potser reciclar una part).

I a sobre, podria passar que algú escrigués v = v, que no té massa sentit però és un programa vàlid, i per tant cal guardar-nos d'aquest cas (this != &other). Es fa servir l'adreça del vector other i es compara amb this que és l'adreça del vector destí. Si són diferents, llavors es fa l'assignació, sinó no es fa.

El codi de la còpia no intenta reciclar res, i directament allibera la memòria antiga, i directament reserva memòria nova i copia tots els valors, copiant també la capacitat i el tamany.

template <typename T>
Vector<T>& Vector<T>::operator=(const Vector& other) {
    if (this != &other) {
        delete[] data_;
        capacity_ = other.capacity_;
        size_ = other.size_;
        data_ = new T[capacity_];
        for (int i = 0; i < size_; ++i) {
            data_[i] = other.data_[i];
        }
    }
    return *this;
}

push_back

Aquest mètode és el que demostra que, normalment, un push_back és una operació $O(1)$, molt ràpida, però de tant en tant (quan la reserva de caselles arriba a zero), cal redimensionar. També es veu perquè el cost s'amortitza, ja que el número de redimensionaments decau exponencialment, donat que cada cop es reserva espai pel doble de caselles. Per tant, el cost de push_back és $O(1)$ amortitzat en totes les crides.

template <typename T>
void Vector<T>::push_back(const T& x) {
    if (size_ == capacity_) {
        reallocate_(capacity_ == 0 ? initial_capacity_ : 2 * capacity_);
    }
    data_[size_] = x;
    ++size_;
}

La constant initial_capacity_ l'hem definida més amunt, just al principi.

pop_back

En el pop_back també reduïm la capacitat si el vector es buida prou. Concretament, quan el tamany baixa per sota d'un quart de la capacitat, s'allibera la memòria i es reserva espai per a la meitat. És important utilitzar el llindar a un quart i no a la meitat: amb el llindar a la meitat, una seqüència alternada de push_back i pop_back al voltant del límit causaria un redimensionament a cada operació, i perdríem el cost amortitzat $O(1)$.

template <typename T>
void Vector<T>::pop_back() {
    assert(size_ > 0, "Vector::pop_back: vector buit!");
    --size_;
    if (size_ < capacity_ / 4) {
        reallocate_(capacity_ / 2);
    }
}

resize

resize permet que l'usuari del vector decideixi un nou tamany de cop, i aquí tenim vàries opcions. La opció d'aquest mètode és

template <typename T>
void Vector<T>::resize(int n) {
    assert(n >= 0, "Vector::resize: mida negativa!");
    reallocate_(n);
    size_ = n;
}

reserve

Aquest mètode permet tenir un control millor sobre els moments en què el vector es redimensionarà. Si d'entrada sabem que necessitarem 1000 caselles, és millor reservar-les d'entrada (tot i que el tamany sigui 0), que no pas fer uns $\log_2(1000)$ redimensionaments.

template <typename T>
void Vector<T>::reserve(int n) {
    assert(n >= 0, "Vector::reserve: capacitat negativa!");
    if (n > capacity_) {
        reallocate_(n);
    }
}

I ja només falta tancar el namespace i la protecció de doble #include.

}  // namespace pro2

#endif