Implémentation de la classe std :: vector

Question

Au plaisir de recevoir vos commentaires sur ma tentative de répliquer la fonctionnalité de classe vectorielle. Surtout, j'ai des doutes sur le constructeur de copie et les méthodes de redimensionnement. Je pense que le constructeur de copie pourrait potentiellement provoquer une fuite de mémoire, mais je ne sais pas comment l'améliorer. J'ai implémenté deux méthodes de redimensionnement et elles semblent toutes les deux fonctionner, mais quelle est la meilleure?

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

Je vous remercie.

Answer 1

À propos du constructeur de copie et resize()

Dans le constructeur de copie (et les autres constructeurs également), vous allouez de la mémoire en utilisant new T[...], mais resize()vous allouez de la mémoire avec new char[sizeof(T) * ...], puis utilisez le placement nouveau pour copier les anciens éléments. Le premier est sûr, mais appelle potentiellement plus de constructeurs que prévu, le second a le problème que vous pouvez avoir une capacité inutilisée qui n'a jamais été correctement initialisée, mais lorsque vous deletele faites, vous appellerez le destructeur sur tous les éléments réservés.

Pour être sûr et pour éviter d'appeler le constructeur de Tpour les éléments réservés, procédez comme suit de manière cohérente:

• Utilisez char *m_Datapour garder une trace de la mémoire allouée (vous pouvez la conserver comme T *m_Data, mais vous devez faire attention à ne jamais appeler delete[] m_Datadirectement)
• Utilisez toujours le placement newlors de l'ajout d'éléments réels au vecteur
• Utilisez toujours «placement delete» lors de la suppression d'éléments réels du vecteur

De plus, idéalement, vous voulez des std::moveéléments pendant resize(), mais c'est délicat, surtout si Tle constructeur de mouvement de s peut lever des exceptions.

Divergence de std::vector

Comme déjà discuté dans les commentaires, votre classe vectorielle est légèrement différente de std::vector. Cela est dû aux exigences de la mission. En dehors des devoirs de cours, il existe également de vrais scénarios où vous ne pouvez pas utiliser std::vector, mais où vous devez l'implémenter vous-même. Dans ce cas, vous voulez garder l'interface autant que possible la même que celle de std::vector's, pour vous assurer que votre propre classe est un remplacement instantané, et il n'y a pas de surprises.

Constructeur réservant de l'espace ou allouant des éléments

Votre constructeur qui prend un size_targument l'utilise pour réserver de l'espace, mais n'ajoute aucun élément au vecteur. Cependant, le constructeur correspondant de std::vectorutilise l'argument pour allouer des éléments réels qui sont initialisés par défaut. Aussi, avec votre classe:

Vector<int> v(4, 2);

Cela n'alloue que de l'espace pour deux éléments, qui ne sont pas initialisés, et définit m_Sizeà 4, ce qui rend les tailles incohérentes les unes avec les autres et permet à un appel ultérieur de operator[]()lire hors limites sans générer d'erreur. Comparez cela avec:

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

Ceci alloue un vecteur de 4 éléments qui sont tous initialisés à la valeur 2. Donc un comportement tout à fait différent.

Utiliser size_tpour les compteurs

Dans le constructeur qui prend une liste d'initialiseurs, vous utilisez int cnt, mais un intpeut ne pas être assez grand. Utilisez size_tsystématiquement pour les tailles, les nombres et les indices.

Vous pouvez allouer de la mémoire dans la liste d'initialisation des membres

Notez simplement que vous pouvez avoir des expressions plus complexes dans la liste d'initialiseurs de membres, y compris celles avec des effets secondaires tels que l'allocation de mémoire. Vous pouvez donc écrire:

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

Cela n'a pas vraiment d'importance dans ce cas, mais c'est une bonne pratique de le faire, car il y a des avantages dans certains cas.

Lancer en utilisant un type d'exception approprié

N'utilisez pas de throwchaînes aléatoires, mais utilisez un type approprié pour l'exception. Si vous deviez utiliser la bibliothèque standard, sélectionnez un type approprié , par exemple:

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

Si vous ne pouvez pas utiliser la bibliothèque standard, définissez au moins votre propre type d'exception, afin qu'un appelant puisse utiliser des blocs catch spécifiques. Par exemple, considérez que vous souhaiterez peut-être effectuer les opérations suivantes:

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
}

Si vous lancez simplement une chaîne, vous ne pouvez avoir qu'un seul catchbloc, qui doit ensuite analyser la chaîne pour comprendre ce qui se passe.

Envisagez de ne pas enregistrer les limites operator[]()

La bibliothèque standard n'effectue pas de vérification des limites lors de son utilisation operator[](), car elle a un impact significatif sur les performances. Il existe une fonction distincte at(), qui vérifie les limites.

Pas besoin d'écrire à l' Vector<T>intérieurVector

Dans la définition de classe, vous n'avez pas besoin d'écrire Vector<T>, écrivez simplement Vector.

Itérateurs manquants

Votre classe n'implémente pas d'itérateurs, vous ne pouvez donc pas écrire quelque chose comme:

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

C'est un bon exercice pour essayer d'implémenter des itérateurs pour votre classe.