การปรับใช้คลาส std :: vector

Question

หวังว่าจะได้รับคำติชมของคุณเกี่ยวกับความพยายามในการจำลองฟังก์ชันการทำงานของคลาสเวกเตอร์ โดยเฉพาะอย่างยิ่งฉันมีข้อสงสัยเกี่ยวกับตัวสร้างการคัดลอกและวิธีการปรับขนาด ฉันคิดว่าตัวสร้างการคัดลอกอาจทำให้หน่วยความจำรั่ว แต่ฉันไม่รู้ว่าจะทำให้ดีขึ้นได้อย่างไร ฉันใช้วิธีการปรับขนาดสองวิธีและดูเหมือนว่าทั้งคู่จะใช้งานได้ แต่แบบไหนดีกว่ากัน

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

ขอขอบคุณ.

Answer 1

เกี่ยวกับตัวสร้างสำเนาและ resize()

ในตัวสร้างการคัดลอก (และตัวสร้างอื่น ๆ ด้วย) คุณจะจัดสรรหน่วยความจำโดยใช้new T[...]แต่resize()คุณจะจัดสรรหน่วยความจำด้วยnew char[sizeof(T) * ...]แล้วใช้ตำแหน่งใหม่เพื่อคัดลอกองค์ประกอบเก่า ก่อนหน้านี้ปลอดภัย แต่อาจเรียกตัวสร้างมากกว่าที่คาดไว้ตัวหลังมีปัญหาว่าคุณสามารถมีความจุที่ไม่ได้ใช้งานซึ่งไม่เคยเริ่มต้นอย่างถูกต้อง แต่เมื่อคุณdeleteเรียกใช้ตัวทำลายในองค์ประกอบที่สงวนไว้ทั้งหมด

เพื่อความปลอดภัยและเพื่อหลีกเลี่ยงการเรียกตัวสร้างTสำหรับองค์ประกอบที่สงวนไว้ให้ทำดังต่อไปนี้อย่างสม่ำเสมอ:

• ใช้char *m_Dataเพื่อติดตามหน่วยความจำที่จัดสรร (คุณสามารถเก็บไว้เป็นT *m_Dataแต่คุณต้องระวังอย่าโทรdelete[] m_Dataโดยตรง)
• ใช้ตำแหน่งเสมอnewเมื่อเพิ่มองค์ประกอบจริงลงในเวกเตอร์
• ใช้"ตำแหน่งdelete"เสมอเมื่อลบองค์ประกอบจริงออกจากเวกเตอร์

นอกจากนี้คุณควรต้องการstd::moveองค์ประกอบในระหว่างresize()แต่นั่นเป็นเรื่องยุ่งยากโดยเฉพาะอย่างยิ่งหากTตัวสร้างการเคลื่อนไหวสามารถโยนข้อยกเว้นได้

ความแตกต่างจาก std::vector

std::vectorดังที่ได้กล่าวไปแล้วในความคิดเห็นที่ระดับเวกเตอร์ของคุณจะแตกต่างกันเล็กน้อยจาก นี่เป็นเพราะข้อกำหนดของการมอบหมายงาน นอกจากการมอบหมายชั้นเรียนแล้วยังมีสถานการณ์จริงที่คุณไม่สามารถใช้ได้std::vectorแต่คุณต้องนำไปใช้ด้วยตัวเอง ในกรณีนี้คุณต้องการให้อินเทอร์เฟซเหมือนเดิมมากที่สุดเท่าที่จะเป็นไปได้std::vectorเพื่อให้แน่ใจว่าคลาสของคุณเป็นของทดแทนแบบดร็อปอินและไม่มีเรื่องน่าประหลาดใจ

ตัวสร้างการจองพื้นที่เทียบกับการจัดสรรองค์ประกอบ

ตัวสร้างของคุณที่ใช้size_tอาร์กิวเมนต์จะใช้เพื่อจองพื้นที่ แต่ไม่ได้เพิ่มองค์ประกอบใด ๆ ให้กับเวกเตอร์ อย่างไรก็ตามตัวสร้างที่สอดคล้องกันจากstd::vectorใช้อาร์กิวเมนต์เพื่อจัดสรรองค์ประกอบจริงซึ่งเป็นค่าเริ่มต้นเริ่มต้น นอกจากนี้ในชั้นเรียนของคุณ:

Vector<int> v(4, 2);

สิ่งนี้จะจัดสรรพื้นที่เฉพาะสำหรับสององค์ประกอบซึ่งไม่ได้เริ่มต้นและตั้งค่าm_Sizeเป็น 4 ทำให้ขนาดไม่สอดคล้องกันและอนุญาตให้การเรียกครั้งต่อ ๆ ไปoperator[]()อ่านนอกขอบเขตโดยไม่เกิดข้อผิดพลาด ตรงกันข้ามกับ:

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

นี้จัดสรรเวกเตอร์ของธาตุทั้ง 4 2ซึ่งได้รับการเริ่มต้นที่จะคุ้มค่าที่ ดังนั้นพฤติกรรมที่ค่อนข้างแตกต่างกัน

ใช้size_tสำหรับเคาน์เตอร์

ในตัวสร้างที่ใช้รายการ initializer คุณใช้int cntแต่intอาจไม่ใหญ่พอ ใช้size_tอย่างสม่ำเสมอสำหรับขนาดจำนวนและดัชนี

คุณสามารถจัดสรรหน่วยความจำในรายการเริ่มต้นสมาชิก

โปรดทราบว่าคุณสามารถมีนิพจน์ที่ซับซ้อนมากขึ้นในรายการตัวเริ่มต้นของสมาชิกรวมถึงนิพจน์ที่มีผลข้างเคียงเช่นการจัดสรรหน่วยความจำ ดังนั้นคุณสามารถเขียน:

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

มันไม่สำคัญในกรณีนี้ แต่เป็นแนวทางปฏิบัติที่ดีเนื่องจากมีประโยชน์ในบางกรณี

โยนโดยใช้ประเภทข้อยกเว้นที่เหมาะสม

อย่าthrowสุ่มสตริง แต่ใช้ประเภทที่เหมาะสมสำหรับข้อยกเว้น หากคุณจะใช้ไลบรารีมาตรฐานให้เลือกประเภทที่เหมาะสมจากตัวอย่างเช่น:

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

หากคุณไม่สามารถใช้ไลบรารีมาตรฐานอย่างน้อยก็ให้กำหนดประเภทข้อยกเว้นของคุณเองเพื่อให้ผู้โทรใช้ catch-blocks เฉพาะได้ ตัวอย่างเช่นพิจารณาว่าคุณอาจต้องการทำสิ่งต่อไปนี้:

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
}

หากคุณเพียงแค่โยนสตริงคุณสามารถมีได้เพียงcatchบล็อกเดียวซึ่งจะต้องแยกวิเคราะห์สตริงเพื่อดูว่าเกิดอะไรขึ้น

พิจารณาไม่ทำการเช็คอินในขอบเขต operator[]()

ไลบรารีมาตรฐานจะไม่ทำการตรวจสอบขอบเขตเมื่อใช้operator[]()เนื่องจากมีผลกระทบอย่างมากต่อประสิทธิภาพ มีฟังก์ชันแยกต่างหากat()ที่ทำหน้าที่ตรวจสอบขอบเขต

ไม่ต้องเขียนVector<T>ข้างในVector

ภายในกำหนดระดับที่คุณไม่จำเป็นต้องเขียนเพียงแค่เขียนVector<T>Vector

ไม่มีตัวทำซ้ำ

ชั้นเรียนของคุณไม่ได้ใช้ตัววนซ้ำดังนั้นคุณจึงไม่สามารถเขียนบางสิ่งเช่น:

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

เป็นการออกกำลังกายที่ดีที่จะพยายามใช้ตัววนซ้ำสำหรับชั้นเรียนของคุณ