Std :: vector sınıfının gerçeklenmesi

Question

Vektör sınıfı işlevselliğini çoğaltma girişimim hakkında geri bildiriminizi almak için sabırsızlanıyorum. Özellikle kopya yapıcı ve yeniden boyutlandırma yöntemleri hakkında şüphelerim var. Kopya oluşturucusunun bellek sızıntısına neden olabileceğini düşünüyorum, ancak nasıl daha iyi hale getireceğimi bilmiyorum. İki yeniden boyutlandırma yöntemi uyguladım ve ikisi de çalışıyor gibi görünüyor, ancak hangisi aslında daha iyi?

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

Teşekkür ederim.

Answer 1

Kopya oluşturucu hakkında ve resize()

Copy yapıcısında (ve diğer kurucularda), kullanarak bellek ayırırsınız new T[...], ancak içinde resize()bellek ayırır new char[sizeof(T) * ...]ve ardından eski öğeleri kopyalamak için yeni yerleşimi kullanırsınız. İlki güvenlidir, ancak potansiyel olarak beklenenden daha fazla kurucu çağırır, ikincisi, hiçbir zaman düzgün şekilde başlatılmamış kullanılmamış kapasiteye sahip olabileceğiniz sorununa sahiptir, ancak deletebunu yaptığınızda, tüm ayrılmış öğeler için yıkıcıyı çağıracaksınız.

Güvende olmak ve Tayrılmış öğeler için yapıcısını çağırmaktan kaçınmak için aşağıdakileri tutarlı bir şekilde yapın:

• char *m_DataAyrılan hafızayı takip etmek için kullanın (olduğu gibi saklayabilirsiniz T *m_Data, ancak asla delete[] m_Datadoğrudan aramamaya dikkat etmelisiniz )
• newVektöre gerçek öğeler eklerken her zaman yerleşimi kullan
• Vektörden gerçek öğeleri silerken her zaman "yerleşim delete" kullan

Ayrıca, ideal olarak, std::movesırasında öğeleri istersiniz resize(), ancak bu zordur, özellikle de Thareket yapıcısı istisnalar atabilirse.

Dan uzaklaşma std::vector

Yorumlarda daha önce tartışıldığı gibi, vektör sınıfınız biraz farklıdır std::vector. Bu, görevin gerekliliklerinden kaynaklanmaktadır. Sınıf ödevlerinin dışında, kullanamayacağınız std::vector, ancak bunu kendiniz uygulamanız gereken gerçek senaryolar da vardır . Bu durumda std::vector, kendi sınıfınızın yerine geçmesini sağlamak için arayüzü olabildiğince aynı tutmak istersiniz ve sürprizler olmaz.

Oluşturucu alan ayırmaya karşı öğeler ayırma

Bir size_tbağımsız değişken alan kurucunuz, onu alan ayırmak için kullanır, ancak vektöre herhangi bir öğe eklemez. Ancak, gelen ilgili kurucu std::vector, varsayılan olarak başlatılmış gerçek öğeleri tahsis etmek için bağımsız değişkeni kullanır. Ayrıca, sınıfınızla:

Vector<int> v(4, 2);

Bu, yalnızca başlatılmamış iki öğe için alan m_Sizeayırır ve 4'e ayarlanır, boyutları birbiriyle tutarsız hale getirir ve sonraki bir çağrının operator[]()bir hata atmadan sınırların dışına çıkmasına izin verir . Bunu şununla karşılaştırın:

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

Bu, tümü değere göre başlatılan 4 öğeden oluşan bir vektör tahsis eder 2. Yani oldukça farklı bir davranış.

size_tSayaçlar için kullanın

Bir başlatıcı listesi alan yapıcıda kullanırsınız int cnt, ancak intyeterince büyük olmayabilir. size_tBoyutlar, sayılar ve endeksler için tutarlı bir şekilde kullanın .

Üye başlatıcı listesinde bellek ayırabilirsiniz

Üye başlatıcı listesinde, bellek ayırma gibi yan etkilere sahip olanlar da dahil olmak üzere daha karmaşık ifadelere sahip olabileceğinizi unutmayın. Böylece yazabilirsiniz:

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

Bu durumda gerçekten önemli değil, ancak bazı durumlarda faydalar olduğu için bunu yapmak iyi bir uygulamadır .

Uygun bir istisna türü kullanarak atın

Yapma throwrastgele dizeleri, ancak istisna için uygun bir türü kullanabilirsiniz. Standart kitaplığı kullanacaksanız, örneğin aşağıdakilerden uygun bir tür seçin :

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

Standart kitaplığı kullanamıyorsanız, en azından kendi istisna türünüzü tanımlayın, böylece bir arayan belirli yakalama bloklarını kullanabilir. Örneğin, aşağıdakileri yapmak isteyebileceğinizi düşünün:

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
}

Yalnızca bir dizge atarsanız, yalnızca bir catchblokunuz olabilir, bu durumda neler olup bittiğini anlamak için dizeyi ayrıştırmanız gerekir.

Sınır kontrolü yapmamayı düşünün operator[]()

Standart kitaplık, operator[]()performans üzerinde önemli bir etkiye sahip olduğu için kullanım sırasında sınır kontrolleri yapmaz . at()Sınır kontrolü yapan ayrı bir fonksiyon vardır .

Vector<T>İçine yazmaya gerek yokVector

Sınıf tanımının içine yazmak zorunda değilsiniz Vector<T>, sadece yazın Vector.

Eksik yineleyiciler

Sınıfınız yineleyiciler uygulamıyor, bu nedenle şöyle bir şey yazamazsınız:

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

Sınıfınız için yineleyiciler uygulamaya çalışmak iyi bir egzersizdir.