Estrutura e Variáveis de Membro

Para simular o funcionamento do std::vector, utilizamos a alocação dinâmica de memória no heap. A estrutura base baseia-se em três ponteiros fundamentais que gerenciam o intervalo de dados e a capacidade total alocada.

template <typename T>
class MyVector {
public:
    typedef T* iterator;
    typedef const T* const_iterator;

private:
    iterator _base = nullptr;          // Início do array
    iterator _top = nullptr;           // Fim dos dados válidos (size)
    iterator _capacity_limit = nullptr; // Fim do espaço alocado (capacity)
};

Gerenciamento de Iteradores

Os iteradores em um vector simplificado são ponteiros diretos para os elementos. As funções begin e end delimitam o intervalo de elementos ativos.

iterator begin() { return _base; }
iterator end() { return _top; }

const_iterator begin() const { return _base; }
const_iterator end() const { return _top; }

Capacidade e Acesso a Elementos

O tamenho (size) é a distância entre o topo e a base, enquanto a capacidade é a distância total entre o limite da memória e a base. O acesso via índice utiliza a sobrecarga do operador de colchetes com validação de limites.

size_t size() const { return _top - _base; }
size_t capacity() const { return _capacity_limit - _base; }

T& operator[](size_t index) {
    assert(index < size());
    return *(_base + index);
}

const T& operator[](size_t index) const {
    assert(index < size());
    return *(_base + index);
}

Realocação de Memória (Reserve)

A função reserve é crucial para evitar múltiplas alocações. É necessário realizar uma cópia profunda dos elementos existentes para o novo bloco de memória, garanitndo que objetos complexos (como std::string) não sofram problemas de cópia rasa (shallow copy).

void reserve(size_t new_cap) {
    if (new_cap > capacity()) {
        size_t current_size = size();
        T* new_data = new T[new_cap];

        if (_base) {
            // Cópia profunda via atribuição para evitar problemas com tipos complexos
            for (size_t i = 0; i < current_size; ++i) {
                new_data[i] = _base[i];
            }
            delete[] _base;
        }

        _base = new_data;
        _top = _base + current_size;
        _capacity_limit = _base + new_cap;
    }
}

Inserção e Remoção de Elementos

Ao inserir elementos, devemos estar atentos à "invalidação de iteradores". Se houver realocação, o ponteiro original torna-se inválido, exigindo o cálculo do deslocamento relativo.

iterator insert(iterator pos, const T& val) {
    assert(pos >= _base && pos <= _top);

    if (_top == _capacity_limit) {
        size_t offset = pos - _base;
        size_t next_cap = capacity() == 0 ? 4 : capacity() * 2;
        reserve(next_cap);
        pos = _base + offset;
    }

    iterator cursor = _top;
    while (cursor > pos) {
        *cursor = *(cursor - 1);
        --cursor;
    }

    *pos = val;
    ++_top;
    return pos;
}

void push_back(const T& val) {
    insert(end(), val);
}

iterator erase(iterator pos) {
    assert(pos >= _base && pos < _top);

    iterator cursor = pos + 1;
    while (cursor != _top) {
        *(cursor - 1) = *cursor;
        ++cursor;
    }

    --_top;
    return pos;
}

Redimensionamento Dinâmico (Resize)

O resize ajusta o número de elementos. Se o novo tamanho for maior, preenchemos o espaço com valores padrão; se for menor, apenas movemos o ponteiro de controle.

void resize(size_t n, T val = T()) {
    if (n < size()) {
        _top = _base + n;
    } else {
        if (n > capacity()) {
            reserve(n);
        }
        while (size() < n) {
            push_back(val);
        }
    }
}

Construtores e Gerenciamento de Ciclo de Vida

Implementamos o construtor padrão, o preenchimento inicial e o construtor por intervalo de iteradores (template). O destrutor garante a liberação correta da memória heap.

MyVector() = default;

MyVector(size_t n, const T& val = T()) {
    reserve(n);
    for (size_t i = 0; i < n; ++i) {
        push_back(val);
    }
}

template <class InputIterator>
MyVector(InputIterator first, InputIterator last) {
    while (first != last) {
        push_back(*first);
        ++first;
    }
}

~MyVector() {
    if (_base) {
        delete[] _base;
        _base = _top = _capacity_limit = nullptr;
    }
}

Operação de Atribuição e Swap

Utilizamos a técnica de "Copy and Swap" para implementar o operador de atribuição de forma segura e eficeinte.

void swap(MyVector<T>& other) {
    std::swap(_base, other._base);
    std::swap(_top, other._top);
    std::swap(_capacity_limit, other._capacity_limit);
}

MyVector<T>& operator=(MyVector<T> tmp) {
    this->swap(tmp);
    return *this;
}