Реализация класса 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) * ...]а затем используете размещение new для копирования старых элементов. Первый безопасен, но потенциально вызывает больше конструкторов, чем ожидалось, второй имеет проблему, заключающуюся в том, что у вас может быть неиспользованная емкость, которая никогда не была должным образом инициализирована, но когда вы 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аргумент, использует его для резервирования места, но не добавляет никаких элементов в вектор. Однако соответствующий конструктор from std::vectorиспользует аргумент для выделения фактических элементов, которые инициализируются по умолчанию. Также с вашим классом:

Vector<int> v(4, 2);

При этом выделяется место только для двух элементов, которые не инициализированы, и устанавливается m_Sizeзначение 4, что делает размеры несовместимыми друг с другом и позволяет последующему вызову operator[]()считываться за пределы без возникновения ошибки. Сравните это с:

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

Это выделяет вектор из 4 элементов, которые все инициализируются значением 2. Так что совсем другое поведение.

Используйте size_tдля прилавков

В конструкторе, который принимает список инициализаторов, вы используете 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. Например, подумайте, что вы можете сделать следующее:

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-block, который затем должен проанализировать строку, чтобы выяснить, что происходит.

Подумайте о том, чтобы не выполнять проверку границ operator[]()

Стандартная библиотека не выполняет проверки границ при использовании operator[](), так как это оказывает значительное влияние на производительность. Есть отдельная функция at(), которая проверяет границы.

Не нужно писать Vector<T>внутриVector

Внутри определения класса писать не нужно Vector<T>, просто напишите Vector.

Отсутствующие итераторы

Ваш класс не реализует итераторы, поэтому вы не можете написать что-то вроде:

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

Это хорошее упражнение - попытаться реализовать итераторы для вашего класса.