Triển khai lớp vector std ::

Question

Mong nhận được phản hồi của bạn về nỗ lực tái tạo chức năng lớp vectơ của tôi. Đặc biệt là tôi có nghi ngờ về phương thức tạo bản sao và thay đổi kích thước. Tôi nghĩ rằng hàm tạo bản sao đó có thể gây rò rỉ bộ nhớ, nhưng tôi không biết làm thế nào để làm cho nó tốt hơn. Tôi đã thực hiện hai phương pháp thay đổi kích thước và cả hai đều có vẻ hoạt động, nhưng thực sự thì phương pháp nào tốt hơn?

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

Cảm ơn bạn.

Answer 1

Giới thiệu về hàm tạo bản sao và resize()

Trong hàm tạo sao chép (và cả các hàm tạo khác), bạn cấp phát bộ nhớ bằng cách sử dụng new T[...], nhưng trong resize()bạn cấp phát bộ nhớ bằng new char[sizeof(T) * ...]và sau đó sử dụng vị trí mới để sao chép các phần tử cũ. Cái trước là an toàn, nhưng có khả năng gọi nhiều hàm tạo hơn mong đợi, cái sau có vấn đề là bạn có thể có dung lượng chưa sử dụng chưa bao giờ được khởi tạo đúng cách, nhưng khi bạn deletegọi nó, bạn sẽ gọi hàm hủy trên tất cả các phần tử dành riêng.

Để an toàn và tránh gọi hàm tạo của Tcho các phần tử dành riêng, hãy làm như sau một cách nhất quán:

• Sử dụng char *m_Datađể theo dõi bộ nhớ được cấp phát (bạn có thể giữ nguyên T *m_Data, nhưng bạn phải cẩn thận đừng bao giờ gọi delete[] m_Datatrực tiếp)
• Luôn sử dụng vị trí newkhi thêm các phần tử thực tế vào vectơ
• Luôn sử dụng "vị trí delete" khi xóa các phần tử thực tế khỏi vectơ

Ngoài ra, lý tưởng là bạn muốn std::movecác phần tử trong suốt resize(), nhưng điều đó rất khó, đặc biệt là nếu hàm tạo Tchuyển động của nếu có thể ném ra các ngoại lệ.

Sự khác biệt từ std::vector

Như đã thảo luận trong các nhận xét, lớp vectơ của bạn hơi khác với std::vector. Điều này là do yêu cầu của nhiệm vụ. Ngoài các bài tập trên lớp, cũng có những tình huống thực tế mà bạn không thể sử dụng std::vector, nhưng bạn phải tự thực hiện nó. Trong trường hợp đó, bạn muốn giữ giao diện giống như của giao diện càng nhiều càng tốt std::vector, để đảm bảo rằng lớp của riêng bạn là một sự thay thế bổ sung và không có gì bất ngờ.

Không gian dành riêng cho khối xây dựng so với cấp phát các phần tử

Hàm tạo của bạn nhận một size_tđối số sử dụng nó để dự trữ không gian, nhưng không thêm bất kỳ phần tử nào vào vectơ. Tuy nhiên, hàm tạo tương ứng từ std::vectorsử dụng đối số để cấp phát các phần tử thực tế được khởi tạo mặc định. Ngoài ra, với lớp học của bạn:

Vector<int> v(4, 2);

Điều này chỉ phân bổ không gian cho hai phần tử, không được khởi tạo và đặt m_Sizethành 4, làm cho các kích thước không đồng nhất với nhau và cho phép cuộc gọi tiếp theo operator[]()đọc vượt quá giới hạn mà không gây ra lỗi. Đối lập điều này với:

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

Điều này phân bổ một vectơ gồm 4 phần tử đều được khởi tạo thành giá trị 2. Vì vậy, một hành vi khá khác nhau.

Sử dụng size_tcho quầy

Trong hàm tạo có danh sách bộ khởi tạo, bạn sử dụng int cnt, nhưng intcó thể không đủ lớn. Sử dụng size_tnhất quán cho các kích thước, số lượng và chỉ số.

Bạn có thể cấp phát bộ nhớ trong danh sách bộ khởi tạo thành viên

Chỉ cần lưu ý rằng bạn có thể có nhiều biểu thức phức tạp hơn trong danh sách trình khởi tạo thành viên, bao gồm cả những biểu thức có tác dụng phụ như cấp phát bộ nhớ. Vì vậy, bạn có thể viết:

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

Nó không thực sự quan trọng trong trường hợp này, nhưng thực hành tốt để làm điều này, vì có những lợi ích trong một số trường hợp.

Ném bằng cách sử dụng một loại ngoại lệ thích hợp

Đừng dùng throwchuỗi ngẫu nhiên, nhưng hãy sử dụng một loại thích hợp cho trường hợp ngoại lệ. Nếu bạn đang sử dụng thư viện chuẩn, hãy chọn một loại phù hợp , ví dụ:

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

Nếu bạn không thể sử dụng thư viện chuẩn, thì ít nhất hãy xác định kiểu ngoại lệ của riêng bạn, để người gọi có thể sử dụng các khối bắt cụ thể. Ví dụ: hãy xem xét rằng bạn có thể muốn làm như sau:

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
}

Nếu bạn chỉ ném một chuỗi, bạn chỉ có thể có một catch-block, sau đó phải phân tích cú pháp chuỗi để tìm ra điều gì đang xảy ra.

Cân nhắc việc không đăng ký quá giới hạn operator[]()

Thư viện tiêu chuẩn không thực hiện kiểm tra giới hạn khi sử dụng operator[](), vì nó có tác động đáng kể đến hiệu suất. Có một chức năng riêng biệt at(), thực hiện kiểm tra giới hạn.

Không cần viết Vector<T>bên trongVector

Bên trong định nghĩa lớp, bạn không cần phải viết Vector<T>, chỉ cần viết Vector.

Thiếu trình lặp

Lớp của bạn không triển khai các trình vòng lặp, vì vậy bạn không thể viết một cái gì đó như:

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

Đó là một bài tập tốt để cố gắng triển khai các trình vòng lặp cho lớp của bạn.