Динамический массив - практика

1. Процедуральный динамический массив

Видео:

• Массивы
• Типы памяти
• Базовые техники программирования

Распишите код для структуры данных динамического массива:

struct DynamicArray
{
    // ...
}

1. Создайте factory-функцию, которая возвращает массив изначальной максимальной длины, заданной параметром capacity. Создайте еще одну, которая выставляет какой-нибудь дефолтный capacity (например 4).

void test1()
{
    DynamicArray arr = createDynamicArrayWithCapacity(10);
    assert(arr.capacity == 10);
}

2. Он должен давать доступ к размерности буфера (capacity), хранить текущее количество элементов (length / count).

void test2()
{
    DynamicArray arr = createDynamicArray();
    assert(arr.length == 0);
    addElementToArray(&arr, 5);
    assert(arr.length == 1);
}

3. При добавлении элементов в массив, удваивайте длину, если массив полный. Имеется в виду, аллоцируйте буфер двойной длины, и перекопируйте все элементы. Добавляйте элемент в текущий конец массива.

void test3()
{
    DynamicArray arr = createDynamicArrayWithCapacity(1);
    addElementToArray(&arr, 5);
    assert(arr.capacity == 1);
    addElementToArray(&arr, 10);
    assert(arr.capacity == 2);
    addElementToArray(&arr, 20);
    assert(arr.capacity == 4);
}

4. Создайте функцию для доступа к элементам массива по индексу. Выполняйте проверку длины в этой функции, используя assert.

void test4()
{
    DynamicArray arr = createDynamicArray();
    addElementToArray(&arr, 5);
    int el = getElementAtIndex(&arr, 0);
    assert(el == 5);
}

5. Создайте функцию, которая возвращает текущий кусок массива как std::span. Пусть добавление элементов в массив инвалидирует этот взятый кусок, то есть можете просто стирать эту память без лишних проверок, если надо. Инвалидация означает, что уже имеющиеся указатели на элементы из массива становятся недействительными (память на которую они указывают могла быть удалена).

void test5()
{
    DynamicArray arr = createDynamicArray();
    addElementToArray(&arr, 5);
    addElementToArray(&arr, 6);
    addElementToArray(&arr, 7);

    std::span<int> span = getCurrentSpan(&arr);

    assert(span.size() == 3);
    assert(span[0] == 5);
    assert(span[1] == 6);
    assert(span[2] == 7);
}

6. Создайте функцию, которая очищает динамическую память, выделенную функциями массива. Вызывайте эту функцию когда память массива больше не нужна (free / destroy).

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

8. Отделите код связанный со структурой в отдельный файл - сделайте динамический массив модулем.

   • Объявления функций для взаимодействия со структурой и саму структуру положите в файл dynamicArray.h.
   • В main.cpp включайте файл dynamicArray.h.
   • В файл dynamicArray.cpp положите определения функций.

     Можете положить очень короткие функции в dynamicArray.h как inline.

   • Если есть вспомогательные функции, который используете в коде массива, но не в main, сделайте их static и не добавляйте их в dynamicArray.h.
   • Пропишите команду которой компилируйте в .bat (или .sh) скрипт в папке с лабой.

2. То же самое, но RAII

Видео:

• OOP, RAII

Проделайте то же самое, но:

1. Вместо factory функций, используйте дефолтный конструктор, и конструктор с параметром capacity.
2. Вместо free / destroy, определите деструктор.
3. Определите конструктор копирования.
4. Переопределите оператор присваивания.
5. Определите move конструктор.
6. Переопределите оператор присваивания с rvalue reference параметром.
7. Переопределите индексатор под доступ к элементу.
8. addElementToArray сделайте методом и назовите add.
9. Поля сделайте private, сменив struct на class.
10. Предоставьте возможность считывать значения полей, определив методы size и capacity (read-only properties).
11. В функции main, протестируйте все фичи, и покажите примеры использования.

Интерфейс здесь должен выйти примерно как у std::vector.

• Какие ошибки позволяет совершить процедуральная версия по сравнению с OOP версией? (подсказка: публичные поля, создание копий).
• Какую версию проще понять / использовать? В каких ситуациях? Почему?
• Какую роль здесь играет инкапсуляция?

Итераторы (дополнительно):

1. Сделайте возможной итерацию foreach. Для этого можете либо создать свой итератор, либо использовать метод, который возвращал std::span.