Implementasi kelas std :: vector

Question

Menantikan tanggapan Anda tentang upaya saya untuk mereplikasi fungsionalitas kelas vektor. Terutama saya ragu tentang menyalin konstruktor dan metode pengubahan ukuran. Saya pikir konstruktor salinan berpotensi menyebabkan kebocoran memori, tetapi saya tidak tahu cara membuatnya lebih baik. Saya menerapkan dua metode pengubahan ukuran dan keduanya tampaknya berfungsi, tetapi mana yang sebenarnya lebih baik?

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

Terima kasih.

Answer 1

Tentang konstruktor salinan dan resize()

Dalam konstruktor salinan (dan konstruktor lainnya juga), Anda mengalokasikan memori menggunakan new T[...], tetapi dalam resize()mengalokasikan memori dengan new char[sizeof(T) * ...]dan kemudian menggunakan penempatan baru untuk menyalin elemen lama. Yang pertama aman, tetapi berpotensi memanggil lebih banyak konstruktor daripada yang diharapkan, yang terakhir memiliki masalah bahwa Anda dapat memiliki kapasitas yang tidak digunakan yang tidak pernah diinisialisasi dengan benar, tetapi jika Anda deletemelakukannya, Anda akan memanggil destruktor pada semua elemen yang dicadangkan.

Agar aman dan menghindari pemanggilan konstruktor Tuntuk elemen yang dicadangkan, lakukan hal berikut secara konsisten:

• Gunakan char *m_Datauntuk melacak memori yang dialokasikan (Anda dapat menyimpannya sebagai T *m_Data, tetapi Anda harus berhati-hati untuk tidak pernah menelepon delete[] m_Datasecara langsung)
• Selalu gunakan penempatan newsaat menambahkan elemen aktual ke vektor
• Selalu gunakan "penempatan delete" saat menghapus elemen sebenarnya dari vektor

Juga, idealnya Anda ingin std::moveelemen selama resize(), tetapi itu rumit, terutama jika Tkonstruktor bergerak dapat membuang pengecualian.

Perbedaan dari std::vector

Seperti yang sudah dibahas di komentar, kelas vektor Anda sedikit berbeda dari std::vector. Ini karena persyaratan penugasan. Di luar tugas kelas, ada juga skenario nyata yang tidak dapat Anda gunakan std::vector, tetapi Anda harus menerapkannya sendiri. Dalam hal ini Anda ingin menjaga antarmuka sebanyak mungkin std::vector, untuk memastikan kelas Anda sendiri adalah pengganti drop-in, dan tidak ada kejutan.

Konstruktor memesan ruang vs. mengalokasikan elemen

Konstruktor Anda yang size_tmenggunakan argumen menggunakannya untuk memesan ruang, tetapi tidak menambahkan elemen apa pun ke vektor. Namun, konstruktor terkait dari std::vectormenggunakan argumen untuk mengalokasikan elemen aktual yang diinisialisasi default. Juga, dengan kelas Anda:

Vector<int> v(4, 2);

Ini hanya mengalokasikan ruang untuk dua elemen, yang tidak diinisialisasi, dan disetel m_Sizeke 4, membuat ukuran tidak konsisten satu sama lain, dan memungkinkan panggilan berikutnya untuk operator[]()membaca di luar batas tanpa menimbulkan kesalahan. Bandingkan ini dengan:

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

Ini mengalokasikan vektor dari 4 elemen yang semuanya diinisialisasi ke nilai 2. Jadi perilaku yang sangat berbeda.

Gunakan size_tuntuk penghitung

Dalam konstruktor yang mengambil daftar penginisialisasi, Anda menggunakan int cnt, tetapi intmungkin tidak cukup besar. Gunakan size_tsecara konsisten untuk ukuran, hitungan, dan indeks.

Anda dapat mengalokasikan memori dalam daftar penginisialisasi anggota

Perhatikan bahwa Anda dapat memiliki ekspresi yang lebih kompleks dalam daftar penginisialisasi anggota, termasuk ekspresi yang memiliki efek samping seperti mengalokasikan memori. Jadi Anda bisa menulis:

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

Tidak terlalu penting dalam kasus ini, tetapi praktik yang baik untuk melakukan ini, karena ada manfaatnya dalam beberapa kasus.

Lempar menggunakan jenis pengecualian yang tepat

Jangan membuat throwstring acak, tetapi gunakan jenis yang tepat untuk pengecualian. Jika Anda akan menggunakan pustaka standar, pilih jenis yang sesuai dari , misalnya:

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

Jika Anda tidak dapat menggunakan pustaka standar, setidaknya tentukan jenis pengecualian Anda sendiri, sehingga pemanggil dapat menggunakan blok-tangkap tertentu. Misalnya, pertimbangkan bahwa Anda mungkin ingin melakukan hal berikut:

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
}

Jika Anda hanya melempar string, Anda hanya dapat memiliki satu catch-block, yang kemudian harus mengurai string untuk mencari tahu apa yang sedang terjadi.

Pertimbangkan untuk tidak melakukan check-in batas operator[]()

Pustaka standar tidak melakukan pemeriksaan batas saat menggunakan operator[](), karena ini berdampak signifikan pada kinerja. Ada fungsi terpisah at(),, yang melakukan pemeriksaan batas.

Tidak perlu menulis Vector<T>di dalamVector

Di dalam definisi kelas Anda tidak perlu menulis Vector<T>, cukup tulis Vector.

Iterator hilang

Kelas Anda tidak mengimplementasikan iterator, jadi Anda tidak dapat menulis sesuatu seperti:

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

Ini adalah latihan yang bagus untuk mencoba mengimplementasikan iterator untuk kelas Anda.