Динамичен Масив: Свойства и Реализация в C++

▶⚡ Накратко

За Изпита

🎯Учебни Цели

След края на тази лекция вие ще можете да:

• ✓Определяте концепцията и нуждата от динамични масиви
• ✓Разпознавате основните свойства и поведение на динамичните масиви
• ✓Анализирате примерна реализация на динамичен масив в C++
• ✓Прилагате знания за динамични масиви за решаване на прости задачи
• ✓Идентифицирате предимства и недостатъци на динамичните масиви спрямо други структури от данни

---

1. Въведение и Мотивация

💡Защо са необходими динамичните масиви?

Статичните масиви имат фиксиран размер, определен по време на компилация, което ги прави негъвкави за реални приложения. Динамичните масиви решават този проблем, като позволяват:

• Динамично изменение на размера по време на изпълнение
• Ефективно използване на паметта - заделя се само нужното
• Автоматично разширяване при добавяне на нови елементи
• Бърз произволен достъп като при статичните масиви (O(1))

Ограничения на статичните масиви

❌ Проблеми

Фиксиран размер

• Не може да се променя след декларация
• Трябва да знаем предварително колко елементи ще съхраняваме

Неефективност

• Твърде голям → загуба на памет
• Твърде малък → невъзможност за разширение

✅ Решение: Динамични масиви

Променлив размер

• Автоматично се адаптират към нуждите
• Добавяне и премахване по време на изпълнение

Ефективност

• Оптимално използване на паметта
• Баланс между скорост и гъвкавост

Практически примери

Кога са необходими динамични масиви:

• Съхранение на списък с потребители, който се променя
• Обработка на входни данни с неизвестен брой елементи
• Реализация на стекове, опашки и други структури
• Приложения с променливи количества данни

---

2. Преговор: Основи на Масивите и Паметта

2.1. Статични масиви в C++

ℹ️Основни характеристики

Декларация и инициализация:

int arr[5];                      // Декларира масив от 5 елемента
int arr[5] = {1, 2, 3, 4, 5};   // Инициализация

Достъп до елементи:

arr[0] = 10;        // Присвояване
int x = arr[2];     // Четене

Ключови особености:

• Фиксиран размер при декларация
• Разпределени в стека (stack)
• Автоматично управление на паметта

2.2. Динамична памет в C++

Стек (Stack)

Характеристики:

• Автоматично управление
• Бърз достъп
• Ограничен размер
• За локални променливи

Използване:

int arr[10]; // Стек

Хийп (Heap)

Характеристики:

• Ръчно управление
• По-бавен достъп
• Голям размер
• За динамична памет

Използване:

int* arr = new int[10]; // Хийп
delete[] arr;

2.3. Указатели и динамично разпределение

// Заделяне на памет за единичен елемент
int* ptr = new int(10);
std::cout << *ptr << std::endl;  // Извежда 10
delete ptr;
ptr = nullptr;

// Заделяне на памет за масив
int* arr = new int[5];
arr[0] = 1;
arr[1] = 2;
// ... работа с масива ...
delete[] arr;
arr = nullptr;

⚠️Важно!

Ключови правила:

• Използвайте new[] за масиви
• Използвайте delete[] за освобождаване на масиви
• Винаги задавайте nullptr след delete
• Избягвайте изтичане на памет (memory leaks)!

❌

❌ Неправилно

int* arr = new int[5];
// ... използване ...
delete arr;  // Грешка! Трябва delete[]

✅

✅ Правилно

int* arr = new int[5];
// ... използване ...
delete[] arr;  // Правилно!
arr = nullptr;

---

3. Основни Концепции на Динамичните Масиви

3.1. Определение и свойства

ℹ️Какво е динамичен масив?

Динамичен масив е структура от данни, която:

• Позволява променлив размер по време на изпълнение
• Съхранява елементи в непрекъснат блок памет
• Автоматично се разширява при нужда
• Поддържа бърз достъп по индекс (O(1))

Ключови понятия:

• Size (размер) - брой елементи, които се съхраняват в момента
• Capacity (капацитет) - общ брой елементи, за които е заделена памет
• Reallocation (преразпределение) - процес на заделяне на нова памет при нужда

3.2. Капацитет срещу Размер

Size (Размер)

Действителен брой елементи

• Колко елемента има в момента
• Променя се при add/remove
• size ≤ capacity (винаги)

int getSize() { return size; }

Capacity (Капацитет)

Заделена памет

• Максимален брой без реалокация
• Обикновено по-голям от size
• Намалява честотата на копиране

int getCapacity() { return capacity; }

💡Защо capacity > size?

Ефективност! Като имаме резервна памет:

• Избягваме чести операции по преразпределение (скъпи - O(n))
• Добавянето на елементи става по-бързо
• Амортизираме разходите за копиране върху множество операции

Пример:

• Начален capacity = 4, size = 0
• След добавяне на 3 елемента: size = 3, capacity = 4
• Има място за още 1 елемент без реалокация!

3.3. Стратегия за автоматично преоразмеряване

ℹ️Как работи преоразмеряването?

Когато size достигне capacity:

1. Заделя се нов блок памет с по-голям капацитет
2. Копират се всички съществуващи елементи
3. Освобождава се старата памет
4. Актуализират се указателите и capacity

Типични стратегии за растеж:

• Удвояване: new_capacity = capacity * 2
• Коефициент 1.5: new_capacity = capacity * 1.5
• Добавяне на константа: new_capacity = capacity + BLOCK_SIZE

3.4. Амортизирана сложност

✅O(1) амортизирана сложност

Защо push_back е O(1)?

Въпреки че понякога отнема O(n) време (при преразпределение), средно всяка операция е константна!

Математическо обяснение:

• При удвояване: 1 + 2 + 4 + 8 + 16 + ... + n
• Сумата е приблизително 2n
• За n операции → средно 2 операции на елемент
• Резултат: O(1) амортизирано

---

4. Примерна Реализация на Динамичен Масив

4.1. Архитектура на класа

ℹ️Структура на DynamicArray

Приватни членове:

• int* data - указател към динамично заделената памет
• int size - брой елементи в момента
• int capacity - общо заделена памет

Защо са необходими?

• data - управлява динамичната памет
• size - следи колко елементи има
• capacity - оптимизира преразпределението

class DynamicArray {
private:
    int* data;
    int size;
    int capacity;

public:
    DynamicArray(int initial_capacity = 4);
    ~DynamicArray();
    int push_back(int value);
    int get(int index);
    int operator[](int index);
    int getSize() { return size; }
    int getCapacity() { return capacity; }

private:
    int resize();
};

4.2. Конструктор и деструктор

Конструктор

Роля: Инициализира масива

DynamicArray(int initial_capacity = 4) {
    capacity = initial_capacity;
    size = 0;
    data = (int*)malloc(
        capacity * sizeof(int)
    );
    if (!data) {
        fprintf(stderr,
            "Memory allocation failed\n");
    }
}

Деструктор

Роля: Освобождава паметта

~DynamicArray() {
    free(data);
    data = nullptr;
}

RAII принцип:

• Resource Acquisition Is Initialization
• Ресурси се придобиват в конструктора
• Освобождават се в деструктора

⚠️Критично важно!

Деструкторът е от ключово значение за предотвратяване на изтичане на памет! Без него цялата заделена памет би останала неосвободена след унищожаването на обекта.

4.3. Метод push_back

int push_back(int value) {
    // Проверяваме дали е необходимо разширяване
    if (size >= capacity) {
        if (resize() == -1) {
            return -1; // Грешка при преразпределение
        }
    }

    // Добавяме новия елемент
    data[size] = value;
    size++;
    return 1; // Успешно добавяне
}

ℹ️Логика на операцията

Две фази:

1. Проверка за място - ако size >= capacity → извикваме resize()
2. Добавяне - поставяме елемента на позиция size и увеличаваме size

Времева сложност:

• Обикновено: O(1)
• При resize: O(n)
• Амортизирано: O(1)

4.4. Помощна функция resize

int resize() {
    int new_capacity = capacity * 2; // Удвояваме капацитета

    // Заделяме нова памет
    int* new_data = (int*)malloc(new_capacity * sizeof(int));
    if (!new_data) {
        fprintf(stderr, "Memory reallocation failed\n");
        return -1;
    }

    // Копираме старите данни
    for (int i = 0; i < size; i++) {
        new_data[i] = data[i];
    }

    // Освобождаваме старата памет
    free(data);

    // Обновяваме указателя и капацитета
    data = new_data;
    capacity = new_capacity;

    return 1; // Успешно
}

ℹ️Стъпки на преразпределението

1. Заделяне - алокираме нова памет с удвоен размер
2. Копиране - прехвърляме всички елементи
3. Освобождаване - изчистваме старата памет
4. Актуализация - обновяваме указателя и capacity

Времева сложност: O(n) - копираме всички елементи

4.5. Достъп до елементи

int get(int index) {
    if (index < 0 || index >= size) {
        fprintf(stderr, "Index out of bounds\n");
        return -1;
    }
    return data[index];
}

// Претоварване на оператора []
int operator[](int index) {
    return data[index];
}

❌

get() - Безопасен достъп

Особености:

• Проверява границите
• Връща -1 при грешка
• По-бавен (незначително)
• Препоръчва се за production

✅

operator[] - Бърз достъп

Особености:

• Без проверка на границите
• Максимална скорост
• Познат синтаксис
• Отговорност на програмиста

4.6. Пълен пример

#include <stdio.h>
#include <stdlib.h>

class DynamicArray {
private:
    int* data;
    int size;
    int capacity;

    int resize() {
        int new_capacity = capacity * 2;
        int* new_data = (int*)malloc(new_capacity * sizeof(int));

        if (!new_data) {
            fprintf(stderr, "Memory reallocation failed\n");
            return -1;
        }

        for (int i = 0; i < size; i++) {
            new_data[i] = data[i];
        }

        free(data);
        data = new_data;
        capacity = new_capacity;

        return 1;
    }

public:
    DynamicArray(int initial_capacity = 4) {
        capacity = initial_capacity;
        size = 0;
        data = (int*)malloc(capacity * sizeof(int));
        if (!data) {
             fprintf(stderr, "Initial memory allocation failed\n");
        }
    }

    ~DynamicArray() {
        free(data);
        data = nullptr;
    }

    int push_back(int value) {
        if (size >= capacity) {
            if (resize() == -1) {
                return -1;
            }
        }
        data[size] = value;
        size++;
        return 1;
    }

    int get(int index) {
        if (index < 0 || index >= size) {
            fprintf(stderr, "Index out of bounds\n");
            return -1;
        }
        return data[index];
    }

    int operator[](int index) {
        return data[index];
    }

    int getSize() { return size; }
    int getCapacity() { return capacity; }
};

int main() {
    DynamicArray arr(2);

    printf("Initial Size: %d, Initial Capacity: %d\n",
           arr.getSize(), arr.getCapacity());

    arr.push_back(10);
    arr.push_back(20);
    printf("After 2 push_backs: Size: %d, Capacity: %d\n",
           arr.getSize(), arr.getCapacity());

    arr.push_back(30);
    printf("After 3rd push_back: Size: %d, Capacity: %d\n",
           arr.getSize(), arr.getCapacity());

    arr.push_back(40);
    arr.push_back(50);
    printf("After 5th push_back: Size: %d, Capacity: %d\n",
           arr.getSize(), arr.getCapacity());

    printf("Elements in array: ");
    for (int i = 0; i < arr.getSize(); i++) {
        printf("%d ", arr.get(i));
    }
    printf("\n");

    printf("Element at index 1: %d\n", arr[1]);
    printf("Element at index 4: %d\n", arr[4]);

    return 0;
}

Изход:

Initial Size: 0, Initial Capacity: 2
After 2 push_backs: Size: 2, Capacity: 2
After 3rd push_back: Size: 3, Capacity: 4
After 5th push_back: Size: 5, Capacity: 8
Elements in array: 10 20 30 40 50
Element at index 1: 20
Element at index 4: 50

---

5. Сравнение с STL Контейнери

5.1. Защо да използваме std::vector?

✅Предимства на std::vector

Автоматично управление на паметта:

• Никакви memory leaks
• Автоматично освобождаване
• RAII принципи

Богат интерфейс:

• Множество полезни методи
• Работа с STL алгоритми
• Итератори и range-based loops

Оптимизация и сигурност:

• Високо оптимизиран код
• Безопасен достъп с .at()
• Изключения при грешки
• Тестван от години

#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec;

    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);

    std::cout << "Size: " << vec.size() << std::endl;
    std::cout << "Capacity: " << vec.capacity() << std::endl;

    // Безопасен достъп
    try {
        std::cout << vec.at(10) << std::endl;
    } catch (const std::out_of_range& e) {
        std::cout << "Error: " << e.what() << std::endl;
    }

    return 0;
}

5.2. Кога да реализираме собствен динамичен масив?

Образователни цели

Учебни ползи:

• Разбиране на управлението на памет
• Познаване на вътрешната структура
• Практика с указатели
• Подготовка за интервюта

Специални случаи

Рядко в production:

• Специфични изисквания за производителност
• Вградени системи с ограничения
• Специализирана функционалност
• Наследен код

ℹ️Заключение

В образователна среда:

• Реализацията е отлично упражнение
• Помага за разбиране на основните принципи
• Развива умения за low-level програмиране

В производствен код:

• Винаги използвайте std::vector
• Надежден, оптимизиран и тестван
• Богат набор от функционалности
• По-безопасен и поддържаем код

---

6. Сравнение: Статични vs Динамични Масиви

Характеристика	Статични масиви	Динамични масиви
Размер	Фиксиран при създаването	Променя се автоматично
Използване на памет	Винаги еднакво	Адаптира се към данните
Добавяне на елементи	Невъзможно извън размера	Автоматично разширение
Достъп по индекс	O(1)	O(1)
Памет	Стек	Хийп
Гъвкавост	Ниска	Висока
Режийност	Минимална	Някои копирания при реалокация

---

7. Най-добри Практики и Често Срещани Грешки

7.1. Добри практики

✅Препоръки за използване

Избор на структура:

• Динамични масиви за чести добавяния в края
• Бърз достъп по индекс е приоритет
• Известен приблизителен размер → използвайте reserve()

Управление на паметта:

• Използвайте std::vector вместо ръчно управление
• Прилагайте RAII принципа
• Избягвайте "голи" указатели

Оптимизация:

• Предварително резервирайте памет с reserve()
• Избягвайте чести реалокации
• Балансирайте капацитет и паметова ефективност

7.2. Често срещани грешки

⚠️Внимание!

Превишаване на границите:

// ❌ Грешка
arr[arr.getSize()]; // Извън границите!

// ✅ Правилно
if (index < arr.getSize()) {
    arr[index];
}

Утечки на памет:

// ❌ Memory leak
int* data = new int[100];
// Забравяме delete[]

// ✅ Правилно
int* data = new int[100];
delete[] data;
data = nullptr;

Неправилна реалокация:

// ❌ Лош растеж (твърде много реалокации)
new_capacity = capacity + 1;

// ✅ Добър растеж
new_capacity = capacity * 2;

Объркване на size и capacity:

// ❌ Грешка
for (int i = 0; i < arr.getCapacity(); i++)

// ✅ Правилно
for (int i = 0; i < arr.getSize(); i++)

---

8. Обобщение и Ключови Изводи

✅Какво научихме

Динамични Масиви

• Гъвкави структури с променлив размер
• Ефективен достъп по индекс - O(1)
• Амортизирана O(1) сложност за добавяне
• Баланс между гъвкавост и производителност

Ключови концепции

• Size vs Capacity - важно разграничение
• Реалокация - ключов механизъм за растеж
• RAII - принцип за управление на ресурси
• Амортизирана сложност - средна производителност

Практически съвети

• Използвайте std::vector в production код
• Разбирайте вътрешната структура за интервюта
• Избягвайте изтичане на памет
• Оптимизирайте с reserve() когато е възможно

ℹ️Следващи стъпки

За практика:

• Имплементирайте собствен динамичен масив
• Сравнете производителността с std::vector
• Добавете допълнителни методи (insert, erase, reserve)
• Създайте generic версия с шаблони (template)

За по-задълбочено разбиране:

• Изследвайте различни стратегии за растеж
• Анализирайте пространствена и времева сложност
• Сравнете с други структури (свързани списъци)
• Проучете имплементацията на std::vector

---

Допълнителни Ресурси

Dynamic Arrays и std::vector

• How do Dynamic Arrays Work? - GeeksforGeeks - Вътрешна имплементация
• Vectors in C++: The Smart Dynamic Array - Практическо ръководство
• Mastering C++ Vectors - Medium - С примери
• Master Dynamic Arrays with std::vector - Актуализирано за C++23

Имплементация и Вътрешности

• Vector Implementation in C++ - Delft Stack - Как да имплементираме собствен vector
• How to Implement Our Own Vector Class - Стъпка по стъпка
• Dynamic Array Implementation - Yep - О(1) операции
• C++ Vector Implementation - GitHub - std::vector-подобна имплементация в C

Memory Management

• Creating Dynamically-Allocated Array of std::vectors - Stack Overflow дискусия
• C++ Vector Implementation - GitHub - С exception safety

Практически Примери

• C++ Reference: std::vector - Официална документация
• Dynamic Array vs Static Array - Сравнение

Книги

• "Effective STL" by Scott Meyers - Best practices за STL контейнери
• "C++ Primer" - Глава за std::vector и динамична памет

---

Благодаря за вниманието! Успех с упражненията!