СПРИНТ № 8 | Эффективные линейные контейнеры | Урок 10: Разработка контейнера SimpleVector 2

simple_vector.h

#pragma once

#include <cassert>
#include <initializer_list>
#include <vector>
#include <exception>
#include <algorithm>
#include <iostream>
#include "array_ptr.h"

template <typename Type>
class SimpleVector {
public:
    using Iterator = Type*;
    using ConstIterator = const Type*;

    SimpleVector() noexcept = default;

    // Создаёт вектор из size элементов, инициализированных значением по умолчанию
    explicit SimpleVector(size_t size) : size_(size), capacity_(size), ptr_(size) {
        std::fill(begin(), end(), 0);
    }

    // Создаёт вектор из size элементов, инициализированных значением value
    SimpleVector(size_t size, const Type& value) : size_(size), capacity_(size), ptr_(size) {
        std::fill(begin(), end(), value);
    }

    // Создаёт вектор из std::initializer_list
    SimpleVector(std::initializer_list<Type> init) : size_(init.size()), capacity_(init.size()), ptr_(init.size())
    {
        size_t b = 0;
        for (const auto& i : init)
        {
            ptr_[b] = i;
            ++b;
        }
    }

    SimpleVector(const SimpleVector& other): size_(other.size_), capacity_(other.capacity_), ptr_(other.size_){
        std::copy(other.begin(), other.end(), begin());
    }

    SimpleVector& operator=(const SimpleVector& rhs) {
        SimpleVector copy{ rhs };
        swap(copy);
        return *this;
    }


    ~SimpleVector() {}

    // Возвращает количество элементов в массиве
    size_t GetSize() const noexcept {
        return size_;
    }

    // Возвращает вместимость массива
    size_t GetCapacity() const noexcept {
        return capacity_;
    }

    // Сообщает, пустой ли массив
    bool IsEmpty() const noexcept {
        return size_ == 0;
    }

    // Возвращает ссылку на элемент с индексом index
    Type& operator[](size_t index) noexcept {
        return ptr_[index];
    }

    // Возвращает константную ссылку на элемент с индексом index
    const Type& operator[](size_t index) const noexcept {

        return ptr_[index];
    }

    // Возвращает константную ссылку на элемент с индексом index
    // Выбрасывает исключение std::out_of_range, если index >= size
    Type& At(size_t index) {
        if (index >= size_)
            throw std::out_of_range("out of range");
        return ptr_[index];
    }

    // Возвращает константную ссылку на элемент с индексом index
    // Выбрасывает исключение std::out_of_range, если index >= size
    const Type& At(size_t index) const {
        if (index > size_)
            throw std::out_of_range("out of range");
        return ptr_[index];
    }

    // Обнуляет размер массива, не изменяя его вместимость
    void Clear() noexcept {
        size_ = 0;
    }

    // Изменяет размер массива.
    // При увеличении размера новые элементы получают значение по умолчанию для типа Type
    void Resize(size_t new_size) {
        if (new_size > capacity_) {
            auto new_array = ArrayPtr<Type>(new_size);
            for (size_t i = 0; i < size_; ++i) {
                new_array[i] = ptr_[i];
            }
            ptr_.swap(new_array);
            capacity_ = new_size;
        }
        for (size_t i = size_; i < new_size; ++i) {
            ptr_[i] = Type();
        }
        size_ = new_size;
    }

    // Возвращает итератор на начало массива
    // Для пустого массива может быть равен (или не равен) nullptr
    Iterator begin() noexcept {
        return ptr_.Get();
        // Напишите тело самостоятельно
    }

    // Возвращает итератор на элемент, следующий за последним
    // Для пустого массива может быть равен (или не равен) nullptr
    Iterator end() noexcept {
        return ptr_.Get() + size_;
    }

    // Возвращает константный итератор на начало массива
    // Для пустого массива может быть равен (или не равен) nullptr
    ConstIterator begin() const noexcept {
        return ptr_.Get();
    }

    // Возвращает итератор на элемент, следующий за последним
    // Для пустого массива может быть равен (или не равен) nullptr
    ConstIterator end() const noexcept {
        return ptr_.Get() + size_;
    }

    // Возвращает константный итератор на начало массива
    // Для пустого массива может быть равен (или не равен) nullptr
    ConstIterator cbegin() const noexcept {
        return ptr_.Get();
    }

    // Возвращает итератор на элемент, следующий за последним
    // Для пустого массива может быть равен (или не равен) nullptr
    ConstIterator cend() const noexcept {
        return ptr_.Get() + size_;
    }

    // Добавляет элемент в конец вектора
    // При нехватке места увеличивает вдвое вместимость вектора
    void PushBack(const Type& item) {
       if(size_ == capacity_)
       {
            auto new_capacity = (capacity_ == 0) ? 1 : capacity_ * 2;
            auto new_vector = ArrayPtr<Type>(new_capacity);
            for (size_t i = 0; i < size_; ++i)
            {
                new_vector[i] = ptr_[i];
            }
            ptr_.swap(new_vector);
            capacity_ = new_capacity;
       }
       ptr_[size_] = item;
       ++size_;
    }

    // Вставляет значение value в позицию pos.
    // Возвращает итератор на вставленное значение
    // Если перед вставкой значения вектор был заполнен полностью,
    // вместимость вектора должна увеличиться вдвое, а для вектора вместимостью 0 стать равной 1
    Iterator Insert(ConstIterator pos, const Type& value) {
        size_t index = pos - begin();
        if(index > capacity_)
        {
            std::out_of_range("exit of out_of_range");
        }
        if(size_ == capacity_)
        {
            auto new_capacity = (capacity_ == 0) ? 1 : capacity_ * 2;
            auto new_vector = ArrayPtr<Type>(new_capacity);
            std::copy(begin(), begin()+index, new_vector.Get());
            new_vector[index] = value;
            std::copy(begin()+index, end(), new_vector.Get()+index+1);
            ptr_.swap(new_vector);
            capacity_ = new_capacity;
        }
        else{
            std::copy_backward(begin()+index, end(), end()+1);
            ptr_[index] = value;
        }
        ++size_;
        return Iterator(ptr_.Get() + index);
    }

    // "Удаляет" последний элемент вектора. Вектор не должен быть пустым
    void PopBack() noexcept {
        if(size_) --size_;
    }

    // Удаляет элемент вектора в указанной позиции
    Iterator Erase(ConstIterator pos) {
        auto index = pos-begin();

        if(size_)
        {
            auto new_vector = ArrayPtr<Type>(capacity_);
            std::copy(begin(), begin()+index, new_vector.Get());

            std::copy(begin() + index+1, end(), new_vector.Get()+index);
            --size_;
            ptr_.swap(new_vector);
        }
        return Iterator(begin() + index);
    }

    // Обменивает значение с другим вектором
    void swap(SimpleVector& other) noexcept {
        std::swap(size_, other.size_);
        std::swap(capacity_, other.capacity_);
        ptr_.swap(other.ptr_);
    }
private:
    size_t size_ = 0;
    size_t capacity_ = 0;
    ArrayPtr<Type> ptr_;
};

template <typename Type>
inline bool operator==(const SimpleVector<Type>& lhs, const SimpleVector<Type>& rhs) {
    return std::equal(lhs.begin(), lhs.end(), rhs.begin());
}

template <typename Type>
inline bool operator!=(const SimpleVector<Type>& lhs, const SimpleVector<Type>& rhs) {
    return !(rhs==lhs);
}

template <typename Type>
inline bool operator<(const SimpleVector<Type>& lhs, const SimpleVector<Type>& rhs) {
    return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());

}

template <typename Type>
inline bool operator<=(const SimpleVector<Type>& lhs, const SimpleVector<Type>& rhs) {
    // Заглушка. Напишите тело самостоятельно
    return (lhs<rhs) || (lhs==rhs);
}

template <typename Type>
inline bool operator>(const SimpleVector<Type>& lhs, const SimpleVector<Type>& rhs) {
    return std::lexicographical_compare(rhs.begin(), rhs.end(), lhs.begin(), lhs.end());
}

template <typename Type>
inline bool operator>=(const SimpleVector<Type>& lhs, const SimpleVector<Type>& rhs) {
    // Заглушка. Напишите тело самостоятельно
    return (lhs>rhs) || (lhs==rhs);
}

=======================================================================================================================================

array_ptr.h

#include <cassert>
#include <cstdlib>

template <typename Type>
class ArrayPtr {
public:
    ArrayPtr() = default;

    explicit ArrayPtr(size_t size) {
        (size == 0) ? raw_ptr_ = nullptr : raw_ptr_ = new Type[size];
    }

    explicit ArrayPtr(Type* raw_ptr) noexcept {
        if (raw_ptr) raw_ptr_ = raw_ptr;
    }

    ArrayPtr(const ArrayPtr&) = delete;

    ~ArrayPtr() {
        delete[] raw_ptr_;
    }

    ArrayPtr& operator=(const ArrayPtr&) = delete;

    [[nodiscard]] Type* Release() noexcept {
        Type* currentarr = raw_ptr_;
        raw_ptr_ = nullptr;
        return currentarr;
    }

    Type& operator[](size_t index) noexcept {
        return raw_ptr_[index];
    }

    const Type& operator[](size_t index) const noexcept {
        return raw_ptr_[index];
    }

    explicit operator bool() const {
        return (raw_ptr_) ? true : false;
    }

    Type* Get() const noexcept {
        return raw_ptr_;
    }

    void swap(ArrayPtr& other) noexcept {
        Type* temp = other.raw_ptr_;
        other.raw_ptr_ = raw_ptr_;
        raw_ptr_ = temp;
    }

private:
    Type* raw_ptr_ = nullptr;
};

=======================================================================================================================================

tests.h

#pragma once
#include <cassert>
#include <stdexcept>
#include "simple_vector.h"

inline void Test1() {
   // Инициализация конструктором по умолчанию
   {
       SimpleVector<int> v;
       assert(v.GetSize() == 0u);
       assert(v.IsEmpty());
       assert(v.GetCapacity() == 0u);
   }

   // Инициализация вектора указанного размера
   {
       SimpleVector<int> v(5);
       assert(v.GetSize() == 5u);
       assert(v.GetCapacity() == 5u);
       assert(!v.IsEmpty());
       for (size_t i = 0; i < v.GetSize(); ++i) {
           assert(v[i] == 0);
       }
   }

   // Инициализация вектора, заполненного заданным значением
   {
       SimpleVector<int> v(3, 42);
       assert(v.GetSize() == 3);
       assert(v.GetCapacity() == 3);
       for (size_t i = 0; i < v.GetSize(); ++i) {
           assert(v[i] == 42);
       }
   }

   // Инициализация вектора при помощи initializer_list
   {
       SimpleVector<int> v{ 1, 2, 3 };
       assert(v.GetSize() == 3);
       assert(v.GetCapacity() == 3);
       assert(v[2] == 3);
   }

   // Доступ к элементам при помощи At
   {
       SimpleVector<int> v(3);
       assert(&v.At(2) == &v[2]);
       try {
           v.At(3);
           assert(false);  // Ожидается выбрасывание исключения
       }
       catch (const std::out_of_range&) {
       }
       catch (...) {
           assert(false);  // Не ожидается исключение, отличное от out_of_range
       }
   }

   // Очистка вектора
   {
       SimpleVector<int> v(10);
       const size_t old_capacity = v.GetCapacity();
       v.Clear();
       assert(v.GetSize() == 0);
       assert(v.GetCapacity() == old_capacity);
   }

   // Изменение размера
   {
       SimpleVector<int> v(3);
       v[2] = 17;
       v.Resize(7);
       assert(v.GetSize() == 7);
       assert(v.GetCapacity() >= v.GetSize());
       assert(v[2] == 17);
       assert(v[3] == 0);
   }
   {
       SimpleVector<int> v(3);
       v[0] = 42;
       v[1] = 55;
       const size_t old_capacity = v.GetCapacity();
       v.Resize(2);
       assert(v.GetSize() == 2);
       assert(v.GetCapacity() == old_capacity);
       assert(v[0] == 42);
       assert(v[1] == 55);
   }
   {
       const size_t old_size = 3;
       SimpleVector<int> v(3);
       v.Resize(old_size + 5);
       v[3] = 42;
       v.Resize(old_size);
       v.Resize(old_size + 2);
       assert(v[3] == 0);
   }

   // Итерирование по SimpleVector
   {
       // Пустой вектор
       {
           SimpleVector<int> v;
           assert(v.begin() == nullptr);
           assert(v.end() == nullptr);
       }

       // Непустой вектор
       {
           SimpleVector<int> v(10, 42);
           assert(v.begin());
           assert(*v.begin() == 42);
           assert(v.end() == v.begin() + v.GetSize());
       }
   }
}

inline void Test2() {
   // PushBack
   {
       SimpleVector<int> v(1);
       v.PushBack(42);
       assert(v.GetSize() == 2);
       assert(v.GetCapacity() >= v.GetSize());
       assert(v[0] == 0);
       assert(v[1] == 42);
   }

   // Если хватает места, PushBack не увеличивает Capacity
   {
       SimpleVector<int> v(2);
       v.Resize(1);
       const size_t old_capacity = v.GetCapacity();
       v.PushBack(123);
       assert(v.GetSize() == 2);
       assert(v.GetCapacity() == old_capacity);
   }

   // PopBack
   {
       SimpleVector<int> v{ 0, 1, 2, 3 };
       const size_t old_capacity = v.GetCapacity();
       const auto old_begin = v.begin();
       v.PopBack();
       assert(v.GetCapacity() == old_capacity);
       assert(v.begin() == old_begin);
       assert((v == SimpleVector<int>{0, 1, 2}));
   }

   // Конструктор копирования
   {
       SimpleVector<int> numbers{ 1, 2 };
       auto numbers_copy(numbers);
       assert(&numbers_copy[0] != &numbers[0]);
       assert(numbers_copy.GetSize() == numbers.GetSize());
       for (size_t i = 0; i < numbers.GetSize(); ++i) {
           assert(numbers_copy[i] == numbers[i]);
           assert(&numbers_copy[i] != &numbers[i]);
       }
   }

   // Сравнение
   {
       assert((SimpleVector{ 1, 2, 3 } == SimpleVector{ 1, 2, 3 }));
       assert((SimpleVector{ 1, 2, 3 } != SimpleVector{ 1, 2, 2 }));

       assert((SimpleVector{ 1, 2, 3 } < SimpleVector{ 1, 2, 3, 1 }));
       assert((SimpleVector{ 1, 2, 3 } > SimpleVector{ 1, 2, 2, 1 }));

       assert((SimpleVector{ 1, 2, 3 } >= SimpleVector{ 1, 2, 3 }));
       assert((SimpleVector{ 1, 2, 4 } >= SimpleVector{ 1, 2, 3 }));
       assert((SimpleVector{ 1, 2, 3 } <= SimpleVector{ 1, 2, 3 }));
       assert((SimpleVector{ 1, 2, 3 } <= SimpleVector{ 1, 2, 4 }));
    }

   // Обмен значений векторов
   {
       SimpleVector<int> v1{ 42, 666 };
       SimpleVector<int> v2;
       v2.PushBack(0);
       v2.PushBack(1);
       v2.PushBack(2);
       const int* const begin1 = &v1[0];
       const int* const begin2 = &v2[0];

       const size_t capacity1 = v1.GetCapacity();
       const size_t capacity2 = v2.GetCapacity();

       const size_t size1 = v1.GetSize();
       const size_t size2 = v2.GetSize();

       static_assert(noexcept(v1.swap(v2)));
       v1.swap(v2);
       assert(&v2[0] == begin1);
       assert(&v1[0] == begin2);
       assert(v1.GetSize() == size2);
       assert(v2.GetSize() == size1);
       assert(v1.GetCapacity() == capacity2);
       assert(v2.GetCapacity() == capacity1);
   }

   // Присваивание
   {
       SimpleVector<int> src_vector{ 1, 2, 3, 4 };
       SimpleVector<int> dst_vector{ 1, 2, 3, 4, 5, 6 };
       dst_vector = src_vector;
       assert(dst_vector == src_vector);
   }

   // Вставка элементов
   {
       SimpleVector<int> v{ 1, 2, 3, 4 };
       v.Insert(v.begin() + 2, 42);
       assert((v == SimpleVector<int>{1, 2, 42, 3, 4}));
   }


   // Удаление элементов
   {
       SimpleVector<int> v{ 1, 2, 3, 4 };
       v.Erase(v.cbegin() + 2);
       assert((v == SimpleVector<int>{1, 2, 4}));
   }

}