2. Динамические массивы

Задание

Реализовать тип данных «Динамический массив целых чисел» — IntVector и основные функции для работы с ним. Разработать тестовое приложение для демонстрации реализованных функций.

Рекомендуемая структура проекта:

.
|-- Makefile
`-- src
    |-- IntVector.c
    |-- IntVector.h
    `-- main.c

Advanced: в функциях получения элемента по индексу и установки значения заданного элемента предусмотреть обработку выхода за границы массива. Продумать сигнатуру функции, позволяющую обработать ошибку в клиентском коде.

Nightmare: помимо структуры IntVector реализовать обобщенный динамический массив Vector, способный хранить данные любого типа. Бонус за выполнение задания — бесценный опыт.

Требования к работе

  1. Должны обрабатываться ошибки выделения памяти.
  2. Не должно быть утечек памяти.
  3. При тестировании приложения необходимо проверить граничные случаи. Например, работоспособность операции добавления элемента после уменьшения размера массива до нуля.

Руководство

Массивы в языке C

Массив — это тип данных, состоящий из элементов, расположенных в памяти последовательно [1].

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

В стандарте С89 размер массива должен быть известен на этапе компиляции. В стандарте С99 появились массивы переменной длины (Variable-length array), но сохранялось ограничение: после объявления массива невозможно изменить количество элементов в нем.

Массив нельзя передать в функцию. Функции, работающие с массивами, принимают указатель на нулевой элемент и, как правило, размер массива, поскольку нет переносимого способа узнать размер массива, располагая только указателем на нулевой элемент.

Память для массивов выделяется в стеке [2]. Память в стеке выделяется и освобождается автоматически, что значительно упрощает работу с ней. Однако размер стека ограничен. Его можно узнать, выполнив команду:

$ ulimit -s
8192

В приведенном примере размер стека составляет 8МБ. Для изменения размера стека требуются права администратора.

[1]http://en.cppreference.com/w/c/language/array
[2]https://en.wikipedia.org/wiki/Call_stack

Динамические массивы

На практике часто возникают задачи, в которых размер массива неизвестен на этапе компиляции, а также может меняться в процессе работы приложения. При этом требуется сохранить преимущества обычных массивов: обращение к элементам за O(1). В таких случаях используют динамические массивы, которые по историческим причинам в контексте языка C++ называют векторами. [3]

Вектор состоит из трех компонент:

  1. Указатель на участок памяти, в котором хранятся элементы.
  2. Размер. Количество заполненных элементов
  3. Емкость. Количество элементов, для которых зарезервирована память.

Ниже изображен вектор емкостью 7, состоящий из 5 элементов: 3, 1, 4, 1, 5.

data                    capacity = 7
   |                           |
   v                           v
   +---+---+---+---+---+---+---+
   | 3 | 1 | 4 | 1 | 5 |   |   |
   +---+---+---+---+---+---+---+
                       ^
                       |
                    size = 5

Базовые операции с вектором.

IntVector *int_vector_new(size_t initial_capacity)

Создает массив нулевого размера.

Параметры:initial_capacity (size_t) – исходная емкость массива
Результат:указатель на IntVector, если удалось выделить память. Иначе NULL.

Implementation note: поскольку функция возвращает указатель, в реализации ожидается выделение двух участков памяти: для структуры IntVector и для массива внутри структуры. Функция должна корректно обрабатывать ошибку при выделении любого из участков памяти, не должна возвращать указатель частично сформированный объект и не должна приводить к утечкам памяти в случае ошибки.

IntVector *int_vector_copy(const IntVector *v)
Результат:Указатель на копию вектора v. NULL, если не удалось выделить память.
void int_vector_free(IntVector *v)

Освобождает память, выделенную для вектора v.

int int_vector_get_item(const IntVector *v, size_t index)
Результат:элемент под номером index. В случае выхода за границы массива поведение не определено.
void int_vector_set_item(IntVector *v, size_t index, int item)

Присваивает элементу под номером index значение item. В случае выхода за границы массива поведение не определено.

size_t int_vector_get_size(const IntVector *v)
Результат:размер вектора.
size_t int_vector_get_capacity(const IntVector *v)
Результат:емкость вектора.
int int_vector_push_back(IntVector *v, int item)

Добавляет элемент в конец массива. При необходимости увеличивает емкость массива. Для простоты в качестве коэффициента роста можно использовать 2.

Результат:0 в случае успешного добавления элемента, -1 в случае ошибки.

Пример:

data                capacity = 6
   |                       |
   v                       v
   +---+---+---+---+---+---+
   | 3 | 1 | 4 | 1 | 5 |   |
   +---+---+---+---+---+---+
                       ^
                       |
                    size = 5

int_vector_push_back(v, 9)


data                capacity = 6
   |                       |
   v                       v
   +---+---+---+---+---+---+
   | 3 | 1 | 4 | 1 | 5 | 9 |
   +---+---+---+---+---+---+
                           ^
                           |
                        size = 6

int_vector_push_back(v, 2)


data                                        capacity = 12
   |                                               |
   v                                               v
   +---+---+---+---+---+---+---+---+---+---+---+---+
   | 3 | 1 | 4 | 1 | 5 | 9 | 2 |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+
                               ^
                               |
                            size = 7
void int_vector_pop_back(IntVector *v)

Удаляет последний элемент из массива. Нет эффекта, если размер массива равен 0.

int int_vector_shrink_to_fit(IntVector *v)

Уменьшает емкость массива до его размера.

Результат:0 в случае успешного изменения емкости, -1 в случае ошибки.
int int_vector_resize(IntVector *v, size_t new_size)

Изменяет размер массива.

Если новый размер массива больше исходного, то добавленные элементы заполняются нулями.

Если новый размер массива меньше исходного, то перевыделение памяти не происходит. Для уменьшения емкости массива в этом случае следует использовать функцию int_vector_shrink_to_fit.

Результат:0 в случае успеха, -1 в случае ошибки. Если не удалось изменить размер, массив остается в исходном состоянии.
int int_vector_reserve(IntVector *v, size_t new_capacity)

Изменить емкость массива.

Нет эффекта, если новая емкость меньше либо равна исходной.

Результат:0 в случае успеха, -1 в случае ошибки. Если не удалось изменить емкость, массив остается в исходном состоянии.
[3]http://stackoverflow.com/questions/581426/why-is-a-c-vector-called-a-vector