Структуры данных Standard Template Library. stack, unordered_map, unordered_set, unordered_multimap. Занятие 55. 9-11 классы

1.

9-11 классы
Программирование
на C++
Презентация занятия
Структуры данных Standard Template Library. stack,
unordered_map, unordered_set, unordered_multimap,
unordered_multiset.
55 занятие
2023

2.

Программирование
на C++
Теоретическая часть
Структуры данных Standard Template Library. stack,
unordered_map, unordered_set, unordered_multimap,
unordered_multiset.
55 занятие
2023

3.

Программирование
на C++
Standard Template Library
Структуры данных Standard Template Library. stack,
unordered_map, unordered_set, unordered_multimap,
unordered_multiset.
55 занятие
2023

4.

1
Тема: Standard Template Library.
STL
Основные термины
Контейнеры (Containers)
Итераторы (Iterators)
Алгоритмы (Algorithms)
Функциональные объекты (Function Objects)
Адаптеры (Adapters)
Функции-предикаты (Predicate Functions)
Выделители (Allocators)
Строки (Strings)
Исключения (Exceptions)
inginirium.ru

5.

2
Тема: Standard Template Library.
Пример подключения контейнеров:
#include <stack>
#include <unordered_map>
#include <unordered_set>
// Для использования стека (stack)
// Для использования
// неупорядоченного словаря (unordered_map)
// Для использования
// неупорядоченного множества (unordered_set)
#include <string>
int main() {
std::stack<int> myStack;
std::unordered_map<int, std::string> myMap;
std::unordered_set<int> mySet;
std::unordered_multimap<int, std::string> myMultiMap;
std::unordered_multiset<int> myMultiSet;
// Далее можно использовать соответствующие
// контейнеры и выполнять операции над ними
return 0;
}
inginirium.ru

6.

Программирование
на C++
stack
Структуры данных Standard Template Library. stack,
unordered_map, unordered_set, unordered_multimap,
unordered_multiset.
55 занятие
2023

7.

3
Тема: Standard Template Library. stack.
Last-In-First-Out, LIFO
inginirium.ru

8.

4
Тема: Standard Template Library. stack.
Пример использования std::stack:
#include <iostream>
#include <stack>
int main() {
std::stack<int> myStack;
myStack.push(10);
myStack.push(20);
myStack.push(30);
std::cout << "Size of the stack: " << myStack.size() << std::endl;
if (myStack.empty()) {
std::cout << "Stack is empty." << std::endl;
}
else {
std::cout << "Stack is not empty." << std::endl;
}
// ...
inginirium.ru

9.

5
Тема: Standard Template Library. stack.
std::cout << "Top element of the stack: " << myStack.top() << std::endl;
myStack.pop();
std::cout << "Elements in the stack: ";
while (!myStack.empty()) {
std::cout << myStack.top() << " ";
myStack.pop();
}
std::cout << std::endl;
return 0;
}
inginirium.ru

10.

Программирование
на C++
Задача
Структуры данных Standard Template Library. stack,
unordered_map, unordered_set, unordered_multimap,
unordered_multiset.
55 занятие
2023

11.

6
Задача: Правильная скобочная последовательность
Time limit 1000 ms
Mem limit 124928 kB
Дана скобочная последовательность, состоящая из трех типов скобок ( ), [ ], { }.
Определить, является ли она правильной.
Входные данные
Строка содержит скобочную последовательность, длина которой не превышает
255 символов.
Выходные данные
Вывести "yes", если последовательность правильная, и "no" в противном случае.
Sample 1
Input
Output
()
yes
Sample 2
Input
Output
(}]
no
inginirium.ru

12.

Программирование
на C++
Решение
Структуры данных Standard Template Library. stack,
unordered_map, unordered_set, unordered_multimap,
unordered_multiset.
55 занятие
2023

13.

7
Задача: Правильная скобочная последовательность
#include <iostream>
#include <stack>
int main()
{
std::string str;
std::cin >> str;
std::stack<char> s1;
for (size_t i = 0; i < str.length(); i++)
{
// ...
}
if (s1.empty()) {
std::cout << "yes";
}
else {
std::cout << "no";
}
return 0;
}
inginirium.ru

14.

8
Задача: Правильная скобочная последовательность
for (size_t i = 0; i < str.length(); i++)
{
if (str[i] == '(' || str[i] == '{' || str[i] == '[') {
s1.push(str[i]);
}
else {
if (!s1.empty())
// switch (str[i])
else
{
std::cout << "no";
return 0;
}
}
}
inginirium.ru

15.

9
Задача: Правильная скобочная последовательность
if (!s1.empty())
switch (str[i])
{
case ')’:
if (s1.top() == '(‘)
s1.pop();
break;
case '}’:
if (s1.top() == '{‘)
s1.pop();
break;
case ']’:
if (s1.top() == '[‘)
s1.pop();
break;
}
else
{
std::cout << "no";
return 0;
}
inginirium.ru

16.

Программирование
на C++
Хэш-таблицы
Структуры данных Standard Template Library. stack,
unordered_map, unordered_set, unordered_multimap,
unordered_multiset.
55 занятие
2023

17.

10
inginirium.ru

18.

Программирование
на C++
unordered_map
unordered_set
Структуры данных Standard Template Library. stack,
unordered_map, unordered_set, unordered_multimap,
unordered_multiset.
55 занятие
2023

19.

11
Тема: Standard Template Library. unordered_map/unordered_set.
Открытая адресация:
data
X
X
- занято
- свободно
inginirium.ru

20.

12
Тема: Standard Template Library. unordered_map/unordered_set.
Метод цепочек:
data1
data2
data3
inginirium.ru

21.

13
Тема: Standard Template Library. unordered_map/unordered_set.
bucket
data1
data2
data3
bucket_count
load_factor = size / bucket_count
inginirium.ru

22.

14
Тема: Standard Template Library. unordered_map/unordered_set.
#include <iostream>
#include <unordered_map>
#include <string>
int main() {
// Создание unordered_map с именами и возрастами
std::unordered_map<std::string, int> ageMap;
// Добавление элементов в unordered_map
ageMap["Alice"] = 25;
ageMap["Bob"] = 30;
ageMap["Charlie"] = 35;
// Получение и вывод значения по ключу
std::cout << "Age of Alice: " << ageMap["Alice"] << std::endl;
// Проверка наличия ключа
if (ageMap.count("Bob") > 0) {
std::cout << "Bob's age exists in the unordered_map." << std::endl;
}
// ...
inginirium.ru

23.

15
Тема: Standard Template Library. unordered_map/unordered_set.
// Итерация по элементам unordered_map
std::cout << "Elements in ageMap:" << std::endl;
for (const auto& pair : ageMap) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
// Удаление элемента по ключу
ageMap.erase("Charlie");
return 0;
}
inginirium.ru

24.

Программирование
на C++
Задание
Структуры данных Standard Template Library. stack,
unordered_map, unordered_set, unordered_multimap,
unordered_multiset.
55 занятие
2023

25.

16
Тема: Standard Template Library. unordered_map/unordered_set.
Задание:
Измените данный код так, чтобы хранился только возраст.
Используйте std::unordered_set.
inginirium.ru

26.

Программирование
на C++
Решение
Структуры данных Standard Template Library. stack,
unordered_map, unordered_set, unordered_multimap,
unordered_multiset.
55 занятие
2023

27.

17
Тема: Standard Template Library. unordered_map/unordered_set.
#include <iostream>
#include <unordered_set>
int main() {
// Создание unordered_set для хранения возрастов
std::unordered_set<int> ageSet;
// Добавление элементов в unordered_set
ageSet.insert(25);
ageSet.insert(30);
ageSet.insert(35);
// Проверка наличия элемента
if (ageSet.count(30) > 0) {
std::cout << "Age 30 exists in the unordered_set." << std::endl;
}
// ...
inginirium.ru

28.

18
Тема: Standard Template Library. unordered_map/unordered_set.
// Итерация по элементам unordered_set
std::cout << "Elements in ageSet:" << std::endl;
for (const auto& age : ageSet) {
std::cout << age << std::endl;
}
// Удаление элемента
ageSet.erase(35);
return 0;
}
inginirium.ru

29.

Программирование
на C++
unordered_multimap
unordered_multiset
Структуры данных Standard Template Library. stack,
unordered_map, unordered_set, unordered_multimap,
unordered_multiset.
55 занятие
2023

30.

19
Тема: Standard Template Library. unordered_multimap/unordered_multiset.
#include <iostream>
#include <unordered_map>
#include <string>
int main() {
std::unordered_multimap<std::string, std::string> studentSubjects;
// Добавление пар ключ-значение в unordered_multimap
studentSubjects.insert({ "Alice", "Math" });
studentSubjects.insert({ "Alice", "Physics" });
studentSubjects.insert({ "Bob", "Computer Science" });
studentSubjects.insert({ "Bob", "Physics" });
// Итерация по элементам unordered_multimap
std::cout << "Student Subjects:" << std::endl;
for (const auto& pair : studentSubjects) {
std::cout << "Student: " << pair.first << ", Subject: " << pair.second << std::endl;
}
return 0;
}
inginirium.ru

31.

Программирование
на C++
equal_range
Структуры данных Standard Template Library. stack,
unordered_map, unordered_set, unordered_multimap,
unordered_multiset.
55 занятие
2023

32.

20
Тема: Standard Template Library. unordered_multimap/unordered_multiset.
#include <iostream>
#include <unordered_map>
int main()
{
std::unordered_multimap<int, int> sample;
sample.insert({ 1, 2 });
sample.insert({ 1, 2 });
sample.insert({ 2, 3 });
sample.insert({ 3, 4 });
sample.insert({ 2, 6 });
auto itr = sample.equal_range(1);
std::cout << "Elements with Key 1: ";
for (auto it = itr.first; it != itr.second; it++) {
std::cout << it->second << " ";
}
// ...
inginirium.ru

33.

21
Тема: Standard Template Library. unordered_multimap/unordered_multiset.
std::cout << std::endl;
itr = sample.equal_range(2);
std::cout << "Elements with Key 2: ";
for (auto it = itr.first; it != itr.second; it++) {
std::cout << it->second << " ";
}
return 0;
}
inginirium.ru

34.

Программирование
на C++
Задание
Структуры данных Standard Template Library. stack,
unordered_map, unordered_set, unordered_multimap,
unordered_multiset.
55 занятие
2023

35.

22
Тема: Standard Template Library. unordered_map/unordered_set.
Задание:
Измените данный код так, чтобы хранилось одно значение.
Используйте std::unordered_multiset.
inginirium.ru

36.

Программирование
на C++
Задача
Структуры данных Standard Template Library. stack,
unordered_map, unordered_set, unordered_multimap,
unordered_multiset.
55 занятие
2023

37.

23
Задача: Сумма трех
Time limit 1000 ms
Mem limit 524288 kB
Вам дается массив из n целых чисел, и ваша задача - найти три значения (в разных
позициях), сумма которых равна x.
Входные данные
Первая строка ввода содержит два целых числа n и x: размер массива и целевую
сумму. Вторая строка содержит n целых чисел