Implementierung der Klasse std :: vector

Question

Ich freue mich auf Ihr Feedback zu meinem Versuch, die Funktionalität von Vektorklassen zu replizieren. Insbesondere habe ich Zweifel an Kopierkonstruktor- und Größenänderungsmethoden. Ich denke, dass der Kopierkonstruktor möglicherweise zu einem Speicherverlust führen kann, aber ich weiß nicht, wie ich ihn verbessern kann. Ich habe zwei Größenänderungsmethoden implementiert und beide scheinen zu funktionieren, aber welche ist eigentlich besser?

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

Vielen Dank.

Answer 1

Über den Kopierkonstruktor und resize()

Im Kopierkonstruktor (und auch in den anderen Konstruktoren) weisen Sie Speicher mit zu new T[...], aber in resize()ordnen Sie Speicher mit zu new char[sizeof(T) * ...]und verwenden dann die Platzierung neu, um die alten Elemente zu kopieren. Ersteres ist sicher, ruft jedoch möglicherweise mehr Konstruktoren als erwartet auf. Letzteres hat das Problem, dass Sie nicht genutzte Kapazität haben können, die nie ordnungsgemäß initialisiert wurde. Wenn Sie deletedies jedoch tun, rufen Sie den Destruktor für alle reservierten Elemente auf.

Gehen Sie wie Tfolgt vor, um sicher zu gehen und den Konstruktor für reservierte Elemente nicht aufzurufen :

• Verwenden char *m_DataSie diese Option , um den zugewiesenen Speicher zu verfolgen (Sie können ihn auch behalten T *m_Data, müssen jedoch darauf achten, dass Sie niemals delete[] m_Datadirekt anrufen ).
• Verwenden Sie immer die Platzierung, newwenn Sie dem Vektor tatsächliche Elemente hinzufügen
• Verwenden Sie immer "Platzierung delete", wenn Sie tatsächliche Elemente aus dem Vektor löschen

Idealerweise möchten Sie auch std::moveElemente während resize(), aber das ist schwierig, insbesondere wenn Tder Verschiebungskonstruktor Ausnahmen auslösen kann.

Abweichung von std::vector

Wie bereits in den Kommentaren erläutert, unterscheidet sich Ihre Vektorklasse geringfügig von std::vector. Dies ist auf die Anforderungen des Auftrags zurückzuführen. Außerhalb von Klassenzuweisungen gibt es auch reale Szenarien, in denen Sie nicht verwenden können std::vector, die Sie jedoch selbst implementieren müssen. In diesem Fall möchten Sie die Benutzeroberfläche so weit wie möglich std::vectorunverändert lassen, um sicherzustellen, dass Ihre eigene Klasse ein Ersatz ist und es keine Überraschungen gibt.

Konstruktor reserviert Platz im Vergleich zum Zuweisen von Elementen

Ihr Konstruktor, der ein size_tArgument verwendet, verwendet es, um Speicherplatz zu reservieren, fügt dem Vektor jedoch keine Elemente hinzu. Der entsprechende Konstruktor von std::vectorverwendet das Argument jedoch, um tatsächliche Elemente zuzuweisen, die standardmäßig initialisiert sind. Auch mit Ihrer Klasse:

Vector<int> v(4, 2);

Dadurch wird nur Platz für zwei Elemente reserviert, die nicht initialisiert sind, und m_Sizeauf 4 gesetzt, wodurch die Größen nicht miteinander übereinstimmen und ein nachfolgender Aufruf operator[]()ohne Fehler ausgelesen werden kann. Vergleichen Sie dies mit:

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

Dies ordnet einen Vektor von 4 Elementen zu, die alle auf den Wert initialisiert sind 2. Also ein ganz anderes Verhalten.

Verwenden Sie size_tfür Zähler

In dem Konstruktor, der eine Initialisierungsliste verwendet, verwenden Sie int cnt, aber eine ist intmöglicherweise nicht groß genug. Verwenden Sie size_tkonsequent für Größen, Zählungen und Indizes.

Sie können Speicher in der Mitgliederinitialisierungsliste zuweisen

Nur eine Anmerkung, dass Sie komplexere Ausdrücke in der Mitgliederinitialisierungsliste haben können, einschließlich solcher mit Nebenwirkungen wie dem Zuweisen von Speicher. So können Sie schreiben:

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

In diesem Fall spielt es keine Rolle, aber es ist eine gute Praxis , dies zu tun, da es in einigen Fällen Vorteile gibt.

Werfen Sie mit einem geeigneten Ausnahmetyp

throwVerwenden Sie keine zufälligen Zeichenfolgen, sondern verwenden Sie einen geeigneten Typ für die Ausnahme. Wenn Sie die Standardbibliothek verwenden möchten, wählen Sie einen geeigneten Typ aus , zum Beispiel:

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

Wenn Sie die Standardbibliothek nicht verwenden können, definieren Sie mindestens Ihren eigenen Ausnahmetyp, damit ein Aufrufer bestimmte Catch-Blöcke verwenden kann. Angenommen, Sie möchten Folgendes tun:

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
}

Wenn Sie nur eine Zeichenfolge werfen, können Sie nur einen catchBlock haben, der dann die Zeichenfolge analysieren muss, um herauszufinden, was los ist.

Erwägen Sie, keine Grenzen einzuchecken operator[]()

Die Standardbibliothek führt bei der Verwendung keine Grenzüberprüfungen durch operator[](), da dies einen erheblichen Einfluss auf die Leistung hat. Es gibt eine separate Funktion, at()die Grenzwertprüfungen durchführt.

Keine Notwendigkeit, Vector<T>hinein zu schreibenVector

Innerhalb der Klassendefinition müssen Sie nicht schreiben Vector<T>, sondern nur schreiben Vector.

Fehlende Iteratoren

Ihre Klasse implementiert keine Iteratoren, daher können Sie nicht Folgendes schreiben:

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

Es ist eine gute Übung, Iteratoren für Ihre Klasse zu implementieren.