Посібник по STL C++: Найчастіше використовувані контейнери та алгоритми STL - javascript.org.ua

Стандартна бібліотека шаблонів (STL) — потужна колекція повторно використовуваних компонентів, яка підвищує ефективність і стислий код у C++. STL надає контейнери (структури даних), алгоритми, ітератори та функції, всі з яких працюють безперешкодно разом. У цьому посібнику ми розглянемо найбільш часто використовувані контейнери та алгоритми STL з практичними прикладами та випадками використання.

Що таке C++ STL?

STL — це бібліотека шаблонних класів і функцій, яка реалізує стандартні структури даних і алгоритми. Замість того, щоб писати алгоритм сортування або динамічний масив з нуля, ви можете використовувати вбудовані компоненти, такі як vector і sort(), щоб спростити ваш код і зберегти ефективність.

Контейнери STL

Контейнери використовуються для зберігання колекцій даних. Вони поділяються на чотири типи:

1. Контейнери послідовностей

Ці контейнери зберігають елементи в лінійній послідовності.

Vector

Опис: Динамічний масив, який підтримує швидкий випадковий доступ.
Кращий випадок використання: Коли потрібен частий доступ за індексом і динамічне змінення розміру.
Загальні функції:
- push_back(), pop_back() — Додавати/видаляти елементи з кінця (O(1)).
- size() — Отримати кількість елементів.
- insert(), erase() — Модифікація елементів (O(n) для операцій у середині).
Приклад:

#include   
using namespace std;  
int main() {  
 vector v = {10, 20, 30};  
 v.push_back(40); // [10, 20, 30, 40]  
 v.pop_back(); // [10, 20, 30]  
 int x = v[1]; // 20  
}

List

Опис: Подвійно зв'язаний список, оптимізований для вставок і видалень.
Кращий випадок використання: Часті вставки/видалення в середині послідовності.
Загальні функції:
- push_front(), push_back() — Додавати елементи (O(1)).
- pop_front(), pop_back() — Видаляти елементи (O(1)).
- insert(), erase() — Модифікація елементів (O(1) після знаходження позиції).
Приклад:

#include   
list l = {1, 2, 3};  
l.push_front(0); // [0, 1, 2, 3]  
l.remove(2); // [0, 1, 3]

Deque (Двостороння черга)

Опис: Дозволяє ефективно виконувати вставки/видалення з обох кінців.
Кращий випадок використання: Коли часто потрібні операції як з передньою, так і з задньою частинами.
Приклад:

#include   
deque dq = {10, 20};  
dq.push_front(5); // [5, 10, 20]  
dq.pop_back(); // [5, 10]

2. Ассоціативні контейнери (упорядковані)

Елементи зберігаються в упорядкованому вигляді (за замовчуванням за зростанням).

Set

Опис: Зберігає унікальні елементи в упорядкованому вигляді (реалізовано за допомогою збалансованого двійкового дерева пошуку).
Кращий випадок використання: Коли потрібна колекція унікальних елементів у відсортованому порядку.
Приклад:

#include   
set s = {5, 3, 1};  
s.insert(4); // {1, 3, 4, 5}  
auto it = s.find(3); // Повертає ітератор на 3

Map

Опис: Зберігає пари ключ-значення, відсортовані за ключами.
Кращий випадок використання: Реалізація структури даних, схожої на словник.
Приклад:

#include   
map m;  
m["Alice"] = 25;  
m.insert({"Bob", 30});

Multiset та Multimap

Опис: Як set і map, але дозволяє дублікати ключів.
Приклад:

multiset ms = {1, 1, 2}; // {1, 1, 2}  
multimap mm;  
mm.insert({"Alice", 25});  
mm.insert({"Alice", 26}); // Обидва записи збережені

3. Невпорядковані ассоціативні контейнери

Елементи зберігаються за допомогою хешування (немає гарантії порядку, середній час доступу O(1)).

Unordered Set та Map

Кращий випадок використання: Швидкі пошуки, де порядок не важливий.
Приклад:

#include   
unordered_set us = {3, 1, 2}; // Зберігається в будь-якому порядку

4.

Контейнерні адаптери

Ці адаптери обмежують операції існуючих контейнерів.

Стек (LIFO)

Кращий випадок використання: Операції "останній увійшов — перший вийшов" (LIFO).
Приклад:

#include   
stack s;  
s.push(10);  
s.pop();

Черга (FIFO)

Кращий випадок використання: Операції "перший увійшов — перший вийшов" (FIFO).
Приклад:

#include   
queue q;  
q.push(10);  
q.pop();

Черга з пріоритетами

Опис: За замовчуванням максимальна купа (найбільший елемент на верху).
Кращий випадок використання: Планування завдань за пріоритетами.
Приклад:

priority_queue pq;  
pq.push(3); // [3]  
pq.push(5); // [5, 3]  
pq.top(); // 5

Алгоритми STL

Заголовок `` надає потужні вбудовані алгоритми.

sort()

Використання: Сортує елементи в діапазоні.
Приклад:

#include   
vector v = {5, 3, 1, 4};  
sort(v.begin(), v.end()); // [1, 3, 4, 5]

minelement() & maxelement()

Використання: Знаходить найменший/найбільший елемент у діапазоні.
Приклад:

auto min_it = min_element(v.begin(), v.end());  
cout << *min_it; // Виводить 1

next_permutation()

Використання: Генерує наступну лексикографічну перестановку.
Приклад:

string s = "aba";  
next_permutation(s.begin(), s.end()); // "baa"

Висновок

STL C++ — це важливий набір інструментів для написання ефективного та читабельного коду. Освоївши основні контейнери, такі як vector, map та unordered_set, а також алгоритми, такі як sort() і next_permutation(), ви зможете значно підвищити свою продуктивність. Почніть практикувати сьогодні, щоб розкрити всю потужність STL!

Перекладено з: C++ STL Tutorial: Most Frequently Used STL Containers & Algorithms