Алгоритмы и структуры данных на C++: практическое руководство для разработчиков

Алгоритмы и структуры данных на C++: от теории к реальным проектам

Освоение алгоритмов и структур данных — это фундамент, который отличает начинающего программиста от профессионального инженера. В C++, одном из самых мощных и производительных языков, понимание этих концепций позволяет писать не просто работающий, а быстрый, масштабируемый и надёжный код. В этой статье мы разберём ключевые структуры данных и алгоритмы на практике, с готовыми примерами, которые вы сможете сразу использовать в своих проектах.

Мы не будем углубляться в абстрактную теорию — каждый раздел содержит конкретный код на C++ и пояснения, как и почему работает та или иная конструкция. Материал ориентирован на разработчиков, которые уже знакомы с синтаксисом C++, но хотят систематизировать знания по алгоритмам.

1. Базовые структуры данных: массивы, списки и динамические структуры

Начнём с самого необходимого. В C++ стандартная библиотека (STL) предоставляет мощные контейнеры, но понимание их внутреннего устройства критически важно для оптимизации.

Динамический массив (std::vector)

std::vector — это самый часто используемый контейнер. Он представляет собой динамический массив, который автоматически расширяется при добавлении элементов. Однако важно помнить про амортизированную сложность: вставка в конец — O(1) в среднем, но вставка в середину — O(n).

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = {10, 20, 30, 40};
    
    // Добавление в конец
    numbers.push_back(50);
    
    // Вставка в начало (дорогая операция)
    numbers.insert(numbers.begin(), 5);
    
    // Удаление последнего элемента
    numbers.pop_back();
    
    for (int num : numbers) {
        std::cout << num << " ";
    }
    // Вывод: 5 10 20 30 40
    return 0;
}

Связный список (std::list)

В отличие от вектора, std::list реализован как двусвязный список. Он идеален, когда вы часто вставляете или удаляете элементы в середине контейнера — эти операции выполняются за O(1). Плата за это — отсутствие прямого доступа по индексу.

#include <list>

std::list<std::string> tasks = {"Написать код", "Провести тесты"};
tasks.push_front("Спланировать архитектуру");
tasks.push_back("Задокументировать");

// Вставка в середину
auto it = tasks.begin();
std::advance(it, 2); // Перемещаем итератор на 2-й элемент
tasks.insert(it, "Рефакторинг");

Стек и очередь (std::stack, std::queue)

Это адаптеры контейнеров, которые ограничивают функциональность базового контейнера. Стек работает по принципу LIFO (Last In, First Out), очередь — FIFO (First In, First Out).

#include <stack>
#include <queue>

// Стек
std::stack<int> st;
st.push(1);
st.push(2);
st.pop(); // Удаляет 2

// Очередь
std::queue<int> q;
q.push(10);
q.push(20);
q.pop(); // Удаляет 10 (первый)

2. Алгоритмы сортировки и поиска: от пузырька до бинарного поиска

Сортировка — классическая задача, но на практике важно знать, когда использовать встроенные алгоритмы, а когда писать свои.

Быстрая сортировка (QuickSort) — реализация в C++

STL использует интроспективную сортировку (гибрид QuickSort, HeapSort и InsertionSort). Но для понимания напишем классический QuickSort:

#include <iostream>
#include <vector>

int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// Использование:
std::vector<int> data = {9, 3, 7, 1, 8, 2};
quickSort(data, 0, data.size() - 1);
// Результат: 1 2 3 7 8 9

Бинарный поиск (Binary Search)

Один из самых эффективных алгоритмов поиска для отсортированных данных. В STL он реализован как std::binary_search и std::lower_bound.

#include <algorithm>
#include <vector>

std::vector<int> sorted = {1, 3, 5, 7, 9, 11, 13};

// Проверка существования
bool found = std::binary_search(sorted.begin(), sorted.end(), 7); // true

// Поиск первого элемента, не меньшего заданного
auto it = std::lower_bound(sorted.begin(), sorted.end(), 6);
if (it != sorted.end()) {
    std::cout << "Первый элемент >= 6: " << *it; // 7
}

3. Хеш-таблицы и ассоциативные контейнеры

Хеш-таблицы обеспечивают поиск, вставку и удаление в среднем за O(1). В C++ для этого используются std::unordered_map и std::unordered_set.

std::unordered_map — словарь на практике

Этот контейнер незаменим для подсчёта частоты элементов, кэширования или создания справочников.

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    std::unordered_map<std::string, int> wordCount;
    std::string text = "cpp python cpp java python cpp";
    
    // Разбиваем строку на слова и считаем
    std::string word;
    for (char ch : text) {
        if (ch == ' ') {
            wordCount[word]++; // Если ключа нет, он создаётся
            word.clear();
        } else {
            word += ch;
        }
    }
    if (!word.empty