Что нужно знать для реализации?
Указатели
Move семантика (Дополнительный этап)
rValue и lValue ссылки (Дополнительный этап)
Шаблоны
Итераторы (Дополнительный этап)
Переопределение операторов
Введение
Я буду использовать c++20. Также эта статья разбита на этапы:
Первый - третий этапы предназначены для новичков
Дополнительный этап - для более опытных читателей
Первый этап
Для начала нужно создать шаблонный класс. Для этого используется template
template<typename T>
class Vector {
};Далее определяем какие поля будет содержать класс:
Указатель на область памяти, где будет находиться массив.
Размер вектора (size)
Максимальный размер вектора (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) Оператор обращения по индексу
Таких операторов должно быть два:
Оператор, который возвращает обычную ссылку на элемент
Оператор, который возвращает константную ссылку на элемент
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.
Комментарии (34)
kozlyuk
07.12.2021 01:20+11Я буду использовать c++20
Без auto, move semantics, exception safety и умных указателей, зато с дублированием кода и new в пустом объекте.
alexac
07.12.2021 01:44+11...без поддержки аллокаторов, итераторов, возможности зарезервировать место при создании, и с вызовом конструктора по умолчанию для каждого объекта в коллекции на каждое увеличение выделенной области памяти.
Когда открываешь статью желая найти кишки хорошо реализованного вектора, а там куцый велосипед на костылях.
4eyes
07.12.2021 19:08+2Я буду использовать c++20
... при этом "perfect forwarding" был придуман так давно, что про просто забыли :)
dmitrmax
07.12.2021 01:24+13А кто будет вызывать деструктор элемента в remove? Дедушка Страуструп?
На самом деле пост - иллюстрация того, почему не нужно писать свои контейнеры, если только ты не профи написания контейнеров и хорошо подумал на тему того, нужен ли миру ещё один контейнер. =)
oleg1977
07.12.2021 02:46В статье не меньше десятка ошибок, но зачем деструктор в remove()?
win32asm
07.12.2021 08:01А как ещё гарантировать, что объект будет убит не когда нибудь после дождичка в четверг?
Правда, в данной реализации более правильным решением было бы записать в освободившееся поле дефолтный объект данного типа (а иначе как мы массив смогли бы создать)?
Chaos_Optima
07.12.2021 17:00Потому что там не правильно реализован remove в принципе, вместо удаления элемента получаем копирование одного элемента в другой по связке, без фактического удаления. Ещё нет удаления последнего элемента, он получается просто дублируется.
KanuTaH
07.12.2021 01:31+7Это все как бы выглядит откровенно не очень. Например,
removeу вас по факту элемент не удаляет. В конструкторах копии и перемещения вы зачем-то вызываетеdelete[] arr_, а как вы думаете, на что у вас в этот момент указываетarr_? Зачем вообще использовать голые указатели, если есть такая абстракция, какunique_ptr, да и к тому же аж C++20 декларируется? Заодно и деструктор можно будет к чертям выкинуть, он здесь не нужен. Перед тем, как писать объект в поток, задумайтесь, а сможете ли вы его потом прочитать обратно "в целости и сохранности". В общем, годится максимум на лабораторную работу студента первого курса, да и то незачтенную. Приходите через неделю на пересдачу.4eyes
07.12.2021 21:18А какой unique_ptr там должен быть, чтобы отпала необходимость в деструкторе? ????
Edit: (Убрал вопрос про delete)
KanuTaH
07.12.2021 21:56В текущей парадигме -
std::unique_ptr<T[]>нопремер хотя бы уже был бы лучше, чем то, что сейчас.4eyes
09.12.2021 17:08На
std::unique_ptr<T[]>не получится сделатьerase, который без перевыделения памяти удалит элемент из коллекции и вызовет его деструктор.Точнее,
erase-то получится, но деструкторstd::unique_ptrпотом всё равно повызывает деструкторы для всех выделенных элементов.KanuTaH
09.12.2021 17:39Такой - не получится, но поскольку выбранная парадигма хранения элементов вектора в виде
T[]так или иначе подразумевает хранение default constructed элементов, то получится заменить его на соседний через операцию перемещения (а на худой конец копирования) в процессе сдвигания элементов, а последний элемент соответственно заменить наT{}. Это максимум что можно сделать в выбранной парадигме хранения, и для лабы это ОК, но это хотя бы нужно сделать аккуратно, а не так, как сейчас.
rafaelpro
07.12.2021 02:29-9В комментариях как всегда соревнование токсиков
in_heb
07.12.2021 02:43+13А надо было нахваливать кривое решение? Вообще странно, можно было залезть в какие-нибудь исходники вектора и тогда бы всех этих токсичных комментариев не было.
0xd34df00d
07.12.2021 02:45+11Пусть лучше комментаторы сейчас дадут пару десятков минут неприятных эмоций, чем язык в рантайме потом даст их пару ночей.
А вообще статья хорошая, можно показывать всем тем, кто говорит, что современные плюсы стали по умолчанию более дружественными к новичкам.
KanuTaH
07.12.2021 03:16+8Даже джинн из Аладдина и его отечественный аналог старик Хоттабыч были не слишком дружественны к новичкам, поскольку требовали тщательно продумывать формулировки желаний. Джафар вот криво сформулировал и на UB нарвался.
Devoter
07.12.2021 07:06+4Эм, а разве не стали? auto, std::*_ptr, std::vector, лямбды идут из коробки, как раз для тех, кто хочет писать прикладное ПО, а не велосипедить стандартную библиотеку. К слову, ничего против велосипедов целях самообучения не имею. Подобные вещи на страницах критикуемого Шилдта очень помогали как раз понять - как оно примерно работает внутри, а значит - как этим пользоваться. И да, я в курсе, что там сильно упрощенные реализации, но это же книга для новичков.
Просто сейчас, как по мне, C++ поделился на два языка: C++ для разработчиков прикладного ПО с фиберами и прочими улучшалками жизни, и C++ для разработчиков системного ПО, где не стыдно использовать адресную арифметику и голые указатели.
Refridgerator
07.12.2021 04:01+4Так за это мы и ценим хабр. Лучше испытать боль от токсичных комментариев сейчас — чем когда из-за кривого кода упадёт самолёт или встанет производство. Зато если к чему в статье придраться не нашли — можно с чистой совестью жить дальше.
mSnus
07.12.2021 04:03+7Спасибо этим токсикам. Благодаря им, начинающие, попавшие на эту статью, не повторят чужих ошибок.
Elsajalee
07.12.2021 02:36Иногда для счастья надо, что addMemory выделял память фиксированными кусками, а не удвоением.
Иногда хотелось бы не иметь возможности удалять элементы (за ненадобностью операции), но зато при добавлении новых данных и увеличении памяти обходиться без копирования и временного увеличения используемой памяти.
Это как варианты, что можно сделать из vector.
Reformat
07.12.2021 04:39+4Друзья, если мы будем так нещадно минусовать начинающих программистов, тут одни маркетологи с менеджерами и останутся. Кто не писал свой вектор, первым брось камень..
Devoter
07.12.2021 07:11+5А зачем писать статьи на данную тему? Думаю, каждый немало велосипедов в жизни написал, но это не повод публиковать о них статью. Статья и лабораторная работа - не одно и тоже.
Reformat
07.12.2021 07:32+12Я согласен что у этого конкретного велосипеда есть минусы, описанные выше. Но тем не менее, мне гораздо приятнее увидеть и обсудить статью про программирование с кодом, чем еще один мотивационно-психиологический бред от мамкиных менеджеров-коучей, который, почему-то, получает здесь плюсики.
oleg1977
07.12.2021 18:30Я лично не против лабораторных, но приведенный код просто вопиет:
Списки инициализации
std::copy вместо циклов копирования
В конструкторах не нужно делать проверку на this
Консрукторы копирования и перемещения устанавливают массив в nullptr, а деструктор удаляет без проверки
В move-assignment не нужна проверка на самоприсваивание
В move конструкторе и присваивании не нужно удалять текщий массив, нужно свопнуть его с rvalue (см также п 4)
В copy конструкторе и присваивании аргумент должен быть ссылкой на константу
Ingulf
07.12.2021 17:01а теперь по каждому хэлловорлду будет статья? предложенный вектор даже слабее чем университетская лаба
4eyes
07.12.2021 19:17В качестве дальнейшего упражнения я предложил бы автору создать vector<unique_ptr>, добавить в него пару элементов и удалить первый. Само собой, при этом должен быть удален один элемент, причем - первый, и для него дожен быть вызван деструктор.
Когда это заработает, проверить, что vector<int> все еще компилируется.
ncr
Если я усну и проснусь через сто лет и меня спросят, что сейчас происходит в C++, я отвечу: пишут велосипеды. С ошибками.
Если вдруг new T[] или operator= бросит исключение, инвариант будет нарушен.
Если вектор продолжать использовать, начнутся чудеса.