Собственный vector на c++

Что нужно знать для реализации?

• Указатели

• Move семантика (Дополнительный этап)

• rValue и lValue ссылки (Дополнительный этап)

• Шаблоны

• Итераторы (Дополнительный этап)

• Переопределение операторов

Введение

Я буду использовать c++20. Также эта статья разбита на этапы:

• Первый - третий этапы предназначены для новичков

• Дополнительный этап - для более опытных читателей

Первый этап

Для начала нужно создать шаблонный класс. Для этого используется template

template<typename T>
class Vector {
};

Далее определяем какие поля будет содержать класс:

1. Указатель на область памяти, где будет находиться массив.

2. Размер вектора (size)

3. Максимальный размер вектора (capacity)

С первым и вторым пунктом всё понятно. А для чего нужен третий? Отвечая на этот вопрос, нужно вспомнить, что вектор - это динамический массив. Поэтому, чтобы каждый раз, при добавлении элемента, не выделять новую память, нужно выделить её с запасом.

template<typename T>
class Vector {
private:
    T* arr_;
    size_t size_{};
    size_t capacity_{};
};

Также надо добавить конструктор класса.

template<typename T>
class Vector {
public:
		Vector() {
      	arr_ = new T[1];
      	capacity_ = 1;
    }
private:
    T* arr_;
    size_t size_{};
    size_t capacity_{};
};

Второй этап

Теперь нужно добавить эти методы:

• Метод, который проверяет пустой ли список

• Метод получения размера вектора

• Метод получения максимального размера вектора

• Метод выделения новой памяти

• Метод добавления элемента

• Метод удаления элемента

1) Метод, который проверяет пустой ли список

[[nodiscard]] bool isEmpty() const {
		return size_ == 0;
}

2) Метод получения размера вектора

[[nodiscard]] size_t size() const {
		return size_;
}

3) Метод получения максимального размера вектора

[[nodiscard]] size_t capacity() const {
		return capacity_;
}

4) Метод выделения новой памяти

Мы будем создавать новый массив arr_ с размером capacity * 2, чтобы выделять память с запасом. Но перед этим надо записать предыдущий массив arr_ в другой указатель tmp. Затем заполняем свободные ячейки массива arr_ ячейками tmp. Не забываем удалить указатель tmp, чтобы не было утечки памяти.

void addMemory() {
		capacity_ *= 2;
    T* tmp = arr_;
    arr_ = new T[capacity_];
    for (size_t i = 0; i < size_; ++i) arr_[i] = tmp[i];
    delete[] tmp;
}

5) Метод добавления элемента

Для начало нужно проверить - есть ли свободные ячейки. Если их нет вызываем addMemory(). Далее записываем элемент в индекс size_ и увеличиваем size_ на 1.

void pushBack(const T& value) {
		if (size_ >= capacity_) addMemory();
    arr_[size_++] = value;
}

6) Метод удаления элемента

Здесь нужно уточнить, что у этого метода будет один аргумент - индекс элемента, который нужно удалить.

Чтобы удалить элемент в начале или в середине, нужно переместить все элементы, которые правее данного, на 1 ячейку. А затем уменьшить size_ на 1. Если же этот элемент находиться в конце массива, мы просто уменьшаем size_ на 1.

void remove(size_t index) {
		for (size_t i = index + 1; i < size_; ++i) {
    		arr_[i - 1] = arr_[i];
    }
    --size_;
}

Третий этап

В этом этапе мы добавим:

• Оператор обращения по индексу

• Деструктор

• Оператор записи в поток

1) Оператор обращения по индексу

Таких операторов должно быть два:

1. Оператор, который возвращает обычную ссылку на элемент

2. Оператор, который возвращает константную ссылку на элемент

T& operator[](size_t index)  {
		return arr_[index];
}

const T& operator[](size_t index) const {
		return arr_[index];
}

2) Деструктор

Деструктор нужен для того, чтобы, после выхода из области видимости, вектор сам удалял указатель.

~Vector() {
	delete[] arr_;
}

3) Оператор записи в поток

Он нужен для того, чтобы мы смогли выводить весь вектор в консоль , файлы и т.д.

template<typename T>
inline std::ostream& operator<<(std::ostream& os, const Vector<T>& vec) {
    for (size_t i = 0; i < vec.size(); ++i) os << vec[i] << " ";
    return os;
}

Дополнительный этап

Здесь мы добавим:

• Итераторы

• Конструкторы с move семантикой

• Операторы присваивания

1) Итераторы

Они нужны для алгоритмов из библиотеки algorithm, а также для цикла for each

T* begin() {
		return &arr_[0];
}

const T* begin() const {
    return &arr_[0];
}

T* end() {
   return &arr_[size_];
}

const T* end() const {
    return &arr_[size_];
}

2) Конструкторы с move семантикой

Это нужно, чтобы вектор корректно копировался и перемещался.

Когда делаем копирование вектора, нужно не забыть передать все элементы вектора other в текущий вектор с помощью цикла for.

Когда же мы вызываем конструктор с lvalue-ссылкой, то удаляем текущий указатель arr_ и перемещаем всю информацию о векторе other в текущий вектор.

Vector(Vector& other) {
    if (this != &other) {
        delete[] arr_;
     		arr_ = new T[other.capacity_];
        for (size_t i = 0; i < other.size_; ++i) arr_[i] = other.arr_[i];
        size_ = other.size_;
        capacity_ = other.capacity_;
    }
}
Vector(Vector&& other)  noexcept {
    if (this != &other) {
        delete[] arr_;
        arr_ = other.arr_;
        size_ = other.size_;
        capacity_ = other.capacity_;
        other.arr_ = nullptr;
        other.size_ = other.capacity_ = 0;
    }
}

3) Операторы присваивания

Это то же самое, что конструкторы копирования и конструкторы с move семантикой, только операторы.

Vector& operator=(Vector& other) {
    if (this != &other) {
        delete[] arr_;
      	arr_ = new T[other.capacity_];
      	for (size_t i = 0; i < other.size_; ++i) arr_[i] = other.arr_[i];
        size_ = other.size_;
        capacity_ = other.capacity_;
    }
    return *this;
}

Vector& operator=(Vector&& other) noexcept {
    if (this != &other) {
        delete[] arr_;
        arr_ = other.arr_;
        size_ = other.size_;
        capacity_ = other.capacity_;
        other.arr_ = nullptr;
        other.size_ = other.capacity_ = 0;
    }
    return *this;
    }

Итоги

Теперь вы понимаете, как работает вектор в С++. Полный код можно найти на github.