C++: контейнеры STL и алгоритмы

Контейнеры STL и их сложность, vector, list, map, set, unordered_map, итераторы, алгоритмы sort и find, лямбда-выражения, умные указатели.

STL избавляет от написания структур данных вручную. В курсовой это стоит подчёркивать: правильный выбор контейнера — инженерное решение, которое обосновывают сложностью операций.

Контейнеры и их сложность

vector

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

vector<int> v = {5, 3, 8, 1, 9, 2};

v.push_back(7);            // добавить в конец
v.reserve(100);            // заранее выделить память — избежать перевыделений
cout << v.size() << ' ' << v.capacity() << '\n';

// Доступ
v[0];                      // без проверки границ, быстро
v.at(0);                   // с проверкой, бросает out_of_range
v.front(); v.back();

// Обход
for (int x : v) cout << x << ' ';
for (auto it = v.begin(); it != v.end(); ++it) cout << *it << ' ';

// Удаление по значению — идиома erase-remove
v.erase(remove(v.begin(), v.end(), 8), v.end());

// Двумерный вектор
vector<vector<int>> matrix(3, vector<int>(4, 0));
matrix[1][2] = 5;

Вызов reserve перед заполнением большого вектора заметно ускоряет работу: без него при каждом переполнении происходит выделение новой памяти и копирование всех элементов. Для миллиона вставок разница достигает нескольких раз.

Ассоциативные контейнеры

#include <map>
#include <unordered_map>
#include <set>
#include <string>

map<string, int> counts;              // отсортирован по ключу
counts["алгоритм"]++;                 // создаст с нулём и увеличит
counts.insert({"структура", 5});

// Поиск без создания элемента
if (auto it = counts.find("дерево"); it != counts.end())
    cout << it->second;

// Обход: у map — по возрастанию ключа
for (const auto& [word, n] : counts)
    cout << word << ": " << n << '\n';

unordered_map<string, int> fast;       // O(1), но порядок произвольный

set<int> unique_values = {5, 3, 8, 3, 5};   // остаётся {3, 5, 8}
multiset<int> with_dups = {5, 3, 5};        // допускает повторы

// Подсчёт частот слов — классическая задача курсовой
map<string, int> freq;
string word;
while (cin >> word) freq[word]++;

Алгоритмы

#include <algorithm>
#include <numeric>

vector<int> v = {5, 3, 8, 1, 9, 2};

sort(v.begin(), v.end());                        // по возрастанию
sort(v.begin(), v.end(), greater<int>());        // по убыванию
sort(v.begin(), v.end(), [](int a, int b) {      // свой критерий
    return abs(a) < abs(b);
});

auto it = find(v.begin(), v.end(), 8);
bool found = binary_search(v.begin(), v.end(), 8);   // только для сортированного

int total = accumulate(v.begin(), v.end(), 0);
int maxv  = *max_element(v.begin(), v.end());
int cnt   = count_if(v.begin(), v.end(), [](int x) { return x > 4; });

// Преобразование
vector<int> squares(v.size());
transform(v.begin(), v.end(), squares.begin(), [](int x) { return x * x; });

// Разделение по условию
auto mid = partition(v.begin(), v.end(), [](int x) { return x % 2 == 0; });

reverse(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());    // убрать соседние дубликаты

Структуры в контейнерах

struct Student {
    string name;
    int course;
    double grade;
};

vector<Student> group = {
    {"Иванов", 3, 4.5},
    {"Петров", 2, 3.8},
    {"Сидоров", 3, 4.9},
};

// Сортировка по нескольким полям
sort(group.begin(), group.end(), [](const Student& a, const Student& b) {
    if (a.course != b.course) return a.course < b.course;
    return a.grade > b.grade;
});

// Отбор
vector<Student> honors;
copy_if(group.begin(), group.end(), back_inserter(honors),
        [](const Student& s) { return s.grade >= 4.5; });

// Среднее
double avg = accumulate(group.begin(), group.end(), 0.0,
    [](double sum, const Student& s) { return sum + s.grade; }) / group.size();

// Для использования в set нужен оператор сравнения
struct ByName {
    bool operator()(const Student& a, const Student& b) const {
        return a.name < b.name;
    }
};
set<Student, ByName> sorted_students(group.begin(), group.end());

Умные указатели

#include <memory>

// Было: ручное управление, легко забыть delete
Node* p = new Node(5);
delete p;                        // а при исключении между строк — утечка

// Стало: память освобождается автоматически
auto up = make_unique<Node>(5);           // единственный владелец
auto sp = make_shared<Node>(5);           // подсчёт ссылок
weak_ptr<Node> wp = sp;                   // не удерживает объект

// Дерево на умных указателях
struct TreeNode {
    int value;
    unique_ptr<TreeNode> left, right;
    explicit TreeNode(int v) : value(v) {}
};

void insert(unique_ptr<TreeNode>& root, int v) {
    if (!root) { root = make_unique<TreeNode>(v); return; }
    insert(v < root->value ? root->left : root->right, v);
}

Умные указатели — обязательный элемент современного C++. В курсовой их применение показывает знакомство со стандартом C++11 и выше; ручные new и delete в новом коде считаются признаком устаревшего стиля.

Как выбрать контейнер

1. Нужен доступ по индексу и последовательный обход — vector.
2. Часто вставляете и удаляете в середине по известной позиции — list.
3. Нужен поиск по ключу и порядок обхода — map или set.
4. Порядок не важен, а скорость поиска критична — unordered_map или unordered_set.
5. Нужно всегда извлекать минимум или максимум — priority_queue.
6. Вставки с двух концов — deque.