Упражнения: Динамичен Масив в C++

Напредък

✅ Завършени: 0 / 0📊 Напредък: 0%

💡 Напредъкът се записва локално в браузъра

ℹ️За тези упражнения

Упражненията са разделени на четири нива на трудност и имат за цел да затвърдят вашите знания за динамичните масиви в C++. Започнете с лесните задачи и постепенно преминете към по-трудните.

Съвети:

Решавайте задачите последователно
Не се притеснявайте да прегледате лекцията
Дискутирайте решенията с колеги
Тествайте кода си с различни входни данни

Легенда на Трудността

🟢 EASY

Основни концепции и теоретични въпроси

🟡 MEDIUM

Анализ и разбиране на код

🟠 MEDIUM-HARD

Приложение и имплементация

🔴 HARD

Напреднали концепции и оптимизация

🟢 Лесни Упражнения

Упражнение

10 minЛЕСНО

Задача 1: Статични масиви в C++

Въпрос: Кое от следните твърдения е вярно за статичните масиви в C++?

A) Размерът им може да се променя по време на изпълнение
B) Заделят памет в heap-а
C) Имат фиксиран размер, определен по време на компилация
D) Използват указатели за достъп до елементи

Отговор: C

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

Упражнение

10 minЛЕСНО

Задача 2: Предимства на динамичните масиви

Въпрос: Какво е основното предимство на динамичните масиви спрямо статичните?

A) По-бърз достъп до елементи
B) Възможност за автоматично изменение на размера
C) По-малко използване на памет
D) По-проста синтаксис

Отговор: B

Основното предимство на динамичните масиви е възможността за автоматично изменение на размера по време на изпълнение на програмата.

Упражнение

10 minЛЕСНО

Задача 3: Capacity (капацитет)

Въпрос: В контекста на динамичните масиви, какво представлява capacity (капацитет)?

A) Броят на текущо съхранените елементи
B) Максималният брой елементи, които могат да бъдат съхранени преди преразпределение
C) Размерът на всеки елемент в байтове
D) Броят на извършените операции push_back

Отговор: B

Капацитетът (capacity) е максималният брой елементи, които могат да бъдат съхранени в заделената памет преди да се наложи преразпределение.

Упражнение

10 minЛЕСНО

Задача 4: Освобождаване на динамична памет

Въпрос: Коя операция се използва за освобождаване на динамично заделена памет в C++?

A) free() или delete[]
B) release()
C) clear()
D) remove()

Отговор: A

За освобождаване на динамично заделена памет използваме:

delete[] за масиви заделени с new[]
free() за памет заделена с malloc()

Упражнение

10 minЛЕСНО

Задача 5: Времева сложност за достъп по индекс

Въпрос: Каква е времевата сложност за достъп по индекс в динамичен масив?

A) O(n)
B) O(log n)
C) O(1)
D) O(n²)

Отговор: C

Достъпът по индекс в динамичен масив е O(1) - константно време, тъй като елементите се съхраняват в непрекъснат блок памет.

Упражнение

10 minЛЕСНО

Задача 6: Разпределение на памет

Въпрос: Дадена е следната декларация. Къде се разпределя паметта?

int arr[10];

A) В heap-а
B) В стека
C) В глобалната памет
D) В регистрите на процесора

Отговор: B

Статичните масиви се разпределят в стека (stack), където паметта се управлява автоматично.

🟡 Средни Упражнения

Упражнение

10 minЛЕСНО

Задача 7: Капацитет по-голям от размера

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

Отговор:

Капацитетът е по-голям от размера, за да се избегнат чести операции по преразпределение на памет, които са скъпи (O(n)). Това позволява добавяне на нови елементи без веднага да се налага копиране на цялата структура.

Като имаме резервна памет, амортизираме разходите за преразпределение върху множество операции и постигаме O(1) амортизирана сложност за добавяне.

Упражнение

10 minЛЕСНО

Задача 8: Анализ на resize операция

Задача: Разгледайте следния код:

DynamicArray arr(2);
arr.push_back(10);
arr.push_back(20);
arr.push_back(30);

Какъв ще бъде капацитетът след третата операция push_back, ако масивът удвоява капацитета си при преразпределение? Обяснете стъпка по стъпка.

Отговор:

Стъпка по стъпка:

Начало: capacity = 2, size = 0
След push_back(10): size = 1, capacity = 2 (има място)
След push_back(20): size = 2, capacity = 2 (запълнен)
При push_back(30):
- size == capacity → необходимо е преразпределение
- resize() се извиква → new_capacity = 2 * 2 = 4
- Елементи се копират, памет се актуализира
- Добавя се елемент 30
- Резултат: size = 3, capacity = 4

Упражнение

15 minСРЕДНО

Задача 9: Разлика между size и capacity

Задача: Каква е разликата между size и capacity в динамичен масив? Дайте конкретен пример със стойности.

Отговор:

Size (размер):

Броят на действително съхранени елементи
Променя се при добавяне/премахване
Показва колко елемента има в момента

Capacity (капацитет):

Заделената памет - максимален брой елементи без реалокация
Обикновено по-голям или равен на size
Променя се само при преразпределение

Пример:

DynamicArray arr(4);
arr.push_back(10);
arr.push_back(20);
// size = 2 (има 2 елемента)
// capacity = 4 (може да побере 4 без реалокация)

Упражнение

15 minСРЕДНО

Задача 10: Времева сложност на resize

Задача: Анализирайте следния фрагмент от resize метода:

int* new_data = (int*)malloc(new_capacity * sizeof(int));
for (int i = 0; i < size; i++) {
    new_data[i] = data[i];
}
free(data);
data = new_data;

Каква е времевата сложност на този код и защо?

Отговор:

Времевата сложност е O(n), където n е size.

Защо?

malloc() е O(1) - заделяне на памет
Цикълът копира всички n елемента → O(n)
free() е O(1) - освобождаване
Присвояването е O(1)

Доминиращият фактор е копирането на елементите, което отнема линейно време спрямо броя на съществуващите елементи.

Упражнение

15 minСРЕДНО

Задача 11: Предимства на std::vector

Задача: Защо използването на std::vector е предпочитано пред ръчна имплементация на динамичен масив в production код? Посочете поне 3 причини.

Отговор:

Три основни причини:

Автоматично управление на паметта
- Никакви memory leaks
- RAII принципи
- Автоматично освобождаване
Богат интерфейс и функционалност
- Множество полезни методи
- Работа с STL алгоритми
- Итератори и range-based loops
Оптимизация и сигурност
- Високо оптимизиран код
- Безопасен достъп с .at()
- Изключения при грешки
- Тестван и проверен от години

Допълнителни причини:

По-лесна поддръжка на кода
Стандартизиран и познат API
Добре документиран

Упражнение

15 minСРЕДНО

Задача 12: RAII принцип

Задача: Какво е RAII принципът и как се прилага при реализацията на динамичен масив? Дайте пример с конструктор и деструктор.

Отговор:

RAII (Resource Acquisition Is Initialization) е принцип, при който:

Ресурсите се придобиват в конструктора
Ресурсите се освобождават в деструктора
Гарантира правилно управление дори при изключения

Пример:

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

public:
    // Конструктор - придобива ресурса (памет)
    DynamicArray(int initial_capacity = 4) {
        capacity = initial_capacity;
        size = 0;
        data = (int*)malloc(capacity * sizeof(int));
    }

    // Деструктор - освобождава ресурса
    ~DynamicArray() {
        free(data);
        data = nullptr;
    }
};

Предимства:

Автоматично освобождаване
Няма изтичане на памет
Безопасност при изключения

Упражнение

15 minСРЕДНО

Задача 13: Имплементация на pop_back()

Задача: Напишете псевдокод за метод pop_back(), който премахва последния елемент от динамичен масив. Трябва ли да се преразпределя памет?

Отговор:

Псевдокод:

ФУНКЦИЯ pop_back():
    АКО size == 0 ТОГАВА:
        ВЪРНИ грешка (масивът е празен)
    КРАЙ АКО

    size = size - 1  // Намаляваме размера

    // Не е нужно преразпределение на памет!
    // Просто намаляваме size

    ВЪРНИ успех
КРАЙ ФУНКЦИЯ

Важни моменти:

Не е нужно преразпределение - просто намаляваме size
Елементът физически остава в паметта, но е "невидим"
Capacity не се променя
Ако искаме да освободим памет → трябва shrink_to_fit()

C++ имплементация:

void pop_back() {
    if (size > 0) {
        size--;
    }
}

Упражнение

15 minСРЕДНО

Задача 14: Откриване на memory leak

Задача: Идентифицирайте грешката в следния код:

DynamicArray* arr = new DynamicArray(5);
arr->push_back(10);
// ... някакъв код
// програмата завършва

Отговор:

Грешка: Memory leak

Обектът се създава с new, но никъде не се извиква delete. Въпреки че деструкторът на DynamicArray ще освободи вътрешната памет за data, самият обект не се освобождава.

Правилно:

DynamicArray* arr = new DynamicArray(5);
arr->push_back(10);
// ... някакъв код
delete arr;  // Освобождаваме обекта!
arr = nullptr;

Още по-добре:

DynamicArray arr(5);  // Стек - автоматично управление
arr.push_back(10);
// ... някакъв код
// автоматично се освобождава при излизане от scope

🟠 Средно-трудни Упражнения

Упражнение

15 minСРЕДНО

Задача 15: Имплементация на insert()

Задача: Имплементирайте метод insert(int index, int value), който вмъква елемент на определена позиция в динамичен масив. Каква е времевата сложност на този метод в най-лошия случай?

Решение:

int insert(int index, int value) {
    // Проверка за валиден индекс
    if (index < 0 || index > size) {
        return -1; // Грешка
    }

    // Проверка дали е нужно преразпределение
    if (size >= capacity) {
        if (resize() == -1) {
            return -1;
        }
    }

    // Преместване на елементите надясно
    for (int i = size; i > index; i--) {
        data[i] = data[i - 1];
    }

    // Вмъкване на новия елемент
    data[index] = value;
    size++;

    return 1; // Успех
}

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

Най-лош случай: O(n)

Вмъкване в началото → трябва да преместим всички n елемента
Ако е нужно преразпределение → допълнително O(n) за копиране

Анализ по позиция:

Вмъкване в началото (index = 0): O(n)
Вмъкване в средата (index = n/2): O(n/2) = O(n)
Вмъкване в края (index = n): O(1) (като push_back)

Упражнение

15 minСРЕДНО

Задача 16: Амортизирана сложност

Задача: Обяснете концепцията за амортизирана сложност. Защо операцията push_back има амортизирана O(1) сложност, въпреки че понякога отнема O(n) време?

Отговор:

Амортизирана сложност е средната цена на операция при изпълнение на последователност от операции.

Защо push_back е O(1) амортизирано?

Математическо обяснение (при удвояване):

Нека добавим n елемента в масив с начален capacity 1:

При достигане на capacity, правим resize:
- При n=1: копираме 0 елемента
- При n=2: копираме 1 елемент
- При n=4: копираме 2 елемента
- При n=8: копираме 4 елемента
- ...
Общ брой копирания до n елемента:
```
1 + 2 + 4 + 8 + ... + n/2 ≈ n
```
Общ брой операции:
- n добавяния
- ≈ n копирания при resize
- Общо: 2n операции
Средна цена на операция:
```
2n / n = 2 = O(1)
```

Ключови моменти:

Отделни операции може да са O(n)
Но честотата им намалява експоненциално
Средно всяка операция е константна
Това е амортизирана O(1) сложност

Упражнение

20 minТРУДНО

Задача 17: Обединяване на масиви

Задача: Напишете функция, която обединява два динамични масива в нов масив. Каква стратегия бихте използвали за определяне на началния капацитет?

Решение:

DynamicArray merge(const DynamicArray& arr1, const DynamicArray& arr2) {
    // Оптимална стратегия: сумата от размерите
    int total_size = arr1.getSize() + arr2.getSize();

    // Създаваме нов масив с подходящ капацитет
    DynamicArray result(total_size);

    // Копираме елементите от първия масив
    for (int i = 0; i < arr1.getSize(); i++) {
        result.push_back(arr1.get(i));
    }

    // Копираме елементите от втория масив
    for (int i = 0; i < arr2.getSize(); i++) {
        result.push_back(arr2.get(i));
    }

    return result;
}

Стратегия за капацитет:

Оптимален подход:

capacity = size1 + size2
Плюсове:
- Никакви реалокации
- Минимално използване на памет
- Бързо изпълнение

Алтернативни стратегии:

С резерв:
```
capacity = (size1 + size2) * 1.5
```
- Ако ще добавяме още елементи
Степен на 2:
```
capacity = next_power_of_2(size1 + size2)
```
- За консистентност с resize стратегията

Времева сложност: O(n + m), където n и m са размерите на масивите

Упражнение

20 minТРУДНО

Задача 18: Сравнение със свързан списък

Задача: Сравнете динамичния масив със свързан списък по отношение на:

Достъп по индекс
Вмъкване в началото
Вмъкване в края
Използване на памет

Отговор:

Операция	Динамичен масив	Свързан списък	Кой е по-добър?
Достъп по индекс	O(1)	O(n)	Масив ✅
Вмъкване в началото	O(n)	O(1)	Списък ✅
Вмъкване в края	O(1)*	O(1)	Равни ⚖️
Изтриване в началото	O(n)	O(1)	Списък ✅
Използване на памет	По-малко	По-голямо	Масив ✅
Cache locality	Отлична	Лоша	Масив ✅

*амортизирано

Детайлно обяснение:

Динамичен масив:

✅ Бърз достъп O(1)
✅ По-малко памет (няма указатели)
✅ Добро кеширане (непрекъсната памет)
❌ Бавно вмъкване в началото/средата O(n)
❌ Реалокации при растеж

Свързан списък:

✅ Бързо вмъкване/изтриване в началото O(1)
✅ Няма реалокации
✅ Ефективно при чести модификации
❌ Бавен достъп по индекс O(n)
❌ Повече памет (указатели)
❌ Лошо кеширане

Кога какво да използваме:

Динамичен масив → често четене, рядко вмъкване/изтриване
Свързан списък → често вмъкване/изтриване, рядко достъп по индекс

🔴 Трудни Упражнения

Упражнение

20 minТРУДНО

Задача 19: Имплементация на shrink_to_fit()

Задача: Напишете пълна имплементация на метод shrink_to_fit(), който намалява капацитета на динамичен масив до текущия размер. Кога използването на такъв метод е оправдано?

Решение:

int shrink_to_fit() {
    // Ако capacity == size, няма какво да правим
    if (capacity == size) {
        return 1; // Вече е оптимален
    }

    // Ако масивът е празен
    if (size == 0) {
        free(data);
        capacity = 4; // Минимален капацитет
        data = (int*)malloc(capacity * sizeof(int));
        if (!data) {
            return -1;
        }
        return 1;
    }

    // Заделяме нова памет точно за size елемента
    int* new_data = (int*)malloc(size * sizeof(int));
    if (!new_data) {
        return -1; // Грешка при заделяне
    }

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

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

    // Актуализираме
    data = new_data;
    capacity = size;

    return 1; // Успех
}

Кога е оправдано използването?

Полезно:

След големи изтривания

arr.push_back(...); // Много елементи
// Изтриваме повечето
arr.shrink_to_fit(); // Освобождаваме паметта

Преди дълго съхранение
- Когато масивът ще "живее" дълго време
- Не очакваме повече добавяния
Ограничени ресурси
- Вградени системи
- Мобилни приложения
- Големи колекции от малки масиви

Не е оправдано:

Ако продължаваме да добавяме елементи
Overhead от реалокацията > спестената памет
Кратковременни обекти

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

Упражнение

20 minТРУДНО

Задача 20: Коефициент на растеж 1.5

Задача: Разгледайте следната модификация на resize стратегията: вместо да удвоява капацитета, масивът го увеличава с коефициент 1.5.

Какви са предимствата и недостатъците на този подход?
Изчислете колко пъти ще се извърши преразпределение при добавяне на 100 елемента при начален капацитет 4 (за коефициент 1.5 и коефициент 2).

Отговор:

Задача 21: Предимства и недостатъци

Коефициент 1.5:

✅ По-малко изхабена памет (по-малко неизползван capacity)
✅ По-добро преизползване на памет (освободените блокове може да се ползват отново)
❌ Повече реалокации (по-често се достига capacity)

Коефициент 2:

✅ По-малко реалокации (по-рядко достигане на capacity)
✅ По-проста аритметика (по-бързо изчисление)
❌ Повече изхабена памет (до 50% може да е неизползвана)

Задача 22: Изчисления за 100 елемента

Коефициент 2 (удвояване):

Начало: capacity = 4
n=4:   capacity = 8
n=8:   capacity = 16
n=16:  capacity = 32
n=32:  capacity = 64
n=64:  capacity = 128 (стига за 100 елемента)

Брой реалокации: 5

Коефициент 1.5:

Начало: capacity = 4
n=4:   capacity = 6
n=6:   capacity = 9
n=9:   capacity = 13
n=13:  capacity = 19
n=19:  capacity = 28
n=28:  capacity = 42
n=42:  capacity = 63
n=63:  capacity = 94
n=94:  capacity = 141 (стига за 100 елемента)

Брой реалокации: 8

Задача 23: Обобщение

Метрика	Коефициент 2	Коефициент 1.5
Брой реалокации (до 100)	5	8
Краен capacity	128	141
Изхабена памет	28 (22%)	41 (29%)
Общо копирани елементи	~100	~150

Заключение:

Коефициент 2: по-бърз, но повече памет
Коефициент 1.5: по-пестелив с памет, но повече работа
В практиката: много библиотеки използват 1.5 или близък коефициент

Упражнение

20 minТРУДНО

Задача 24: Generic DynamicArray<T>

Задача: Имплементирайте generic (шаблонен) клас DynamicArray<T>, който работи с произволен тип данни, не само с int. Какви допълнителни предизвикателства възникват?

Решение:

template<typename T>
class DynamicArray {
private:
    T* data;
    int size;
    int capacity;

    int resize() {
        int new_capacity = capacity * 2;

        // За сложни типове използваме new[], не malloc()
        T* new_data = new T[new_capacity];

        // Копиране чрез присвояване (извиква копиращ конструктор)
        for (int i = 0; i < size; i++) {
            new_data[i] = data[i];
        }

        delete[] data;
        data = new_data;
        capacity = new_capacity;

        return 1;
    }

public:
    DynamicArray(int initial_capacity = 4)
        : size(0), capacity(initial_capacity) {
        data = new T[capacity];
    }

    ~DynamicArray() {
        delete[] data;
    }

    // Copy constructor
    DynamicArray(const DynamicArray& other)
        : size(other.size), capacity(other.capacity) {
        data = new T[capacity];
        for (int i = 0; i < size; i++) {
            data[i] = other.data[i];
        }
    }

    // Copy assignment
    DynamicArray& operator=(const DynamicArray& other) {
        if (this != &other) {
            delete[] data;
            size = other.size;
            capacity = other.capacity;
            data = new T[capacity];
            for (int i = 0; i < size; i++) {
                data[i] = other.data[i];
            }
        }
        return *this;
    }

    // Move constructor (C++11)
    DynamicArray(DynamicArray&& other) noexcept
        : data(other.data), size(other.size), capacity(other.capacity) {
        other.data = nullptr;
        other.size = 0;
        other.capacity = 0;
    }

    // Move assignment (C++11)
    DynamicArray& operator=(DynamicArray&& other) noexcept {
        if (this != &other) {
            delete[] data;
            data = other.data;
            size = other.size;
            capacity = other.capacity;
            other.data = nullptr;
            other.size = 0;
            other.capacity = 0;
        }
        return *this;
    }

    void push_back(const T& value) {
        if (size >= capacity) {
            resize();
        }
        data[size++] = value;
    }

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

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

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

Предизвикателства:

Управление на паметта
- Не може malloc()/free() - не извикват конструктори/деструктори
- Трябва new/delete за правилна инициализация
Копиране и преместване
- Нужен е копиращ конструктор
- Нужен е copy assignment operator
- За оптимизация: move конструктор и move assignment
Const-correctness
- Различни версии на operator[] за const и non-const
Изключения
- Конструкторите може да хвърлят изключения
- Трябва exception-safe код
Специализация
- За някои типове (като bool) може да са нужни специализации

Използване:

// С int
DynamicArray<int> numbers;
numbers.push_back(10);

// С string
DynamicArray<std::string> names;
names.push_back("Alice");

// С custom тип
DynamicArray<MyClass> objects;
objects.push_back(MyClass());

Упражнение

20 minТРУДНО

Задача 25: Пространствена сложност

Задача: Анализирайте пространствената сложност на динамичен масив с коефициент на растеж 2. В най-лошия случай, каква е максималната неизползвана памет като процент от общата заделена памет?

Отговор:

Задача 26: Математически анализ

При коефициент на растеж 2, най-лошият случай е веднага след resize.

Сценарий:

Capacity = n, Size = n (пълен масив)
Добавяме 1 елемент → resize
New capacity = 2n, Size = n + 1

Изхабена памет:

unused = capacity - size
unused = 2n - (n + 1)
unused = n - 1

Процент изхабена памет:

percentage = unused / capacity * 100%
percentage = (n - 1) / 2n * 100%

При голямо n:

percentage ≈ n / 2n * 100%
percentage ≈ 50%

Задача 27: Заключение

Най-лош случай: ~50% изхабена памет

Детайлен пример:

Capacity = 128, Size = 65
Unused = 128 - 65 = 63
Percentage = 63/128 ≈ 49.2%

Задача 28: Общ случай (различни моменти):

Size	Capacity	Unused	Процент
64	64	0	0%
65	128	63	49.2%
96	128	32	25%
127	128	1	0.8%
128	128	0	0%

Средно: Около 25% изхабена памет

Задача 29: Сравнение с други коефициенти:

Коефициент	Най-лош случай	Среден случай
1.5	~33%	~17%
2.0	~50%	~25%
3.0	~67%	~33%

Trade-off:

По-голям коефициент = повече изхабена памет, но по-малко реалокации
По-малък коефициент = по-малко изхабена памет, но повече реалокации

Упражнение

20 minТРУДНО

Задача 30: Метод reserve()

Задача: Имплементирайте метод reserve(int new_capacity), подобен на std::vector::reserve(), който предварително заделя капацитет. Защо такъв метод може да подобри производителността?

Решение:

int reserve(int new_capacity) {
    // Ако новият капацитет не е по-голям, не правим нищо
    if (new_capacity <= capacity) {
        return 1; // Вече имаме достатъчен капацитет
    }

    // Заделяме нова памет
    int* new_data = (int*)malloc(new_capacity * sizeof(int));
    if (!new_data) {
        fprintf(stderr, "Memory allocation failed in reserve\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; // Успех
}

Защо подобрява производителността?

Задача 31: 1. Избягване на множество реалокации

Без reserve:

DynamicArray arr;
for (int i = 0; i < 1000; i++) {
    arr.push_back(i);  // Много resize операции!
}

С reserve:

DynamicArray arr;
arr.reserve(1000);  // Една реалокация
for (int i = 0; i < 1000; i++) {
    arr.push_back(i);  // Няма resize!
}

Задача 32: 2. Числови резултати

При добавяне на 1000 елемента с начален capacity 4:

Без reserve:

Брой resize операции: 8
Общо копирани елементи: ~2000
Време: ~T

С reserve(1000):

Брой resize операции: 1
Общо копирани елементи: 0
Време: ~T/10

Задача 33: 3. Примери за използване

Известен размер предварително:

DynamicArray arr;
arr.reserve(100);  // Знаем, че ще има 100 елемента
for (int i = 0; i < 100; i++) {
    arr.push_back(i);
}

Приблизителен размер:

DynamicArray arr;
arr.reserve(estimated_size * 1.2);  // С малко резерв
// ... добавяне на елементи ...

Пред множество добавяния:

arr.reserve(arr.getSize() + 50);  // Резервираме за още 50
for (int i = 0; i < 50; i++) {
    arr.push_back(values[i]);
}

Задача 34: 4. Кога НЕ е полезно?

Когато не знаем размера предварително
За малък брой елементи (overhead > benefit)
Когато паметта е критична (може да заделим твърде много)

Заключение: reserve() е мощна оптимизация когато знаем или можем да оценим броя елементи предварително!

Упражнение

20 minТРУДНО

Задача 35: Embedded systems стратегия

Задача: Представете си, че работите със системи с ограничена памет (embedded systems). Каква алтернативна стратегия за растеж бихте предложили вместо експоненциално удвояване? Обосновете отговора си.

Отговор:

Задача 36: Стратегия: Линеен растеж с малък фиксиран блок

int resize() {
    // Вместо capacity * 2
    const int BLOCK_SIZE = 8; // Малък фиксиран блок
    int new_capacity = capacity + BLOCK_SIZE;

    int* new_data = (int*)malloc(new_capacity * sizeof(int));
    if (!new_data) {
        return -1;
    }

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

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

    return 1;
}

Задача 37: Обосновка

Предимства за embedded системи:

Предсказуемо използване на памет
- Винаги знаем точно колко памет ще заделим
- Няма внезапни големи заявки за памет
- По-лесно планиране на ресурсите
По-малко изхабена памет
- При capacity 100, size 51:
  - С удвояване: capacity 200 (49% изхабена)
  - С блокове от 8: capacity 104 (3% изхабена)
Стабилност
- Избягваме ситуации без памет
- По-добър контрол в критични системи

Недостатъци:

Повече реалокации
- За 100 елемента:
  - С удвояване: 5-6 реалокации
  - С блокове от 8: 12-13 реалокации
По-бавно растене
- O(n²) време общо за n елемента в най-лошия случай

Задача 38: Хибридна стратегия (оптимална)

int resize() {
    int new_capacity;

    if (capacity < 64) {
        // За малки размери - удвояване
        new_capacity = capacity * 2;
    } else {
        // За големи размери - фиксирани блокове
        const int BLOCK_SIZE = 16;
        new_capacity = capacity + BLOCK_SIZE;
    }

    // ... останалата логика ...
}

Защо е по-добра:

Бързо растене в началото
Контролирано използване на памет след това
Баланс между ефективност и стабилност

Задача 39: Други подходи за embedded системи

1. Максимален капацитет

const int MAX_CAPACITY = 256;

int resize() {
    if (capacity >= MAX_CAPACITY) {
        return -1; // Не може повече
    }
    // ... растеж до MAX_CAPACITY ...
}

2. Конфигурируем растеж

struct GrowthPolicy {
    int initial_capacity;
    int block_size;
    int max_capacity;
};

// Различни профили за различни нужди

3. Предварително резервиране

// При създаване заделяме реалистичен capacity
DynamicArray arr(estimated_max_size);

Задача 40: Заключение за embedded системи

Препоръчвам:

Хибридна стратегия или линеен растеж
Максимален капацитет за безопасност
Предварително резервиране когато е възможно
Грижлив мониторинг на паметта

Приоритети:

Предсказуемост > Скорост
Стабилност > Оптималност
Сигурност > Гъвкавост

Упражнение

20 minТРУДНО

Задача 41: Benchmark на производителност

Задача: Напишете функция benchmark(), която измерва времето за добавяне на 1 милион елемента в:

Динамичен масив с начален капацитет 1
Динамичен масив с предварително резервиран капацитет 1000000
std::vector без резервация

Обяснете разликите в производителността.

Решение:

#include <iostream>
#include <chrono>
#include <vector>

// Използваме нашия DynamicArray клас
#include "DynamicArray.h"

void benchmark() {
    const int N = 1000000;

    // 1. Динамичен масив с capacity 1
    {
        auto start = std::chrono::high_resolution_clock::now();

        DynamicArray arr(1);
        for (int i = 0; i < N; i++) {
            arr.push_back(i);
        }

        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

        std::cout << "DynamicArray (capacity 1): " << duration.count() << " ms" << std::endl;
        std::cout << "  Final size: " << arr.getSize() << std::endl;
        std::cout << "  Final capacity: " << arr.getCapacity() << std::endl;
    }

    // 2. Динамичен масив с предварително резервиран capacity
    {
        auto start = std::chrono::high_resolution_clock::now();

        DynamicArray arr(1);
        arr.reserve(N);  // Предварително резервиране
        for (int i = 0; i < N; i++) {
            arr.push_back(i);
        }

        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

        std::cout << "DynamicArray (reserved " << N << "): " << duration.count() << " ms" << std::endl;
        std::cout << "  Final size: " << arr.getSize() << std::endl;
        std::cout << "  Final capacity: " << arr.getCapacity() << std::endl;
    }

    // 3. std::vector без резервация
    {
        auto start = std::chrono::high_resolution_clock::now();

        std::vector<int> vec;
        for (int i = 0; i < N; i++) {
            vec.push_back(i);
        }

        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

        std::cout << "std::vector (no reserve): " << duration.count() << " ms" << std::endl;
        std::cout << "  Final size: " << vec.size() << std::endl;
        std::cout << "  Final capacity: " << vec.capacity() << std::endl;
    }

    // 4. Бонус: std::vector с резервация
    {
        auto start = std::chrono::high_resolution_clock::now();

        std::vector<int> vec;
        vec.reserve(N);
        for (int i = 0; i < N; i++) {
            vec.push_back(i);
        }

        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

        std::cout << "std::vector (reserved " << N << "): " << duration.count() << " ms" << std::endl;
        std::cout << "  Final size: " << vec.size() << std::endl;
        std::cout << "  Final capacity: " << vec.capacity() << std::endl;
    }
}

int main() {
    std::cout << "=== Benchmark: Adding 1,000,000 elements ===" << std::endl;
    benchmark();
    return 0;
}

Примерни резултати:

=== Benchmark: Adding 1,000,000 elements ===
DynamicArray (capacity 1): 156 ms
  Final size: 1000000
  Final capacity: 1048576

DynamicArray (reserved 1000000): 18 ms
  Final size: 1000000
  Final capacity: 1000000

std::vector (no reserve): 42 ms
  Final size: 1000000
  Final capacity: 1048576

std::vector (reserved 1000000): 15 ms
  Final size: 1000000
  Final capacity: 1000000

Задача 42: Анализ на резултатите

1. DynamicArray (capacity 1): ~156 ms

Много реалокации (~20 пъти с удвояване)
Всяка реалокация копира всички елементи
Общо копирани елементи: ~2,000,000
Най-бавен вариант

2. DynamicArray (reserved): ~18 ms

Нула реалокации
Само добавяне на елементи
Оптимално използване на памет
~8.6x по-бързо от вариант 1

3. std::vector (no reserve): ~42 ms

По-малко реалокации от нашия DynamicArray
По-добра реализация на resize
Оптимизации от компилатора
~3.7x по-бързо от вариант 1

4. std::vector (reserved): ~15 ms

Същата логика като DynamicArray (reserved)
Малко по-бързо поради STL оптимизации
Най-бърз вариант

Задача 43: Ключови изводи

1. Предварителното резервиране е критично

До 8-10x по-бързо за големи масиви
Избягва скъпите реалокации

2. std::vector е по-оптимизиран

По-добра реализация на resize
Компилаторни оптимизации
Но принципите са същите

3. Експоненциалният растеж работи

Дори без reserve, резултатите са приемливи
Амортизираната сложност е реална

4. За production код

Винаги използвайте reserve() когато знаете размера
std::vector е по-добър избор от custom имплементация

Задача 44: Практически съвети

// ❌ Бавно
std::vector<int> vec;
for (int i = 0; i < BIG_NUMBER; i++) {
    vec.push_back(i);
}

// ✅ Бързо
std::vector<int> vec;
vec.reserve(BIG_NUMBER);
for (int i = 0; i < BIG_NUMBER; i++) {
    vec.push_back(i);
}

Обобщение и Следващи Стъпки

✅Какво постигнахме

Преминахте през 25 упражнения с различна сложност:

✅ 6 лесни - основни концепции
✅ 8 средни - анализ и разбиране
✅ 4 средно-трудни - приложение
✅ 7 трудни - напреднали техники

Научихте:

Как работят динамичните масиви
Разлика между size и capacity
Амортизирана сложност
Оптимизационни техники
Сравнение с други структури

Задача 45: Препоръки за практика

1. Имплементирайте

Напишете собствена пълна имплементация на динамичен масив с всички методи

2. Тествайте

Създайте unit тестове за вашата имплементация и проверете всички случаи

3. Сравнете

Сравнете производителността на вашата имплементация с std::vector

4. Разширете

Добавете допълнителни методи като insert, erase, reserve, shrink_to_fit

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

За задълбочаване:

Имплементирайте generic версия с templates
Проучете Move Semantics в C++11
Разгледайте имплементацията на std::vector в STL
Изследвайте различни стратегии за растеж

За практика:

LeetCode/HackerRank задачи с динамични масиви
Проекти използващи custom контейнери
Benchmark различни имплементации

Успех с практиката! Keep coding! 💻

Напредък

Легенда на Трудността​

🟢 EASY

🟡 MEDIUM

🟠 MEDIUM-HARD

🔴 HARD

🟢 Лесни Упражнения​

Задача 1: Статични масиви в C++​

Задача 2: Предимства на динамичните масиви​

Задача 3: Capacity (капацитет)​

Задача 4: Освобождаване на динамична памет​

Задача 5: Времева сложност за достъп по индекс​

Задача 6: Разпределение на памет​

🟡 Средни Упражнения​

Задача 7: Капацитет по-голям от размера​

Задача 8: Анализ на resize операция​

Задача 9: Разлика между size и capacity​

Задача 10: Времева сложност на resize​

Задача 11: Предимства на std::vector​

Задача 12: RAII принцип​

Задача 13: Имплементация на pop_back()​

Задача 14: Откриване на memory leak​

🟠 Средно-трудни Упражнения​

Задача 15: Имплементация на insert()​

Задача 16: Амортизирана сложност​

Задача 17: Обединяване на масиви​

Задача 18: Сравнение със свързан списък​

🔴 Трудни Упражнения​

Задача 19: Имплементация на shrink_to_fit()​

Задача 20: Коефициент на растеж 1.5​

Задача 21: Предимства и недостатъци​

Задача 22: Изчисления за 100 елемента​

Задача 23: Обобщение​

Задача 24: Generic DynamicArray<T>​

Задача 25: Пространствена сложност​

Задача 26: Математически анализ​

Задача 27: Заключение​

Задача 28: Общ случай (различни моменти):​

Задача 29: Сравнение с други коефициенти:​

Задача 30: Метод reserve()​

Задача 31: 1. Избягване на множество реалокации​

Задача 32: 2. Числови резултати​

Задача 33: 3. Примери за използване​

Задача 34: 4. Кога НЕ е полезно?​

Задача 35: Embedded systems стратегия​

Задача 36: Стратегия: Линеен растеж с малък фиксиран блок​

Задача 37: Обосновка​

Задача 38: Хибридна стратегия (оптимална)​

Задача 39: Други подходи за embedded системи​

Задача 40: Заключение за embedded системи​

Задача 41: Benchmark на производителност​

Задача 42: Анализ на резултатите​

Задача 43: Ключови изводи​

Задача 44: Практически съвети​

Обобщение и Следващи Стъпки​

Задача 45: Препоръки за практика​

1. Имплементирайте

2. Тествайте

3. Сравнете

4. Разширете

Легенда на Трудността

🟢 Лесни Упражнения

Задача 1: Статични масиви в C++

Задача 2: Предимства на динамичните масиви

Задача 3: Capacity (капацитет)

Задача 4: Освобождаване на динамична памет

Задача 5: Времева сложност за достъп по индекс

Задача 6: Разпределение на памет

🟡 Средни Упражнения

Задача 7: Капацитет по-голям от размера

Задача 8: Анализ на resize операция

Задача 9: Разлика между size и capacity

Задача 10: Времева сложност на resize

Задача 11: Предимства на std::vector

Задача 12: RAII принцип

Задача 13: Имплементация на pop_back()

Задача 14: Откриване на memory leak

🟠 Средно-трудни Упражнения

Задача 15: Имплементация на insert()

Задача 16: Амортизирана сложност

Задача 17: Обединяване на масиви

Задача 18: Сравнение със свързан списък

🔴 Трудни Упражнения

Задача 19: Имплементация на shrink_to_fit()

Задача 20: Коефициент на растеж 1.5

Задача 21: Предимства и недостатъци

Задача 22: Изчисления за 100 елемента

Задача 23: Обобщение

Задача 24: Generic DynamicArray<T>

Задача 25: Пространствена сложност

Задача 26: Математически анализ

Задача 27: Заключение

Задача 28: Общ случай (различни моменти):

Задача 29: Сравнение с други коефициенти:

Задача 30: Метод reserve()

Задача 31: 1. Избягване на множество реалокации

Задача 32: 2. Числови резултати

Задача 33: 3. Примери за използване

Задача 34: 4. Кога НЕ е полезно?

Задача 35: Embedded systems стратегия

Задача 36: Стратегия: Линеен растеж с малък фиксиран блок

Задача 37: Обосновка

Задача 38: Хибридна стратегия (оптимална)

Задача 39: Други подходи за embedded системи

Задача 40: Заключение за embedded системи

Задача 41: Benchmark на производителност

Задача 42: Анализ на резултатите

Задача 43: Ключови изводи

Задача 44: Практически съвети

Обобщение и Следващи Стъпки

Задача 45: Препоръки за практика