STL-контейнеры (list, forward_list, stack, deque, queue, priority_queue)

1. STL-контейнеры (list, forward_list, stack, deque, queue, priority_queue)

2. Вспомним и повторим

Контейнер – способ хранения набора объектов в памяти.
STL (Standard Template Library) – это библиотека стандартных шаблонов, содержащая контейнеры,
алгоритмы и итераторы. Контейнеры STL предназначены для хранения и управления коллекциями
данных.
Типы STL-контейнеров:
1. vector
2. iterator
3. span
4. array
5. set
6. map
7. list
8. forward_list
9. stack
10. deque
11. queue
12. priority_queue
и другие…
1

3. list

– pop_back()
– pop_front()
– insert(pos, value)
– удалить последний элемент
– удалить первый элемент
–
– вставить элемент перед итератором
pos
erase(pos) – удалить элемент по итератору
– remove(value)
– удалить все элементы с заданным значением
list
list – это двусвязный список из библиотеки STL.
Каждый элемент хранит ссылки на предыдущий и
следующий элементы. Для работы с векторами
необходимо включить заголовок:
#include <list>
Основные методы:
push_back(val) – добавить val в конец
push_front(val) – добавить val в начало
pop_back() – удалить последний элемент
pop_front() – удалить первый элемент
insert(pos, val) – вставить val перед pos
erase(pos) – удалить элемент по итератору
clear() – удалить все элементы
sort() – отсортировать элементы списка
begin() – итератор на первый элемент
end() – итератор за последним элементом
void printList(std::list<int> numbers) {
std::cout << "List elements: ";
for (int n : numbers)
std::cout << n << " ";
std::cout << "\n";
}
int main() {
std::list<int> numbers = { 5, 2, 9 };
numbers.push_front(1); // добавить 1 в начало
numbers.push_back(10); // добавить 10 в конец
printList(numbers);
// отсортировать список
numbers.sort();
printList(numbers);
// удалить все элементы со значением 5
numbers.remove(5);
printList(numbers);
numbers.pop_front(); // удалить первый элемент
numbers.pop_back(); // удалить последний элемент
printList(numbers);
return 0;
}
4

4. forward_list

forward_list – это это однонаправленный список. В нем
каждый элемент знает только о следующем элементе (нет
указателя на предыдущий).
#include <forward_list>
Основные методы:
push_front(value) – добавить элемент в начало
pop_front() – удалить первый элемент
insert_after(pos, value) – вставить элемент после итератора
pos
erase_after(pos) – удалить элемент после итератора pos
remove(value) – удалить все элементы с указанным
значением
sort() – отсортировать список по возрастанию
merge(other_list) – слить с другим списком
reverse() – перевернуть порядок элементов
clear() – удалить все элементы списка
void printList(std::forward_list<int> numbers) {
std::cout << "List elements: ";
for (int n : numbers)
std::cout << n << " ";
std::cout << "\n";
}
int main() {
std::forward_list<int> numbers = { 3, 1, 4 };
numbers.push_front(5); // Добавить 5 в начало
printList(numbers);
// Сортировать список
numbers.sort();
printList(numbers);
// Вставить 7 после первого элемента
auto it = numbers.begin();
numbers.insert_after(it, 7);
printList(numbers);
// Удалить все элементы равные 3
numbers.remove(3);
printList(numbers);
return 0;
}
5

5. stack

stack – это структура данных, которая работает по принципу
LIFO, "последний пришел — первый ушел". Элемент,
добавленный в стек последним, будет извлечён первым. Для
работы с ним необходимо включить заголовок:
int main() {
std::stack<int> s;
s.push(10);
s.push(20);
s.push(30);
#include <stack>
Основные методы:
push(value) – положить элемент на вершину стека
pop() – удалить верхний элемент
top() – получить доступ к верхнему элементу
empty() – проверить, пуст ли стек
size() – вернуть количество элементов в стеке
emplace(args) – эффективно создать элемент на вершине
std::cout << "Top element: "
<< s.top() << "\n"; // 30
s.pop(); // Убираем 30
std::cout << "After pop, new top: "
<< s.top() << "\n"; // 20
std::cout << "Stack size: " << s.size() << "\n";
if (!s.empty())
std::cout << "Stack is not empty.\n";
return 0;
}
6

6. Задача

Напишите программу, которая хранит список посылок. Каждая посылка – это объект класса
Package, содержащий: идентификатор, пункт назначения, вес (в кг), флаг срочности.
Необходимо реализовать следующий функционал:
1. Все посылки хранить в std::list и далее их вывести в консоль.
2. Найти самую тяжёлую и самую лёгкую посылку и вывести.
3. Рассчитать общий вес посылок к отправке.
4. Срочные посылки отдельно сохранять в std::forward_list и исключить их из списка.
5. Удалить из оставшихся посылок те, у которых пункт назначения, например, "Москва".
6. После удаления подготовить посылки к отправке (поместить в std::stack).
7. Выгрузить посылки на отправку (извлечь посылки из std::stack и вывести в консоль).
7

7. queue

queue – это структура данных, которая работает по
принципу FIFO, "первый пришел — первый ушел".
Элемент, добавленный в очередь первым, будет извлечен
первым. Для работы с ним необходимо включить заголовок:
int main() {
std::queue<int> q;
q.push(10);
q.push(20);
q.push(30);
#include <queue>
std::cout << "First element: "
<< q.front() << "\n"; // 10
std::cout << "Last element: "
<< q.back() << "\n";
// 30
Основные методы:
push(value) – добавить элемент в конец очереди
pop() – удалить элемент из начала очереди
front() – получить первый элемент (в начале очереди)
back() – получить последний элемент (в конце очереди)
empty() – проверить, пуста ли очередь
size() – вернуть количество элементов в очереди
q.pop(); // Удаляем 10
std::cout << "After pop, new first element: "
<< q.front() << "\n"; // 20
std::cout << "Queue size: " << q.size() << "\n";
if (!q.empty())
std::cout << "Queue is not empty.\n";
return 0;
}
8

8. deque

deque (двусторонняя очередь) – это структура данных, int main() {
std::deque<int> dq = { 2, 4, 6 };
которая представляет собой очередь с возможностью
dq.push_front(1); // Добавить в начал
добавления и удаления элементов с обоих концов. Для
dq.push_back(8); // Добавить в конец
работы с ним необходимо включить заголовок:
std::cout << "Deque elements: ";
for (int n : dq)
std::cout << n << " ";
std::cout << "\n";
#include <deque>
Основные методы:
push_back(value) – добавить элемент в конец
push_front(value) – добавить элемент в начало
pop_back() – удалить элемент с конца
pop_front() – удалить элемент с начала
erase(pos) – удалить элемент по итератору
clear() – удалить все элементы из контейнера
operator[] – доступ к элементу по индексу
front() – доступ к первому элементу
back() – доступ к последнему элементу
dq.pop_front(); // Удалить первый элемент
dq.pop_back(); // Удалить последний элемент
std::cout << "After pops: ";
for (int n : dq)
std::cout << n << " ";
std::cout << "\n";
std::cout << "First element: " << dq.front() << "\n";
std::cout << "Last element: " << dq.back() << "\n";
return 0;
}
9

9. priority_queue

priority_queue (очередь с приоритетом) — это абстрактная
структура данных, которая работает аналогично обычной
очереди, но с дополнительным условием: каждый элемент
имеет приоритет, и элементы с более высоким приоритетом
извлекаются раньше, независимо от порядка их
добавления. Для работы с ним необходимо включить
заголовок:
#include <queue>
Основные методы:
push(value) – добавить элемент в очередь
pop() – удалить элемент с самым высоким приоритетом
top() – получить элемент с самым высоким приоритетом
empty() – проверить, пуста ли очередь
size() – вернуть количество элементов
int main() {
std::priority_queue<int> pq;
pq.push(30);
pq.push(10);
pq.push(40);
pq.push(20);
std::cout << "Top element: "
<< pq.top() << "\n"; // 40
pq.pop(); // Убираем 40
std::cout << "New top after pop: "
<< pq.top() << "\n"; // 30
std::cout << "Priority queue size: "
<< pq.size() << "\n";
return 0;
}
10

10. Задача

Напишите программу для обработки пассажирских очередей в аэропорту. Каждый пассажир
описывается классом Passenger, содержащим: имя, пункт назначения, флаг vip клиента, количество
багажа.
Необходимо реализовать следующий функционал:
1. Все пассажиры хранятся в std::vector.
2. Регистрация пассажиров:
1. Добавить обычных пассажиров в std::queue.
2. vip-пассажиров в std:priority_queue.
3. Рассчитать количество VIP и обычных пассажиров.
4. Организовать посадку используя std::deque. Сначала идут пассажиры, которые имеют vip и у
которых меньше всего багажа. Далее идут обычные граждане.
5. Исключить пассажиров, летящих в определенных город, например, "Москва". (Имулировать
задержу рейса)
6. Подсчитать, сколько пассажиров летящих в каждый город.
7. Вывести список пассажиров в порядке посадки.
11

11. Отличия контейнеров

11

12. Сложность алгоритмов

11

13. Спасибо за внимание!