Implementazione della classe std :: vector

Question

Non vedo l'ora di ricevere il tuo feedback sul mio tentativo di replicare la funzionalità della classe vettoriale. Soprattutto ho dei dubbi sul costruttore di copie e sui metodi di ridimensionamento. Penso che il costruttore di copie possa potenzialmente causare perdite di memoria, ma non so come migliorarlo. Ho implementato due metodi di ridimensionamento ed entrambi sembrano funzionare, ma qual è effettivamente il migliore?

#include <iostream>
#include <type_traits>
#include <math.h>

template <typename T>
class Vector {
private:
    T* m_Data;
    size_t m_Size, m_Capacity;
public:
    Vector(size_t cap = 2)
        : m_Size(0), m_Capacity(cap) {
        m_Data = new T[cap];
    }
    
    Vector(size_t size, size_t cap)
        : m_Size(size), m_Capacity(cap) {
        m_Data = new T[cap];
    }

    Vector(const std::initializer_list<T>& il)
        : Vector(il.size(), il.size() * 2) {
        int cnt = 0;
        for (const auto& el : il)
            m_Data[cnt++] = el;
    }
   
    // copy constructor, makes deep copy
    Vector(const Vector& v)
        : m_Size(v.size()), m_Capacity(v.capacity()) {
        m_Data = new T[m_Capacity];
        for (size_t i = 0; i < m_Size; i++) {
            m_Data[i] = v[i];
        }
    }
    
    ~Vector() {
        delete[] m_Data;
    }

//    void resize(size_t newCapacity) {
//        T* newData = new T[newCapacity];
//        m_Size = std::min(m_Size, newCapacity);
//
//        for (size_t i = 0; i < m_Size; i++)
//            newData[i] = std::move(m_Data[i]);
//
//        delete[] m_Data;
//        m_Data = newData;
//        m_Capacity = newCapacity;
//    }
    
    void resize(size_t newCapacity) {
        char* newData = new char[sizeof(T) * newCapacity];
        m_Size = std::min(m_Size, newCapacity);
        
        T* dst = reinterpret_cast<T*>(newData);
        for (size_t i = 0; i < m_Size; i++)
            new (dst + i) T(m_Data[i]);
        
        delete[] m_Data;
        m_Data = reinterpret_cast<T*>(newData);
        m_Capacity = newCapacity;
    }
    

        
    void push_back(const T& n) {
        if (m_Capacity <= m_Size)
            resize(m_Capacity * 2);
    
        m_Data[m_Size++] = n;
    }
    
    void push_back(const T&& n) {
        if (m_Capacity <= m_Size)
            resize(m_Capacity * 2);
    
        m_Data[m_Size++] = std::move(n);
    }
    
    void pop_back() {
        if (m_Size > 0)
            m_Data[--m_Size].~T();
    }

    void clear() {
        for (size_t i = 0; i < m_Size; i++)
            m_Data[i].~T();
        m_Size = 0;
    }
    
    size_t size() const {
        return m_Size;
    }
    
    size_t capacity() const {
        return m_Capacity;
    }
    
    bool empty() const {
        return m_Size == 0;
    }
    
    const T& operator[](size_t index) const {
        if (index >= m_Size)
            throw "Index out of bounds";
        
        return m_Data[index];
    }
    
    T& operator[](size_t index) {
        if (index >= m_Size)
            throw "Index out of bounds";
        
        return m_Data[index];
    }
    
    Vector<T> operator+(const Vector& other) {
        if (m_Size != other.size())
            throw "Vectors are of different size";
        
        Vector<T> v(m_Size);
        for (size_t i = 0; i < m_Size; i++) {
            v.push_back(m_Data[i] + other[i]);
        }
        
        return v;
    }
    
};

template <
typename T,
typename = typename std::enable_if<std::is_arithmetic<T>::value, T>::type>
int norm(const Vector<T> v) {
    int nrm = 0;
    size_t n = v.size();
    
    for (int i = 0; i < n; i++) {
        nrm += v[i]*v[i];
    }
    
    return sqrt(nrm);
}

template <typename T>
std::ostream& operator<<(std::ostream& s, const Vector<T>& v) {
    s << "[";
    size_t n = v.size();
    for (size_t i = 0; i < n; i++) {
        s << v[i] << (i < n - 1 ? ", " : "");
    }
    s << "]";
    return s;
}

int main(int argc, const char * argv[]) {
    Vector<int>* a = new Vector<int> {1, 2, 3, 4, 5};
    Vector<int> b = {5, 4, 3, 2, 6};
    Vector<int> c = b;

    return 0;
}

Grazie.

Answer 1

Informazioni sul costruttore di copie e resize()

Nel costruttore di copia (e anche negli altri costruttori), si alloca la memoria utilizzando new T[...], ma in resize()si alloca la memoria con new char[sizeof(T) * ...]e quindi si utilizza la posizione nuova per copiare i vecchi elementi. Il primo è sicuro, ma potenzialmente chiama più costruttori del previsto, il secondo ha il problema che puoi avere capacità inutilizzate che non sono mai state inizializzate correttamente, ma quando deletelo farai chiamerai il distruttore su tutti gli elementi riservati.

Per sicurezza ed evitare di chiamare il costruttore di Tper elementi riservati, eseguire le operazioni seguenti in modo coerente:

• Usa char *m_Dataper tenere traccia della memoria allocata (potresti tenerla come T *m_Data, ma devi stare attento a non chiamare mai delete[] m_Datadirettamente)
• Usa sempre il posizionamento newquando aggiungi elementi reali al vettore
• Usa sempre "posizionamento delete" quando elimini gli elementi effettivi dal vettore

Inoltre, idealmente vuoi gli std::moveelementi durante resize(), ma questo è complicato, specialmente se Til costruttore di mosse può generare eccezioni.

Divergenza da std::vector

Come già discusso nei commenti, la tua classe vettoriale è leggermente diversa da std::vector. Ciò è dovuto ai requisiti dell'assegnazione. Al di fuori dei compiti in classe, ci sono anche scenari reali in cui non puoi usare std::vector, ma devi implementarlo da solo. In tal caso, si desidera mantenere l'interfaccia il più possibile uguale a quella std::vectordi, per assicurarsi che la propria classe sia un sostituto immediato e non ci siano sorprese.

Costruttore che riserva lo spazio vs. allocazione di elementi

Il tuo costruttore che accetta un size_targomento lo usa per riservare spazio, ma non aggiunge alcun elemento al vettore. Tuttavia, il costruttore corrispondente di std::vectorutilizza l'argomento per allocare gli elementi effettivi che sono inizializzati per impostazione predefinita. Inoltre, con la tua classe:

Vector<int> v(4, 2);

Questo alloca solo lo spazio per due elementi, che non sono inizializzati, e imposta m_Sizea 4, rendendo le dimensioni incoerenti tra loro e consentendo a una chiamata successiva di operator[]()leggere fuori dai limiti senza generare un errore. Confronta questo con:

std::vector<int> v(4, 2);

Questo alloca un vettore di 4 elementi che sono tutti inizializzati al valore 2. Quindi un comportamento abbastanza diverso.

Utilizzare size_tper i contatori

Nel costruttore che accetta un elenco di inizializzatori, usi int cnt, ma intpotrebbe non essere abbastanza grande. Utilizzare in modo size_tcoerente per dimensioni, conteggi e indici.

È possibile allocare memoria nell'elenco degli inizializzatori dei membri

Solo una nota che puoi avere espressioni più complesse nell'elenco degli inizializzatori dei membri, comprese quelle con effetti collaterali come l'allocazione della memoria. Quindi puoi scrivere:

Vector(size_t size, size_t cap)
    : m_Data(new T[cap]), m_Size(size), m_Capacity(cap) {}

Non ha molta importanza in questo caso, ma è buona norma farlo, poiché in alcuni casi ci sono dei vantaggi.

Lancia utilizzando un tipo di eccezione appropriato

Non throwstringhe casuali, ma usa un tipo appropriato per l'eccezione. Se dovessi utilizzare la libreria standard, seleziona un tipo adatto , ad esempio:

if (index >= m_Size)
    throw std::out_of_range("Index out of bounds");

Se non è possibile utilizzare la libreria standard, definire almeno il proprio tipo di eccezione, in modo che un chiamante possa utilizzare specifici blocchi di cattura. Ad esempio, considera che potresti voler fare quanto segue:

try {
    Vector<int> v(100000); // might throw std::bad_alloc if `new` fails
    Vector<int> w(10000);
    v[100000] = 10;   // out of range error
    v += w;           // vectors of different size
}
catch (std::bad_alloc &e) {
    // out of memory
}
catch (std::out_of_bounds &e) {
    // handle index out of bounds
}
catch (std::invalid_argument &e) {
    // handle operator+[] with an argument of the wrong size
}

Se lanci solo una stringa, puoi avere solo un catchblocco, che deve quindi analizzare la stringa per capire cosa sta succedendo.

Considera di non fare il check-in per i limiti operator[]()

La libreria standard non esegue controlli dei limiti durante l'utilizzo operator[](), poiché ha un impatto significativo sulle prestazioni. Esiste una funzione separata at(), che esegue i controlli dei limiti.

Non c'è bisogno di scrivere Vector<T>dentroVector

All'interno della definizione della classe non è necessario scrivere Vector<T>, basta scrivere Vector.

Iteratori mancanti

La tua classe non implementa gli iteratori, quindi non puoi scrivere qualcosa come:

Vector<int> v(10);
...
for (auto el: v) {
    std::cout << el << "\n";
}

È un buon esercizio provare a implementare gli iteratori per la tua classe.