Перейти до змісту

Створення динамічного масиву

Проблема: масив фіксованого розміру

Звичайний масив у C/C++ має фіксований розмір, який задається при оголошенні:

int grades[100]; // Maximum 100 elements — what if we need 101?

Проблеми статичного масиву

  • Розмір потрібно знати заздалегідь
  • Якщо виділити забагато — марнуємо пам'ять
  • Якщо замало — програма не працює коректно

Ми хочемо масив, який росте сам, коли даних стає більше. Саме так працює std::vector у стандартній бібліотеці C++. Сьогодні ми напишемо свій аналог.

Крок 1: Структура для динамічного масиву

Що потрібно зберігати?

  • data — вказівник на масив у динамічній пам'яті
  • size — скільки елементів вже зберігається
  • capacity — скільки елементів поміщається в виділену пам'ять
struct vector {
    int* data;
    int size;
    int capacity;
};

flowchart LR
    subgraph v["vector"]
        direction LR
        data["data (int*)"]
        size["size: 3"]
        capacity["capacity: 4"]
    end
    data --> arr
    subgraph arr["Heap memory"]
        direction LR
        a0["10"] ~~~ a1["20"] ~~~ a2["30"] ~~~ a3["?"]
    end

size — це кількість елементів, які ми вже записали. capacity — це загальний обсяг виділеної пам'яті (в елементах). Коли size == capacity, масив заповнений і потрібно виділяти більше пам'яті.

Крок 2: Створення та знищення

Нам потрібні функції для створення вектора (виділення пам'яті) та його знищення (звільнення пам'яті):

vector create(int initial_capacity = 4) {
    vector v;
    v.data = new int[initial_capacity];
    v.size = 0;
    v.capacity = initial_capacity;
    return v;
}

void destroy(vector& v) {
    delete[] v.data;
    v.data = nullptr;
    v.size = 0;
    v.capacity = 0;
}

Важливо

Кожен new повинен мати відповідний delete. Якщо забути викликати destroy, станеться витік пам'яті (memory leak) — пам'ять залишиться зайнятою, але ми втратимо до неї доступ.

Крок 3: Зміна розміру (resize)

Коли масив заповнений, потрібно:

  1. Виділити новий, більший масив
  2. Скопіювати старі дані
  3. Звільнити старий масив
void resize(vector& v, int new_capacity) {
    int* new_data = new int[new_capacity];

    int to_copy = (v.size < new_capacity) ? v.size : new_capacity;
    for (int i = 0; i < to_copy; ++i) {
        new_data[i] = v.data[i];
    }

    delete[] v.data;
    v.data = new_data;
    v.capacity = new_capacity;
    v.size = to_copy;
}

flowchart LR
    subgraph before["capacity = 2"]
        b0["10"]
        b1["20"]
    end

    before -- "resize(v, 4)" --> after

    subgraph after["capacity = 4"]
        a0["10"]
        a1["20"]
        a2["?"]
        a3["?"]
    end

Стратегія подвоєння

Зазвичай capacity збільшують вдвічі (capacity * 2). Це гарантує, що в середньому додавання елемента працює за \(O(1)\) — так звана амортизована складність.

Крок 4: Додавання елементів

void push_back(vector& v, int value) {
    if (v.size == v.capacity) {
        resize(v, v.capacity * 2);
    }
    v.data[v.size] = value;
    ++v.size;
}

Крок 5: Доступ за індексом

int& at(vector& v, int index) {
    assert(index >= 0 && index < v.size);
    return v.data[index];
}

Функція повертає посилання (int&), тому через неї можна і читати, і записувати:

at(v, 0) = 42;               // write
std::cout << at(v, 0);       // read: 42

Повний приклад з вільними функціями

Зберемо все разом і перевіримо:

#include <iostream>
#include <cassert>

struct vector {
    int* data;
    int size;
    int capacity;
};

vector create(int initial_capacity = 4) {
    vector v;
    v.data = new int[initial_capacity];
    v.size = 0;
    v.capacity = initial_capacity;
    return v;
}

void destroy(vector& v) {
    delete[] v.data;
    v.data = nullptr;
    v.size = 0;
    v.capacity = 0;
}

void resize(vector& v, int new_capacity) {
    int* new_data = new int[new_capacity];
    int to_copy = (v.size < new_capacity) ? v.size : new_capacity;
    for (int i = 0; i < to_copy; ++i) {
        new_data[i] = v.data[i];
    }
    delete[] v.data;
    v.data = new_data;
    v.capacity = new_capacity;
    v.size = to_copy;
}

void push_back(vector& v, int value) {
    if (v.size == v.capacity) {
        resize(v, v.capacity * 2);
    }
    v.data[v.size] = value;
    ++v.size;
}

int& at(vector& v, int index) {
    assert(index >= 0 && index < v.size);
    return v.data[index];
}

int main() {
    vector v = create(2);

    for (int i = 1; i <= 5; ++i) {
        push_back(v, i * 10);
    }

    for (int i = 0; i < v.size; ++i) {
        std::cout << at(v, i) << " ";
    }
    std::cout << std::endl; // 10 20 30 40 50

    at(v, 2) = 999;
    std::cout << "v[2] = " << at(v, 2) << std::endl; // 999

    destroy(v);
    return 0;
}

Що не так з цим підходом?

Цей код працює, але є проблеми:

  • Легко забути викликати destroy — витік пам'яті
  • Функції create/destroy/push_back не прив'язані до структури — будь-хто може випадково змінити v.data напряму
  • Потрібно передавати структуру в кожну функцію першим аргументом

Чи є спосіб краще? Так — методи структури в C++.

Крок 6: Методи структури

У C++ структура може мати функції-члени (методи). Метод автоматично має доступ до полів структури — не потрібно передавати її як аргумент:

struct int_vector {
    int* data;
    int size;
    int capacity;

    void push_back(int value) {
        // 'data', 'size', 'capacity' — доступні напряму
        if (size == capacity) {
            resize(capacity * 2);
        }
        data[size] = value;
        ++size;
    }

    // ...
};

Порівняй виклик:

// Free functions:
push_back(v, 42);

// Member functions:
v.push_back(42);

Крок 7: Конструктор та деструктор

Конструктор — спеціальний метод, який викликається автоматично при створенні змінної. Його ім'я збігається з ім'ям структури.

Деструктор — викликається автоматично при знищенні змінної (наприклад, при виході зі scope). Його ім'я — ~ + ім'я структури.

struct int_vector {
    int* data;
    int size;
    int capacity;

    // Constructor — called automatically on creation
    int_vector(int initial_capacity = 4) {
        data = new int[initial_capacity];
        size = 0;
        capacity = initial_capacity;
    }

    // Destructor — called automatically on destruction
    ~int_vector() {
        delete[] data;
    }
};

Тепер не потрібно пам'ятати про create/destroy:

{
    int_vector v(8); // constructor: allocates memory
    v.push_back(10);
    v.push_back(20);
    // ...
} // destructor: frees memory automatically!

RAII

Цей патерн називається RAII (Resource Acquisition Is Initialization) — ресурс захоплюється в конструкторі і звільняється в деструкторі. Це основа управління пам'яттю в C++.

Крок 8: Перевантаження operator[]

В C++ можна визначити, як структура реагує на оператор []. Для цього визначається спеціальний метод operator[]:

int& operator[](int index) {
    return at(index);
}

Зверніть увагу — ми перевикористовуємо метод at(), який вже робить перевірку індексу. Тепер можна писати:

v[0] = 42;
std::cout << v[0]; // 42

Замість:

v.at(0) = 42;
std::cout << v.at(0); // 42

Повний приклад: int_vector

#include <iostream>
#include <cassert>

struct int_vector {
    int* data;
    int size;
    int capacity;

    int_vector(int initial_capacity = 4) {
        data = new int[initial_capacity];
        size = 0;
        capacity = initial_capacity;
    }

    ~int_vector() {
        delete[] data;
    }

    void resize(int new_capacity) {
        int* new_data = new int[new_capacity];
        int to_copy = (size < new_capacity) ? size : new_capacity;
        for (int i = 0; i < to_copy; ++i) {
            new_data[i] = data[i];
        }
        delete[] data;
        data = new_data;
        capacity = new_capacity;
        size = to_copy;
    }

    void push_back(int value) {
        if (size == capacity) {
            resize(capacity * 2);
        }
        data[size] = value;
        ++size;
    }

    int& at(int index) {
        assert(index >= 0 && index < size);
        return data[index];
    }

    int& operator[](int index) {
        return at(index);
    }

    void print() {
        std::cout << "[";
        for (int i = 0; i < size; ++i) {
            if (i > 0) std::cout << ", ";
            std::cout << data[i];
        }
        std::cout << "] (size=" << size
                  << ", capacity=" << capacity << ")" << std::endl;
    }
};

int main() {
    int_vector v(2);

    for (int i = 1; i <= 8; ++i) {
        v.push_back(i * 10);
    }
    v.print(); // [10, 20, 30, 40, 50, 60, 70, 80] (size=8, capacity=8)

    v[3] = 999;
    std::cout << "v[3] = " << v[3] << std::endl; // 999

    v.print(); // [10, 20, 30, 999, 50, 60, 70, 80] (size=8, capacity=8)

    return 0;
}

Попередня: Структури в C