Вектор. Логическое описание и физическое представление: указатель, размер и realloc

Модуль "Файл и вектор" • урок 4 из 6 • ~8 минут

Вектор. Логическое описание на C

Вектор. Логическое описание и физическое представление

В прошлом уроке вектор был набором из восьми абстрактных операций. Теперь реализуем их на C. В классическом Паскале встроенных динамических массивов нет, а в C есть все необходимое: ручное управление памятью через malloc и realloc.

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

typedef struct {
    T* data;  /* указатель на начало блока данных */
    int size; /* текущее количество элементов */
} Vector;

Создание и простые операции

При создании запрашиваем у системы сплошной блок памяти нужного размера:

void Create(Vector* v, int sz) {
    v->size = sz;
    v->data = malloc(sizeof(T) * v->size);
}

bool Empty(Vector* v) {
    return v->size == 0;
}

int Size(Vector* v) {
    return v->size;
}

Доступ к элементам: не забываем про границы

Чтение (Load) и запись (Save) обязаны проверять, что индекс лежит в допустимом диапазоне от 0 до size - 1: C сам за границами не следит, а обращение мимо блока - неопределенное поведение:

T Load(Vector* v, int i) {
    if ((i >= 0) && (i < v->size))
        return v->data[i];
    /* сюда попадать не должны: индекс вне границ */
}

void Save(Vector* v, int i, T t) {
    if ((i >= 0) && (i < v->size))
        v->data[i] = t;
}

Изменение длины, сравнение, уничтожение

Копировать элементы вручную не нужно: realloc сначала пытается расширить блок на месте, а если за ним нет свободной памяти - выделяет новый, переносит данные и сам освобождает старый блок. Это та самая операция ИЗМЕНИТЬ_ДЛИНУ за O(N) из спецификации:

void Resize(Vector* v, int sz) {
    v->size = sz;
    v->data = realloc(v->data, sizeof(T) * v->size);
}

bool Equal(Vector* l, Vector* r) {
    if (l->size != r->size)
        return false;
    for (int i = 0; i < l->size; i++) {
        if (l->data[i] != r->data[i])
            return false;
    }
    return true;
}

void Destroy(Vector* v) {
    v->size = 0;
    free(v->data); /* без free - утечка памяти */
}

Более совершенные реализации - например, std::vector в C++ - выделяют память с запасом: емкость (capacity) больше реального размера (size), поэтому частые добавления в конец не дергают аллокатор каждый раз.