07.12.2021 00:53
Mond1c 34 4600 Источник

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

  • Указатели

  • 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.

Комментарии (34)


  1. ncr
    07.12.2021 01:19
    #23792885
    +22

    Если я усну и проснусь через сто лет и меня спросят, что сейчас происходит в C++, я отвечу: пишут велосипеды. С ошибками.

    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;
}

    Если вдруг new T[] или operator= бросит исключение, инвариант будет нарушен.
    Если вектор продолжать использовать, начнутся чудеса.


  1. kozlyuk
    07.12.2021 01:20
    #23792893
    +11

    Я буду использовать c++20

    Без auto, move semantics, exception safety и умных указателей, зато с дублированием кода и new в пустом объекте.


    1. alexac
      07.12.2021 01:44
      #23792935
      +11

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

      Когда открываешь статью желая найти кишки хорошо реализованного вектора, а там куцый велосипед на костылях.


    1. 4eyes
      07.12.2021 19:08
      #23795717
      +2

      Я буду использовать c++20

      ... при этом "perfect forwarding" был придуман так давно, что про просто забыли :)


  1. dmitrmax
    07.12.2021 01:24
    #23792903
    +13

    А кто будет вызывать деструктор элемента в remove? Дедушка Страуструп?

    На самом деле пост - иллюстрация того, почему не нужно писать свои контейнеры, если только ты не профи написания контейнеров и хорошо подумал на тему того, нужен ли миру ещё один контейнер. =)


    1. oleg1977
      07.12.2021 02:46
      #23792997

      В статье не меньше десятка ошибок, но зачем деструктор в remove()?


      1. win32asm
        07.12.2021 08:01
        #23793271

        А как ещё гарантировать, что объект будет убит не когда нибудь после дождичка в четверг?

        Правда, в данной реализации более правильным решением было бы записать в освободившееся поле дефолтный объект данного типа (а иначе как мы массив смогли бы создать)?


      1. Chaos_Optima
        07.12.2021 17:00
        #23795315

        Потому что там не правильно реализован remove в принципе, вместо удаления элемента получаем копирование одного элемента в другой по связке, без фактического удаления. Ещё нет удаления последнего элемента, он получается просто дублируется.


  1. KanuTaH
    07.12.2021 01:31
    #23792917
    +7

    Это все как бы выглядит откровенно не очень. Например, remove у вас по факту элемент не удаляет. В конструкторах копии и перемещения вы зачем-то вызываете delete[] arr_, а как вы думаете, на что у вас в этот момент указывает arr_? Зачем вообще использовать голые указатели, если есть такая абстракция, как unique_ptr, да и к тому же аж C++20 декларируется? Заодно и деструктор можно будет к чертям выкинуть, он здесь не нужен. Перед тем, как писать объект в поток, задумайтесь, а сможете ли вы его потом прочитать обратно "в целости и сохранности". В общем, годится максимум на лабораторную работу студента первого курса, да и то незачтенную. Приходите через неделю на пересдачу.


    1. 4eyes
      07.12.2021 21:18
      #23796083

      А какой unique_ptr там должен быть, чтобы отпала необходимость в деструкторе? ????

      Edit: (Убрал вопрос про delete)


      1. KanuTaH
        07.12.2021 21:56
        #23796187

        В текущей парадигме - std::unique_ptr<T[]> нопремер хотя бы уже был бы лучше, чем то, что сейчас.


        1. 4eyes
          09.12.2021 17:08
          #23803873

          На std::unique_ptr<T[]> не получится сделать erase, который без перевыделения памяти удалит элемент из коллекции и вызовет его деструктор.

          Точнее, erase-то получится, но деструктор std::unique_ptr потом всё равно повызывает деструкторы для всех выделенных элементов.


          1. KanuTaH
            09.12.2021 17:39
            #23803975

            Такой - не получится, но поскольку выбранная парадигма хранения элементов вектора в виде T[] так или иначе подразумевает хранение default constructed элементов, то получится заменить его на соседний через операцию перемещения (а на худой конец копирования) в процессе сдвигания элементов, а последний элемент соответственно заменить на T{} . Это максимум что можно сделать в выбранной парадигме хранения, и для лабы это ОК, но это хотя бы нужно сделать аккуратно, а не так, как сейчас.


  1. rafaelpro
    07.12.2021 02:29
    #23792975
    -9

    В комментариях как всегда соревнование токсиков


    1. in_heb
      07.12.2021 02:43
      #23792993
      +13

      А надо было нахваливать кривое решение? Вообще странно, можно было залезть в какие-нибудь исходники вектора и тогда бы всех этих токсичных комментариев не было.


    1. 0xd34df00d
      07.12.2021 02:45
      #23792995
      +11

      Пусть лучше комментаторы сейчас дадут пару десятков минут неприятных эмоций, чем язык в рантайме потом даст их пару ночей.


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


      1. KanuTaH
        07.12.2021 03:16
        #23793029
        +8

        Даже джинн из Аладдина и его отечественный аналог старик Хоттабыч были не слишком дружественны к новичкам, поскольку требовали тщательно продумывать формулировки желаний. Джафар вот криво сформулировал и на UB нарвался.


      1. Devoter
        07.12.2021 07:06
        #23793195
        +4

        Эм, а разве не стали? auto, std::*_ptr, std::vector, лямбды идут из коробки, как раз для тех, кто хочет писать прикладное ПО, а не велосипедить стандартную библиотеку. К слову, ничего против велосипедов целях самообучения не имею. Подобные вещи на страницах критикуемого Шилдта очень помогали как раз понять - как оно примерно работает внутри, а значит - как этим пользоваться. И да, я в курсе, что там сильно упрощенные реализации, но это же книга для новичков.

        Просто сейчас, как по мне, C++ поделился на два языка: C++ для разработчиков прикладного ПО с фиберами и прочими улучшалками жизни, и C++ для разработчиков системного ПО, где не стыдно использовать адресную арифметику и голые указатели.


    1. Refridgerator
      07.12.2021 04:01
      #23793059
      +4

      Так за это мы и ценим хабр. Лучше испытать боль от токсичных комментариев сейчас — чем когда из-за кривого кода упадёт самолёт или встанет производство. Зато если к чему в статье придраться не нашли — можно с чистой совестью жить дальше.


    1. mSnus
      07.12.2021 04:03
      #23793063
      +7

      Спасибо этим токсикам. Благодаря им, начинающие, попавшие на эту статью, не повторят чужих ошибок.


  1. Elsajalee
    07.12.2021 02:36
    #23792985

    Иногда для счастья надо, что addMemory выделял память фиксированными кусками, а не удвоением.

    Иногда хотелось бы не иметь возможности удалять элементы (за ненадобностью операции), но зато при добавлении новых данных и увеличении памяти обходиться без копирования и временного увеличения используемой памяти.

    Это как варианты, что можно сделать из vector.


    1. svr_91
      07.12.2021 08:48
      #23793355
      +3

      std::deque?


      1. Elsajalee
        07.12.2021 13:09
        #23794369

        Практически, только более предсказуемый в плане контроля выделения памяти.


  1. Reformat
    07.12.2021 04:39
    #23793087
    +4

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


    1. Devoter
      07.12.2021 07:11
      #23793199
      +5

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


      1. Reformat
        07.12.2021 07:32
        #23793229
        +12

        Я согласен что у этого конкретного велосипеда есть минусы, описанные выше. Но тем не менее, мне гораздо приятнее увидеть и обсудить статью про программирование с кодом, чем еще один мотивационно-психиологический бред от мамкиных менеджеров-коучей, который, почему-то, получает здесь плюсики.


      1. oleg1977
        07.12.2021 18:30
        #23795623

        Я лично не против лабораторных, но приведенный код просто вопиет:

        1. Списки инициализации

        2. std::copy вместо циклов копирования

        3. В конструкторах не нужно делать проверку на this

        4. Консрукторы копирования и перемещения устанавливают массив в nullptr, а деструктор удаляет без проверки

        5. В move-assignment не нужна проверка на самоприсваивание

        6. В move конструкторе и присваивании не нужно удалять текщий массив, нужно свопнуть его с rvalue (см также п 4)

        7. В copy конструкторе и присваивании аргумент должен быть ссылкой на константу


        1. Pancir
          07.12.2021 18:44
          #23795665
          +1

          (4) для delete не нужно проверять на nullptr, он сам с этим справляется.


  1. reishi
    07.12.2021 10:28
    #23793661

    Мне кажется не хватает какого-нибудь ресурса типа "review my code". Предлагающим github сразу скажу, что это совсем про другое


    1. thegriglat
      07.12.2021 10:46
      #23793721
      +3

      https://www.reddit.com/r/reviewmycode


    1. Biga
      07.12.2021 13:00
      #23794323
      +1

      codereview.stackexchange.com


      1. Refridgerator
        07.12.2021 13:55
        #23794563

        Активность там только слабовата. Что в просмотрах, что в комментариях.


  1. Ingulf
    07.12.2021 17:01
    #23795321

    а теперь по каждому хэлловорлду будет статья? предложенный вектор даже слабее чем университетская лаба


  1. 4eyes
    07.12.2021 19:17
    #23795745

    В качестве дальнейшего упражнения я предложил бы автору создать vector<unique_ptr>, добавить в него пару элементов и удалить первый. Само собой, при этом должен быть удален один элемент, причем - первый, и для него дожен быть вызван деструктор.

    Когда это заработает, проверить, что vector<int> все еще компилируется.