Implementacja klasy std :: vector

Question

Nie mogę się doczekać, aby poznać Twoją opinię na temat mojej próby odtworzenia funkcjonalności klas wektorowych. Szczególnie mam wątpliwości co do konstruktora kopiującego i metod zmiany rozmiaru. Myślę, że konstruktor kopiujący może potencjalnie spowodować wyciek pamięci, ale nie wiem, jak to poprawić. Zaimplementowałem dwie metody zmiany rozmiaru i obie wydają się działać, ale która z nich jest lepsza?

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

Dziękuję Ci.

Answer 1

O konstruktorze kopiującym i resize()

W konstruktorze kopiującym (a także w innych konstruktorach) alokujesz pamięć przy użyciu new T[...], ale w resize()tym przypadku przydzielasz pamięć za pomocą, new char[sizeof(T) * ...]a następnie umieszczasz nowe, aby skopiować stare elementy. Pierwsza jest bezpieczna, ale potencjalnie wywołuje więcej konstruktorów niż oczekiwano, druga ma problem z tym, że możesz mieć niewykorzystaną pojemność, która nigdy nie została poprawnie zainicjowana, ale kiedy deleteto zrobisz, wywołasz destruktor na wszystkich zarezerwowanych elementach.

Aby być bezpiecznym i uniknąć wywoływania konstruktora Tfor zarezerwowanych elementów, konsekwentnie wykonaj następujące czynności:

• Służy char *m_Datado śledzenia przydzielonej pamięci (możesz zachować ją jako T *m_Data, ale musisz uważać, aby nigdy nie dzwonić delete[] m_Databezpośrednio)
• Zawsze używaj umieszczania newpodczas dodawania rzeczywistych elementów do wektora
• Zawsze używaj „umieszczania delete” podczas usuwania rzeczywistych elementów z wektora

Idealnie byłoby też, gdybyś chciał std::moveelementy w trakcie resize(), ale to jest trudne, zwłaszcza jeśli Tkonstruktor przenoszenia może rzucać wyjątki.

Rozbieżność z std::vector

Jak już wspomniano w komentarzach, Twoja klasa wektorowa różni się nieco od std::vector. Wynika to z wymagań zadania. Poza zadaniami klasowymi istnieją również rzeczywiste scenariusze, z których nie możesz korzystać std::vector, ale musisz je wdrożyć samodzielnie. W takim przypadku chcesz, aby interfejs był jak najbardziej taki sam, jak ten std::vector, aby mieć pewność, że Twoja własna klasa jest zamiennikiem typu drop-in i nie ma żadnych niespodzianek.

Konstruktor rezerwujący miejsce a alokowanie elementów

Twój konstruktor, który pobiera size_targument, używa go do zarezerwowania miejsca, ale nie dodaje żadnych elementów do wektora. Jednak odpowiedni konstruktor z std::vectorużywa argumentu do przydzielania rzeczywistych elementów, które są domyślnie zainicjowane. Również z twoją klasą:

Vector<int> v(4, 2);

To przydziela tylko miejsce na dwa elementy, które nie są zainicjowane, i ustawia m_Sizena 4, sprawiając, że rozmiary są niezgodne ze sobą i pozwalając kolejnemu wywołaniu na operator[]()odczytanie poza granice bez zgłaszania błędu. Porównaj to z:

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

Spowoduje to przydzielenie wektora 4 elementów, z których wszystkie są inicjalizowane na wartość 2. Więc zupełnie inne zachowanie.

Służy size_tdo liczników

W konstruktorze, który pobiera listę inicjalizatora, używasz int cnt, ale intmoże nie być wystarczająco duży. Używaj size_tkonsekwentnie dla rozmiarów, liczebności i indeksów.

Możesz przydzielić pamięć na liście inicjatorów elementu członkowskiego

Tylko uwaga, że ​​możesz mieć bardziej złożone wyrażenia na liście inicjatorów elementu członkowskiego, w tym te z efektami ubocznymi, takimi jak przydzielanie pamięci. Możesz więc napisać:

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

W tym przypadku nie ma to większego znaczenia, ale jest to dobra praktyka , ponieważ w niektórych przypadkach są pewne korzyści.

Wyrzuć używając odpowiedniego typu wyjątku

Nie throwlosuj ciągów, ale użyj odpowiedniego typu dla wyjątku. Gdybyś miał skorzystać z biblioteki standardowej, wybierz odpowiedni typ spośród np .:

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

Jeśli nie możesz użyć standardowej biblioteki, to przynajmniej zdefiniuj własny typ wyjątku, aby wywołujący mógł użyć określonych bloków catch. Na przykład rozważ, że możesz chcieć wykonać następujące czynności:

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
}

Jeśli po prostu wyrzucisz łańcuch, możesz mieć tylko jeden catch-block, który następnie musi przeanalizować łańcuch, aby dowiedzieć się, co się dzieje.

Rozważ rezygnację z wpisywania granic operator[]()

Biblioteka standardowa nie sprawdza granic podczas używania operator[](), ponieważ ma znaczący wpływ na wydajność. Istnieje oddzielna funkcja at(), która sprawdza granice.

Nie musisz pisać w Vector<T>środkuVector

W definicji klasy nie musisz pisać Vector<T>, po prostu pisz Vector.

Brakujące iteratory

Twoja klasa nie implementuje iteratorów, więc nie możesz napisać czegoś takiego:

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

Warto spróbować zaimplementować iteratory dla swojej klasy.