Списъци, Итератори и Управление на Паметта в C++

▶⚡ Накратко

За Изпита

🎯Учебни Цели

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

• ✓Опишете едносвързани и двусвързани списъци - структура, операции и предимства
• ✓Обясните и имплементирайте шаблона Iterator за масиви и свързани списъци
• ✓Контрастирайте итератори за масиви и списъци - поведение и производителност
• ✓Идентифицирайте и използвайте инструменти за откриване на изтичане на памет в C++
• ✓Приложете добри практики за избягване на изтичане на памет (RAII, smart pointers)

---

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

💡Защо да използваме списъци вместо масиви?

Списъците са фундаментална структура от данни, която предлага уникални предимства пред масивите:

• Динамичен размер: Може да расте или намалява по време на изпълнение
• Ефективни вмъквания/изтривания: Особено в средата на структурата
• Гъвкаво използване на паметта: Заделя памет само за реални елементи

Масивите имат свои предимства:

• Произволен достъп: Константно време O(1) за достъп по индекс
• Кеш ефективност: Съседни елементи в паметта
• Прост достъп: Директно индексиране

Кога да изберем списък?

Използвайте Списък Когато

• Броят елементи е неизвестен или се променя често
• Често вмъквате/изтривате в средата
• Не е нужен произволен достъп по индекс
• Паметта трябва да се използва ефективно

Използвайте Масив Когато

• Размерът е фиксиран или известен предварително
• Нужен е бърз произволен достъп
• Кеш ефективността е критична
• Работите с големи обеми данни последователно

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

⚠️Критична Тема

Изтичането на памет е сериозен проблем в C++. Динамично заделената памет, която не се освобождава, води до:

• Постепенно изчерпване на ресурси
• Намаляване на производителността
• Евентуален срив на програмата

Правилното управление на паметта е жизненоважно за стабилни C++ приложения!

---

2. Основи: Масиви, Указатели и Структури

2.1. Преговор на Масиви и Указатели

ℹ️Основни Концепции

Масив: Съседен блок памет със елементи от един тип

int arr[5] = {1, 2, 3, 4, 5};

Указател: Променлива, която съхранява адрес в паметта

int x = 10;
int* ptr = &x;     // ptr съхранява адреса на x
std::cout << *ptr; // Дереференциране - извежда 10

Връзка между Масиви и Указатели

Името на масив често се преобразува в указател към първия елемент:

int arr[3] = {10, 20, 30};
int* p = arr;     // p сочи към arr[0]
std::cout << p[1]; // Извежда 20 (еквивалентно на *(p + 1))

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

int* dynamicArr = new int[5]; // Заделяне
// Използване на масива...
delete[] dynamicArr; // Освобождаване - важно!
dynamicArr = nullptr; // Добра практика

⚠️Важно!

Винаги използвайте delete[] за масиви заделени с new[] и delete за единични обекти заделени с new.

2.2. Структури и Класове за Дефиниране на Възли

ℹ️struct vs class в C++

В C++ struct и class са почти идентични. Единствената разлика:

• struct: Членовете са public по подразбиране
• class: Членовете са private по подразбиране

Възел за Едносвързан Списък

struct Node {
    int data;
    Node* next; // Указател към следващия възел

    // Конструктор
    Node(int value) : data(value), next(nullptr) {}
};

Възел за Двусвързан Списък

class Node {
public:
    int data;
    Node* prev; // Указател към предишния възел
    Node* next; // Указател към следващия възел

    Node(int value) : data(value), prev(nullptr), next(nullptr) {}
};

Заделяне на Памет за Възли

Node* head = new Node(10);  // Заделяме първи възел
Node* second = new Node(20);
head->next = second;        // Свързваме първия към втория
second->prev = head;        // Свързваме втория към първия

// Почистване
delete head;
delete second;

✅Добри Практики

• Винаги инициализирайте указатели към nullptr
• Всеки new трябва да има съответен delete
• Разгледайте използването на smart pointers (std::unique_ptr, std::shared_ptr)

---

3. Едносвързани и Двусвързани Списъци

3.1. Едносвързан Списък: Структура и Обхождане

ℹ️Структура на Възел

Възелът съдържа:

• Данни: Съхранява реалната стойност
• Указател next: Сочи към следващия възел

Първият възел е главата (head). Последният възел има next = nullptr.

Обхождане

struct Node {
    int data;
    Node* next;
};

void traverse(Node* head) {
    Node* current = head;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next; // Преминаваме към следващия
    }
    std::cout << std::endl;
}

3.2. Двусвързан Списък: Структура и Двупосочна Навигация

ℹ️Структура на Възел

Възелът съдържа:

• Данни: Съхранява реалната стойност
• Указател next: Сочи към следващия възел
• Указател prev: Сочи към предишния възел

Първият възел има prev = nullptr. Последният възел има next = nullptr.

Обхождане (Напред и Назад)

struct Node {
    int data;
    Node* next;
    Node* prev;
};

void traverseForward(Node* head) {
    Node* current = head;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

void traverseBackward(Node* tail) {
    Node* current = tail;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->prev;
    }
    std::cout << std::endl;
}

💡Защо Двупосочна Навигация?

Двусвързаният списък позволява:

• Обхождане в двете посоки - напред и назад
• Ефективно изтриване - лесен достъп до предишния възел
• Гъвкави операции - вмъкване преди/след даден възел

3.3. Времева и Пространствена Сложност

Сложност на Основните Операции

Операция	Едносвързан Списък	Двусвързан Списък	Пространство
Вмъкване в начало	O(1)	O(1)	O(1)
Вмъкване в край	O(n) без tail*	O(1) с tail*	O(1)
Изтриване в начало	O(1)	O(1)	O(1)
Изтриване в край	O(n)	O(1) с tail*	O(1)
Търсене	O(n)	O(n)	O(1)
Достъп по индекс	O(n)	O(n)	O(1)

*С tail указател

3.4. Случаи на Употреба

Едносвързан Списък

• Стекове - LIFO структури
• Опашки - с tail указател
• Когато нужно е само напредващо обхождане
• Предимство: По-малко памет, по-проста имплементация

Двусвързан Списък

• История на браузъра - напред/назад
• Плейлисти - навигация в двете посоки
• Undo/Redo - двупосочна навигация
• Предимство: Гъвкави операции, ефективно изтриване

---

4. Шаблон Iterator (Design Pattern)

4.1. Какво е Iterator и Защо да го Използваме?

ℹ️Дефиниция

Iterator е поведенчески шаблон за дизайн, който предоставя начин за последователен достъп до елементите на колекция без да се излага вътрешното ѝ представяне.

💡Цел и Предимства

Цел: Инкапсулира логиката за обхождане, позволявайки на клиентите да обхождат различни колекции с еднакъв интерфейс.

Предимства:

• Преизползване на код: Работи с различни структури (масиви, списъци, дървета)
• Гъвкавост: Клиентите са независими от вътрешната структура
• Множество обхождания: Различни итератори могат да обхождат една колекция независимо
• Опростен клиентски код: Абстрахира сложната логика за обхождане

4.2. Дефиниране на Iterator Интерфейс (STL Стил)

ℹ️Основни Операции

Общи операции на итератора:

• begin(): Връща итератор към първия елемент
• end(): Връща итератор след последния елемент (sentinel)
• operator*(): Дереференциране - връща текущия елемент
• operator++(): Преминава към следващия елемент (pre-increment)
• operator!=(): Сравнява два итератора за неравенство

Концептуален Интерфейс

// Концептуален интерфейс - не се използва директно
template <typename T>
class Iterator {
public:
    virtual ~Iterator() = default;
    virtual T& operator*() = 0;                           // Дереференциране
    virtual Iterator& operator++() = 0;                   // Pre-increment
    virtual bool operator!=(const Iterator& other) const = 0; // Неравенство
};

4.3. Имплементация на Iterator за Масиви

ℹ️Масивите и Указателите

За масивите итераторите са просто указатели. Съседното разположение в паметта опростява нещата.

class Array {
private:
    int* data;
    size_t size;

public:
    // Вложен клас Iterator
    class Iterator {
    private:
        int* ptr; // Указателят Е итератор!

    public:
        Iterator(int* p) : ptr(p) {}

        int& operator*() { return *ptr; }           // Дереференциране
        Iterator& operator++() { ++ptr; return *this; } // Напредване
        bool operator!=(const Iterator& other) const {
            return ptr != other.ptr;
        }
    };

    Iterator begin() { return Iterator(data); }
    Iterator end() { return Iterator(data + size); } // Един след края
};

4.4. Имплементация на Iterator за Двусвързан Списък

ℹ️Списъци и Възли

За двусвързани списъци итераторите трябва да следят указател към текущия Node.

template <typename T>
class DoublyLinkedListIterator {
private:
    Node<T>* current_; // Указател към текущия възел

public:
    DoublyLinkedListIterator(Node<T>* ptr = nullptr) : current_(ptr) {}

    // Дереференциране
    T& operator*() const {
        return current_->data;
    }

    // Pre-increment
    DoublyLinkedListIterator<T>& operator++() {
        current_ = current_->next;
        return *this;
    }

    // Post-increment
    DoublyLinkedListIterator<T> operator++(int) {
        DoublyLinkedListIterator<T> temp(*this);
        current_ = current_->next;
        return temp;
    }

    // Pre-decrement (за DLL)
    DoublyLinkedListIterator<T>& operator--() {
        current_ = current_->prev;
        return *this;
    }

    // Неравенство
    bool operator!=(const DoublyLinkedListIterator<T>& other) const {
        return current_ != other.current_;
    }

    // Равенство
    bool operator==(const DoublyLinkedListIterator<T>& other) const {
        return current_ == other.current_;
    }
};

// В DoublyLinkedList класа:
// typedef DoublyLinkedListIterator<T> iterator;
// iterator begin() { return iterator(head_); }
// iterator end() { return iterator(nullptr); } // nullptr = sentinel

4.5. Сравнение на Iterator за Масиви и Списъци

Сравнителна Таблица

Характеристика	Iterator за Масив	Iterator за Списък
Памет	Лек, често само указател	Съхранява указател към възел
Скорост	Константно време O(1) за достъп и increment	Константно време O(1) за increment
Простота	По-прост заради съседната памет	По-сложна логика за обхождане на възли
Гъвкавост	Обикновено еднопосочен	Лесно поддържа двупосочно обхождане (DLL)
Произволен достъп	Да, iterator + N е O(1)	Не, iterator + N е O(N)

void example() {
    DoublyLinkedList<int> list;
    list.push_back(11);
    list.push_back(12);
    list.push_back(13);

    std::cout << "Range-based for loop:" << std::endl;
    for (auto item : list) { // Работи благодарение на begin() и end()
        std::cout << item << std::endl;
    }

    std::cout << "Ръчно използване на iterator:" << std::endl;
    for (auto iter = list.begin(); iter != list.end(); ++iter) {
        std::cout << *iter << std::endl;
    }
}

---

5. Откриване и Предотвратяване на Изтичане на Памет

5.1. Какво е Изтичане на Памет и Как Възниква?

⚠️Дефиниция

Изтичане на памет възниква когато динамично заделена памет (new, malloc) не се освобождава (delete, free) след като вече не е нужна.

Последици:

• Постепенно нарастване на използваната памет
• Влошаване на производителността
• Евентуален срив на програмата

Основни Причини

Често Срещани Грешки

• Забравяне на delete
• Загубване на указатели към заделена памет
• Изключения, които прескачат cleanup код
• Циклични препратки с raw pointers

Пример за Изтичане

void leak() {
    int* ptr = new int(10); // Памет 1
    ptr = new int(20);      // Памет 2
    // Памет 1 изтича!
    delete ptr; // Само памет 2 се освобождава
}

5.2. Инструменти за Динамичен Анализ

✅Valgrind (Memcheck)

Описание: Инструмент за дебъгване и профилиране на памет (Linux/Unix)

Използване:

# Компилиране с debug символи
g++ -g -o my_program my_program.cpp

# Стартиране с Valgrind
valgrind --leak-check=full \
         --show-leak-kinds=all \
         --track-origins=yes \
         --verbose \
         --log-file=memcheck.log \
         ./my_program

Изход: Детайлни доклади включително stack traces до местата на заделяне и размерите на изтеклите блокове.

✅AddressSanitizer (ASan)

Описание: Бърз детектор на грешки в паметта, интегриран в съвременните компилатори (GCC, Clang)

Използване:

# Компилиране с ASan
g++ -fsanitize=address -g my_program.cpp -o my_program

# Стартиране (ASan докладва грешки по време на изпълнение)
./my_program

LeakSanitizer (LSan): Подмножество на ASan, фокусирано върху изтичания

g++ -fsanitize=leak -g my_program.cpp -o my_program

Предимства: По-бърз от Valgrind, вграден в компилатора, детайлни stack traces

5.3. Статичен Анализ и Compiler Warnings

ℹ️Превантивни Мерки

Инструменти за статичен анализ:

• Анализират код без да го изпълняват
• Примери: Clang Static Analyzer, PVS-Studio, Cppcheck

Compiler Warnings:

# Активиране на предупреждения
g++ -Wall -Wextra -Werror -g my_program.cpp -o my_program

Съвременните компилатори могат да предупреждават за:

• Недостижим код
• Неизползвани променливи
• Потенциални изтичания на ресурси

5.4. Добри Практики (RAII, Smart Pointers)

ℹ️RAII (Resource Acquisition Is Initialization)

Принцип: Инкапсулирайте управлението на ресурси (памет, файлове, lock-ове) в конструктори и деструктори на обекти.

Как работи:

• Ресурсите се придобиват в конструктора
• Автоматично се освобождават в деструктора когато обектът излезе от scope

Smart Pointers

std::unique_ptr

Ексклузивна собственост

• Паметта се освобождава когато unique_ptr излезе от scope
• Не може да се копира, само да се премести

auto ptr = std::make_unique<int>(42);
// Автоматично освобождаване!

std::shared_ptr

Споделена собственост

• Използва reference counting
• Паметта се освобождава когато последният shared_ptr бъде унищожен

auto ptr1 = std::make_shared<int>(42);
auto ptr2 = ptr1; // Споделяне

std::weak_ptr

Слаба референция

• Не увеличава reference count
• Предотвратява циклични зависимости
• Трябва да се "заключи" преди използване

❌

❌ Raw Pointer (Рискован)

void processData() {
  int* data = new int[100];
  // Обработка...
  if (error) {
      return; // Изтичане!
  }
  delete[] data;
}

✅

✅ Smart Pointer (Безопасен)

void processData() {
  auto data = std::make_unique<int[]>(100);
  // Обработка...
  if (error) {
      return; // Автоматично освобождаване!
  }
  // Автоматично освобождаване!
}

✅Други Съвети

• Предпочитайте std::vector, std::list пред raw масиви/списъци когато е възможно
• Обработвайте изключения внимателно, осигурявайки cleanup
• Редовно тествайте с инструменти за динамичен анализ по време на разработка
• Следвайте правилото на тройката/петицата/нулата (Rule of Three/Five/Zero)

---

6. Практически Примери и Често Срещани Грешки

6.1. Примерна Имплементация на Двусвързан Списък

template <typename T>
class Node {
public:
    T data;
    Node<T>* next;
    Node<T>* prev;

    Node() : next(nullptr), prev(nullptr) {}
    Node(const T& item, Node<T>* n = nullptr, Node<T>* p = nullptr)
        : data(item), next(n), prev(p) {}
};

template <typename T>
class DoublyLinkedList {
private:
    Node<T>* head_;
    Node<T>* tail_;
    unsigned int size_;

public:
    DoublyLinkedList() : head_(nullptr), tail_(nullptr), size_(0) {}

    ~DoublyLinkedList() {
        destroy_list();
    }

    void destroy_list() {
        Node<T>* current = head_;
        while (current != nullptr) {
            Node<T>* temp = current->next;
            delete current;
            current = temp;
        }
        head_ = nullptr;
        tail_ = nullptr;
        size_ = 0;
    }

    void push_back(const T& val) {
        Node<T>* newnode = new Node<T>(val);

        if (!tail_) { // Празен списък
            head_ = newnode;
            tail_ = newnode;
        } else {
            tail_->next = newnode;
            newnode->prev = tail_;
            tail_ = newnode;
        }
        size_++;
    }

    unsigned int size() const { return size_; }

    // Iterator typedef
    typedef DoublyLinkedListIterator<T> iterator;

    iterator begin() { return iterator(head_); }
    iterator end() { return iterator(nullptr); }
};

6.2. Често Срещани Грешки

⚠️Грешка 1: Неправилна Логика за Вмъкване

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

void insert(iterator place, const T& item) {
    Node<T>* ptr = place.current_;
    if (!ptr) {
        push_back(item);
        // БАГ: Липсва return - изпълнението продължава!
    }
    Node<T>* newnode = new Node<T>(item); // Потенциално изтичане
    newnode->next = ptr;
    newnode->prev = ptr->prev;
    if (ptr->prev) ptr->prev->next = newnode;
    ptr->prev = newnode;
    // БАГ: Липсва актуализация на head_ при вмъкване в началото
}

Коректна имплементация:

void insert(iterator place, const T& item) {
    Node<T>* ptr = place.current_;
    if (!ptr) {
        push_back(item);
        return; // Важно: явен return
    }
    Node<T>* newnode = new Node<T>(item);
    newnode->next = ptr;
    newnode->prev = ptr->prev;

    if (ptr->prev) {
        ptr->prev->next = newnode;
    } else {
        head_ = newnode; // Актуализиране на head
    }
    ptr->prev = newnode;
    size_++;
}

⚠️Грешка 2: Изтичане в Деструктора

Неправилно:

~DoublyLinkedList() {
    Node<T>* current = head_;
    while (current != nullptr) {
        Node<T>* temp = current->next;
        delete current;
        current = temp;
    }
    // БАГ: head_ и tail_ не са нулирани
    // БАГ: size_ не е нулиран
}

Правилно (виж имплементацията на destroy_list() по-горе)

⚠️Грешка 3: Shallow Copy в Copy Constructor

Неправилно (Shallow Copy):

DoublyLinkedList(const DoublyLinkedList<T>& other) {
    head_ = other.head_;  // Само копира указателя!
    tail_ = other.tail_;
    size_ = other.size_;
    // И двата списъка сочат към едни и същи възли
    // Изтриването на единия ще унищожи и другия!
}

Правилно (Deep Copy):

DoublyLinkedList(const DoublyLinkedList<T>& other)
    : head_(nullptr), tail_(nullptr), size_(0) {
    Node<T>* current = other.head_;
    while (current != nullptr) {
        push_back(current->data); // Създаваме нови възли
        current = current->next;
    }
}

6.3. Използване на Valgrind и AddressSanitizer

Код с изтичане:

#include <iostream>

void leakyFunction() {
    int* arr = new int[50];
    arr[0] = 10;
    // Упс, забравихме delete[]!
}

int main() {
    leakyFunction();
    return 0;
}

Компилиране и анализ:

g++ -g -o program program.cpp
valgrind --leak-check=full --show-leak-kinds=all ./program

Изход на Valgrind:

==12345== HEAP SUMMARY:
==12345==     in use at exit: 200 bytes in 1 blocks
==12345==   total heap usage: 1 allocs, 0 frees, 200 bytes allocated
==12345==
==12345== 200 bytes in 1 blocks are definitely lost in loss record 1 of 1
==12345==    at 0x4C2E0EF: operator new[](unsigned long)
==12345==    by 0x400687: leakyFunction() (program.cpp:4)
==12345==    by 0x4006A5: main (program.cpp:9)

Ключови индикатори: "definitely lost" е ясно изтичане.

Същият код:

Компилиране и стартиране:

g++ -fsanitize=address -g -o program program.cpp
./program

Изход на ASan:

=================================================================
==12345==ERROR: LeakSanitizer: detected memory leaks

Direct leak of 200 byte(s) in 1 object(s) allocated from:
    #0 0x7f8c9b8f7d38 in operator new[](unsigned long)
    #1 0x400687 in leakyFunction() program.cpp:4
    #2 0x4006a5 in main program.cpp:9

SUMMARY: AddressSanitizer: 200 byte(s) leaked in 1 allocation(s).

---

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

✅Основни Изводи

Структури от данни:

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

Итератори:

• Шаблонът Iterator предоставя универсален интерфейс за обхождане
• Разделя клиентския код от вътрешното представяне
• Итераторите за масиви често са указатели; за списъци управляват указатели към възли

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

• Изтичането на памет възниква когато динамично заделената памет не се освобождава
• Инструменти като Valgrind и AddressSanitizer са критични за откриване
• Добри практики като RAII и smart pointers са съществени за превенция

Препоръчителни Четива

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

Книги:

• "Effective C++" от Scott Meyers - Управление на ресурси, smart pointers
• "The C++ Standard Library" от Nicolai M. Josuttis - STL, контейнери, итератори
• "Modern C++ Design" от Andrei Alexandrescu - Напреднали шаблони за дизайн

Онлайн Ресурси:

• The Quest for the Fastest Linked List
• Linked List in C++ - GeeksforGeeks
• Memory Management in C++

Упражнения за Практика

ℹ️Предложени Задачи

1. Имплементирайте push_front, pop_front, pop_back за DoublyLinkedList
2. Проектирайте и имплементирайте const iterator за вашия списък
3. Рефакторирайте списъка да използва std::unique_ptr за управление на възлите
4. Напишете програма с умишлени изтичания и използвайте Valgrind/ASan за откриването им
5. Имплементирайте метод reverse() който обръща списъка на място

---

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

Linked Lists Туториали

• Implementing Iterator Pattern of a Single Linked List - Iterator имплементация
• Linked Lists - Learn C++ - Интерактивен туториал
• Linked List in C++ - GeeksforGeeks - Пълно ръководство

Iterators в C++

• Linked List Iterator Implementation - Stack Overflow решения
• C++20 Singly Linked List with Iterator - Code Review
• Iterators for Linked Lists - Lawrence University - Академичен материал

Видео Лекции

• Linked List and Iterators - C++ Beginners Tutorial - Видео обяснение

Практически Задачи

• PDR: Laboratory 2 - Linked Lists - Лабораторни упражнения
• Simple Implementation of C++ Iterator in Linked List - Примери за имплементация

C++ STL и Iterators

• C++ Iterators Reference - Официална документация
• std::list Documentation - STL list референция

---

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