Реализуйте класс vector с операциями: push_back, push_front, pop_back, pop_front, size, clear

Задача

Реализуйте упрощённый Vector<T> с операциями push_back, push_front, pop_back, pop_front, size, operator[], clear. Используйте правило пяти.

Решение

#include <cstddef>
#include <stdexcept>
#include <utility>
#include <cassert>

template<typename T>
class Vector {
public:
    Vector() = default;

    ~Vector() {
        clear();
        ::operator delete(data_);
    }

    // Rule of Five
    Vector(const Vector& o) : Vector() {
        reserve(o.size_);
        for (size_t i = 0; i < o.size_; ++i) push_back(o.data_[i]);
    }

    Vector& operator=(Vector o) {   // copy-and-swap
        swap(o);
        return *this;
    }

    Vector(Vector&& o) noexcept { swap(o); }

    void push_back(const T& val) {
        ensureCapacity();
        new (data_ + size_) T(val);
        ++size_;
    }

    void push_front(const T& val) {  // O(n)
        ensureCapacity();
        // shift right
        if (size_ > 0) {
            new (data_ + size_) T(std::move(data_[size_ - 1]));
            for (size_t i = size_ - 1; i > 0; --i)
                data_[i] = std::move(data_[i - 1]);
            data_[0].~T();
        }
        new (data_) T(val);
        ++size_;
    }

    void pop_back() {
        if (size_ == 0) throw std::underflow_error("pop_back on empty");
        data_[--size_].~T();
    }

    void pop_front() {  // O(n)
        if (size_ == 0) throw std::underflow_error("pop_front on empty");
        data_[0].~T();
        for (size_t i = 0; i + 1 < size_; ++i)
            new (data_ + i) T(std::move(data_[i + 1]));
        data_[size_ - 1].~T();
        --size_;
    }

    T& operator[](size_t i) { return data_[i]; }

    void clear() {
        for (size_t i = 0; i < size_; ++i) data_[i].~T();
        size_ = 0;
    }

    size_t size()     const { return size_; }
    size_t capacity() const { return cap_; }
    bool   empty()    const { return size_ == 0; }

private:
    void reserve(size_t newCap) {
        if (newCap <= cap_) return;
        T* newData = static_cast<T*>(::operator new(newCap * sizeof(T)));
        for (size_t i = 0; i < size_; ++i) {
            new (newData + i) T(std::move(data_[i]));
            data_[i].~T();
        }
        ::operator delete(data_);
        data_ = newData;
        cap_  = newCap;
    }

    void ensureCapacity() {
        if (size_ == cap_) reserve(cap_ ? cap_ * 2 : 4);
    }

    void swap(Vector& o) noexcept {
        std::swap(data_, o.data_);
        std::swap(size_, o.size_);
        std::swap(cap_,  o.cap_);
    }

    T*     data_ = nullptr;
    size_t size_ = 0;
    size_t cap_  = 0;
};

int main() {
    Vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    assert(v.size() == 3 && v[0] == 1 && v[2] == 3);

    v.push_front(0);
    assert(v.size() == 4 && v[0] == 0 && v[1] == 1);

    v.pop_back();
    assert(v.size() == 3 && v[2] == 2);

    v.pop_front();
    assert(v.size() == 2 && v[0] == 1);

    v.clear();
    assert(v.empty());
}

Ключевые моменты

• push_front и pop_front — O(n) для вектора; если нужен O(1), используйте std::deque.
• Сырая память + placement new позволяют избежать ненужной инициализации элементов.
• Копирование реализовано через copy-and-swap для исключительной безопасности.
• Удвоение вместимости при росте гарантирует амортизированное O(1) для push_back.