Стандартная библиотека С++

1.

ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ
ПРОГРАММИРОВАНИЕ
Тема 3.
Стандартная библиотека С++.

2.

Понятие стандартной библиотеки
Стандартная библиотека – это коллекция классов и функций,
написанная на базовом языке.
Структура стандартной библиотеки С++
Ввод-вывод (iostream, fstream, iomanip, sstream и др.)
Многопоточность (mutex, thread и др.)
Обобщенные алгоритмы и вспомогательные классы (string, algorithm, numeric,
complex, exception и др.)
Стандартная библиотека шаблонов
Стандартная библиотека языка Си (cstdio, cstdlib, cctype и др.)

3.

Строки в С++
Строки С – массив символов char[]
Строки С++ - отдельный класс string
Этапы изучения строк С++
Базовые принципы работы со строками
Функции сравнения
Способы конвертации строк
Функции поиска

4.

Строки в С++. Базовые принципы работы со строками
#include <string>// Заголовочный файл для работы со строками
using namespace std;
int main() {
string
s1 = "Hello, world!",// Присвоение значения
s2("Hello, world"),// Инициализация с помощью конструктора
s3;// Неинициализированная переменная
s3 = s1 + "Some text"; // Конкатенация
int len = s3.length(); // Длина строки
const char *str = s3.data(); // Переход к указателям.
// Здесь принципиально использование const
s1 = s2.substr(3, 2);
// Возвращает подстроку строки s2 длиной 2,
// начиная с позиции 3
// Подсчет количества букв 'o' в строке s3
int o_count = 0;
for (int i = 0; i < s3.length(); ++i) // Индексация строки начинается с нуля
if (s3[i] == 'o') o_count++; // Получение символа в позиции i
return 0;
}

5.

Строки в С++. Ввод/вывод строк
С помощью операций ввода из потока и вывода в поток – считывание
осуществляется до первого символа пробела, конца строки или конца потока
С помощью функции getline – считывание осуществляется до конца строки или
конца потока
#include <iostream>
#include <string>
#include <iostream>
#include <string>
using namespace std;
using namespace std;
int main() {
string s1, s2;
int main() {
string s1, s2;
cin >> s1 >> s2;
getline(cin, s1);
getline(cin, s2);
cout << "First string: " << s1 << endl;
cout << "Second string: " << s2 << endl;
cout << "First string: " << s1 << endl;
cout << "Second string: " << s2 << endl;
return 0;
}
return 0;
}

6.

Строки в С++. Сравнение строк
Слово a предшествует слову b ( a < b ) в лексикографическом смысле, если
либо первые m символов этих слов совпадают, а (m + 1) -ый символ слова a
меньше (m + 1)-ого символа слова b
(например, abcab < abddddab, так как первые две буквы у этих слов совпадают, а
третья буква у первого слова меньше, чем у второго);
либо слово а является началом слова b (например, ab < abcd).
#include <iostream>
#include <string>
using namespace std;
int main() {
string s1, s2;
cin >> s1 >> s2;
if (s1 < s2) cout << "s1 < s2" << endl;
else if (s1 > s2) cout << "s1 > s2" << endl;
else if (s1 == s2) cout << "s1 == s2" << endl;
return 0;
}

7.

Строки в С++. Функции конвертации
Функция
Параметры
Тип
возвращаемого
значения
long int
#include <iostream>
#include <string>
unsigned int
using namespace std;
int
to_string
Пример
unsigned long long
string
double
int main() {
string str1, str2;
long double
str1 = "123";
int ni = stoi(str1);
str2 = to_string(ni);
float
stoi
int
stoui
unsigned int
stoll
long long
stoull
string
str1 = "10000000000"; //10^10
long long nll = stoll(str1);
str2 = to_string(nll);
unsigned long long
stod
double
stof
float
str1 = "1.5";
double d = stod(str1);
str2 = to_string(d);
return 0;
}

8.

Строки в С++. Использование строковых потоков
#include <iostream>
#include <sstream>
#include <string>
using namespace std;
int main() {
string str1, str2;
int n1, n2;
str1 = "12345 54321";
istringstream iss(str1);
iss >> n1 >> n2;
ostringstream oss;
oss << n1 << " " << n2;
str2 = oss.str();
return 0;
}

9.

Строки в С++. Функции поиска
Имя
Описание
size_t _(const string& str, size_t pos) const;
size_t _(const char* s, size_t pos) const;
size_t _(const char* s, size_t pos, size_type n) const;
size_t _(char c, size_t pos) const;
find
Поиск
первого вхождения строки или
символа в заданную строку
rfind
Поиск последнего вхождения строки или
символа в заданную строку
find_first_of
Поиск
первого вхождения одного из
символов строки или или индивидуального
символа в заданную строку
find_last_of
Поиск последнего вхождения одного из
символов строки или или индивидуального
символа в заданную строку

10.

Строки в С++. Функции поиска. Пример
#include <iostream>
#include <string>
using namespace std;
int main() {
string s = "dccdefcddc";
//----------0123456789--------------int pos = -1;
pos = s.find("cd", 0); // pos == 2
pos = s.find("cd", 7); // pos == -1
pos = s.rfind("cd", -1); // pos == 6
pos = s.find_first_of("cd", 0); // pos == 0
pos = s.find_last_of("cd", -1); // pos == 9
return 0;
}

11.

Стандартная библиотека шаблонов
Стандартная библиотека шаблонов (STL – Standard Template
Library) – это набор согласованных обобщённых алгоритмов,
контейнеров, средств доступа к их содержимому и различных
вспомогательных функций.
Компоненты STL
Контейнер – хранилище набора объектов в памяти
Итератор – компонент, обеспечивающий доступ к контейнерам
Алгоритм – вычислительная процедура обработки контейнеров
Адаптер – компонент, обеспечивающий некоторый интерфейс
Функциональный объект – компонент, обеспечивающий сокрытие функции
внутри объекта с целью дальнейшего использования в контейнерах

12.

Контейнеры
Контейнер – это объект, который содержит другие объекты
произвольного типа. Контейнер управляет распределением и
освобождением памяти под свои элементы.
Виды контейнеров
Последовательные контейнеры организуют хранение элементов одного типа в
строго линейном порядке (vector, list, deque).
Ассоциативные контейнеры организуют хранение элементов, оптимальное для
быстрого поиска данных по ключевым значениям (set, map).

13.

Итераторы
Итератор — это объект, который может выполнять итерацию элементов в
контейнере STL и предоставлять доступ к отдельным элементам. Все
контейнеры STL предоставляют итераторы, чтобы алгоритмы могли
получить доступ к своим элементам стандартным способом, независимо
от типа контейнера, в котором сохранены элементы.
Преимущества итераторов
Итераторы помогают систематизировать код и повышают коэффициент его повторного
использования, что повсеместно используется в контейнерах и алгоритмах STL
Итераторы могут предоставлять дополнительные возможности при навигации по
элементам. Например, проверку отсутствия пропусков элементов или защиту от
повторного перебора одного и того же элемента
Некоторые контейнеры могут предоставлять возможность модифицировать свои
объекты без влияния на сам итератор. Например, после того, как итератор уже
«прошёл» первый элемент, можно вставить дополнительные элементы в начало
контейнера без каких-либо нежелательных последствий

14.

Категории итераторов
Наименование
Описание
Итератор ввода
(input iterator)
Используется потоками ввода, может выполнить
итерацию последовательности и прочитать
элемент любое количество раз
(istream_iterator)
Итератор вывода
(output iterator)
Используется потоками вывода, может выполнить
итерацию последовательности и один раз
записать элемент
(ostream_iterator)
Однонаправленный итератор
(forward iterator)
Используется для прохода по элементам в одном
направлении, может выполнить итерацию
последовательности и прочитать любой элемент
или записать неконстантные элементы любое
количество раз
Двунаправленный итератор
(bidirectional iterator)
Используется для прохода по элементам в любом
направлении, может выполнить итерацию
последовательности в любом направлении и
прочитать любой элемент или записать
неконстантные элементы любое количество раз
(list, set, multiset, map, multimap)
Итератор произвольного доступа
(random access iterator)
Используется для получения доступа к любому
элементу массива
(vector, deque, string, array)

15.

Операции, доступные итераторам
Input
iterator
Output
iterator
Forward
iterator
Bidirectional
iterator
Random
access
iterator
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
it1 == it2
it1 != it2
+
+
+
+
it += val
it -= val
+
it1 < it2
it1 <= it2
it1 > it2
it1 >= it2
+
Операция
*it
*it = val
it++
it--

16.

Иерархия итераторов
Random access
iterator
Bidirectional
iterator
Forward
iterator
Input
iterator
Output
iterator

17.

Пример использования итераторов ввода/вывода
#include <iostream>
#include <iterator>
using namespace std;
int main() {
int a[3];
istream_iterator<int> ist(cin), eof;
for (int i = 0; i < 3; ++i, ist++)
if (ist != eof) a[i] = *ist;
copy(a, a + 3, ostream_iterator<int>(cout, "\n"));
return 0;
}

18.

Массивы в C++. Контейнер vector
vector – это последовательный контейнер, инкапсулирующий массивы
переменного размера.
Элементы хранятся непрерывно, а значит доступны не только через итераторы,
но и через смещения, добавляемые к указателям на элементы.
Тип итератора – random access iterator.
#include <vector>
using namespace std;
int main() {
vector<int>
a,
b(10),
c(15, 1);
// Пустой массив
// Неинициализированный массив из 10 элементов
// Массив из 15 элементов, заполненный единичками
// Доступ к элементам
int
c0 = c[0],
// По индексу через оператор []
c1 = c.at(1),
// По индексу через встроенный метод
c_front = c.front(), // Получение первого элемента массива
c_back = c.back();
// Получение последнего элемента массива
return 0;
}

19.

Контейнер vector. Базовые методы
Метод
Описание
begin()
end()
Получение итераторов
начала и конца вектора
соответственно
size()
Получение текущего
размера вектора
empty()
Проверка наличия в
векторе данных
(вернет true, если
вектор пуст)
clear()
push_back()
pop_back()
Пример использования
#include <vector>
#include <ctime>
using namespace std;
int main() {
srand(time(nullptr));
int n1 = rand() % 20, n2 = rand() % 10;
vector<int> a(n1, 0);
// Заполняем вектор случайными числами
for (vector<int>::iterator it = a.begin(); it != a.end(); it += 1)
*it = rand() % 100;
// Добавляем в конец n2 случайных числа
for (int i = 0; i < n2; ++i)
a.push_back(rand() % 100);
Очистка вектора
(удаление всех
элементов)
int n3 = rand() % a.size();
// Удаляем с конца n3 числа
for (int i = 0; i < n3; ++i)
a.pop_back();
Добавление элемента
в конец вектора и
удаление последнего
элемента вектора
соответственно
// Если вектор еще содержит элементы, очищаем его
if (!a.empty())
a.clear();
return 0;
}

20.

Двусвязные списки. Контейнер list
list – это последовательный контейнер, реализующий двусвязный список
произвольного размера.
Поддерживает быструю вставку и удаление элементов из любой позиции в
контейнере. Быстрый произвольный доступ не поддерживается.
Тип итератора – bidirectional iterator.
Вставка элемента перед текущим
Удаление текущего

21.

Контейнер list. Базовые методы
Метод
Описание
begin()
end()
Получение итераторов
начала и конца списка
соответственно
size()
Получение текущего
размера списка
empty()
Проверка наличия в
списке данных (вернет
true, если вектор пуст)
clear()
Очистка
списка(удаление всех
элементов)
push_back()
push_front()
insert()
Добавление элемента в
конец, начало и
произвольную позицию
списка соответственно
pop_back()
pop_front()
erase()
Удаление последнего,
первого и
произвольного
элемента списка
соответственно
Пример использования
#include <list>
#include <ctime>
using namespace std;
int main() {
srand(time(nullptr));
int n1 = rand() % 20, n2 = rand() % 10;
list<int> a(n1, 0);
for (auto it = a.begin(); it != a.end(); ++it)
*it = rand() % 100;
// Добавляем n2 случайных числа в произвольные позиции списка
for (int i = 0; i < n2; ++i) {
int pos = rand() % a.size();
auto it = a.begin();
advance(it, pos);
a.insert(it, rand() % 100); // Вставляем элемент перед pos
}
int n3 = rand() % a.size();
// Удаляем n3 числа
for (int i = 0; i < n3; ++i) {
int pos = rand() % a.size();
auto it = a.begin();
advance(it, pos);
a.erase(it);
}
return 0;
}

22.

Контейнер deque
deque (double-ended-queue) – это последовательный контейнер, реализующий
двустороннюю очередь произвольного размера.
Поддерживает быструю вставку и удаление элементов в начало и в конец.
Поддерживает произвольный доступ.
Тип итератора – random access iterator.

23.

Контейнер deque. Базовые методы
Метод
Описание
begin()
end()
Получение итераторов
начала и конца очереди
соответственно
size()
Получение текущего
размера очереди
empty()
Проверка наличия в
очереди данных (вернет
true, если вектор пуст)
clear()
Очистка очереди
(удаление всех
элементов)
push_back()
push_front()
insert()
Добавление элемента в
конец, начало и
произвольную позицию
очереди соответственно
pop_back()
pop_front()
erase()
Удаление последнего,
первого и
произвольного
элемента очереди
соответственно
Пример использования
#include <queue>
#include <ctime>
using namespace std;
int main() {
srand(time(nullptr));
int n1 = rand() % 20, n2 = rand() % 10;
deque<int> a(n1, 0);
for (auto it = a.begin(); it != a.end(); it += 1)
*it = rand() % 100;
// Добавляем элемент в начало очереди
a.push_front(rand() % 100);
// Добавляем элемент в конец очереди
a.push_back(rand() % 100);
// Удаляем элемент из начала очереди
a.pop_front();
// Удаляем элемент из конца очереди
a.pop_back();
return 0;
}

24.

Оценка сложности алгоритма. O-нотация
O-нотация – это система обозначений, предназначенная для оценки сложности
(количества операций, времени работы, объема потребляемой памяти)
алгоритма.
Фраза «сложность алгоритма есть O(f(n))» означает, что с увеличением
параметра n, характеризующего количество входной информации алгоритма,
время работы алгоритма будет возрастать не быстрее, чем некоторая константа,
умноженная на f(n).
Эта нотация позволяет учитывать в функции f(n) лишь наиболее значимые
элементы, отбрасывая второстепенные.
Примеры
Алгоритм
Сложность
по времени
Пример
Обращение по
индексу
O(1)
a[i] = val
Поиск
O(n)
for (int i = 0; i < n; ++i)
if (a[i] == val) return true;
Пузырьковая
сортировка
O(n2)
for (int i = 0; i < n; i++)
for (int j = n - 1; j > i; j--)
if (a[j] < a[j - 1]) swap(a[j], a[j - 1]);

25.

Сравнение последовательных контейнеров
Операция
Массив
Список
Двусторонняя очередь
Вставка в конец
Удаление из конца
O(1)
O(1)
O(1)
Вставка в начало
Удаление из начала
O(n)
O(1)
O(1)
Вставка в середину
Удаление из
середины
O(n)
O(1)
O(n)
Проход
O(n)
O(n)
O(n)
Доступ по индексу
O(1)
O(n)
O(1)
Поиск
O(n)
O(n)
O(n)

26.

Контейнер set
set – это контейнер, реализующий структуру данных «множество».
Хранит уникальные значения произвольного типа, отсортированные
возрастанию.
Тип итератора – bidirectional iterator.
n = 10
Количество узлов на i-м уровне – 2i
Количество уровней – log n ( log(10) ~ 4)
по
Операция
Множество
Вставка
O(log n)
Проход
O(n)
Доступ
O(log n)
Поиск
O(log n)

27.

Контейнер set. Базовые методы
Метод
Описание
begin()
end()
Получение итераторов
начала и конца
соответственно
size()
Получение текущего
размера
empty()
Проверка наличия в
контейнере данных
clear()
Очистка (удаление всех
элементов)
insert()
Добавление элемента в
произвольную позицию
по ключу и значению
erase()
Удаление
произвольного
элемента по ключу
count()
Пример использования
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s;
// Добавим в set элементы
for (int i = 0; i < 5; ++i) {
s.insert(1);
s.insert(2);
s.insert(3);
}
// Выведем элементы множества на экран
for (auto it = s.begin(); it != s.end(); ++it)
cout << "Set element: " << *it << endl;
// Удалим элемент по значению
s.erase(2);
cout << "New set size: " << s.size() << endl;
Подсчет количества
элементов по ключу
return 0;
}

28.

Контейнер map
map – это контейнер, реализующий ассоциативный массив.
Хранит пары {ключ, значение}. Ключ и значение могут иметь произвольные типы.
Тип итератора – bidirectional iterator.
n = 10
Количество узлов на i-м уровне – 2i
Количество уровней – log n ( log(10) ~ 4)
Операция
Множество
Вставка
O(log n)
Проход
O(n)
Доступ
O(log n)
Поиск
O(log n)

29.

Структура pair
pair – это предопределенная структура, содержащая пару значений заданных
типов.
#include <iostream>
using namespace std;
pair<int, int> p1, p2;
int main() {
p1 = { 1, 2 };
p2.first = 3;
p2.second = 4;
cout << p1.first << " " << p1.second << endl;
return 0;
}

30.

Контейнер map. Базовые методы
Метод
Описание
begin()
end()
Получение итераторов
начала и конца
соответственно
size()
Получение текущего
размера
Пример использования
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
map<string, int> age;
age["Ann"] = 20;
age["Chris"] = 25;
age.insert({"Bob", 22});
empty()
Проверка наличия в
контейнере данных
clear()
Очистка (удаление всех
элементов)
insert()
Добавление элемента в
произвольную позицию
по ключу и значению
for (auto it = age.begin(); it != age.end(); ++it) {
cout << "Name: " << it->first;
cout << ", age: " << it->second << endl;
}
erase()
Удаление
произвольного
элемента по ключу
age["Rand"]; // Вставить в map элемент без значения
if (age.count("Bill") == 0) age["Bill"] = 10;
count()
Подсчет количества
элементов по ключу
return 0;
}

31.

Алгоритмы стандартной библиотеки
Алгоритм – это вычислительная процедура обработки контейнера.
Виды алгоритмов
Микро-алгоритмы
Алгоритмы типа find
Алгоритмы, не модифицирующие контейнер
Модифицирующие алгоритмы

32.

Микро-алгоритмы
Прототип
Описание
swap
Меняет местами
два значения
(T &a, T &b)
iter_swap
(It p, It q)
max
(const T &a, const T &b)
Меняет местами
два элемента по
их итераторам
Возвращает
максимальное из
двух значений
Пример
#include <vector>
#include <algorithm>
#include <ctime>
using namespace std;
vector<int> a;
int n = 0;
int main() {
srand(time(nullptr));
n = rand() % 100;
if (n % 2) n++;
a.resize(n, 0);
for (int i = 0; i < a.size(); ++i)
a[i] = rand() % 100;
min
(const T &a, const T &b)
for (auto it = a.begin(); it != a.end(); it += 2)
{
if (*it == max(*it, *(it + 1)))
Возвращает
минимальное из
двух значений
iter_swap(it, it + 1);
}
return 0;
}

33.

Алгоритмы типа find
Прототип
Описание
find (It p, It q, const T &x)
Возвращает итератор на первое вхождение элемента x в
последовательность, заданную итераторами p и q
find_if (It p, It q, Pr pred)
Возвращает итератор на первый элемент, для которого
предикат pred вернул значение true
find_first_of (It p, It q, Itr i, Itr j)
Возвращает итератор на первое вхождение любого
элемента из последовательности, заданной итераторами
i и j, в последовательность, заданную итераторами p и q.
Последовательности могут быть разных типов
for_each (It p, It q, F func)
Для каждого элемента последовательности применяет
функтор func
binary_search (It p, It q, const T &x)
Возвращает true, если в упорядоченной
последовательности есть элемент, значение которого
равно x, false в противном случае
min_element (It p, It q)
max_element (It p, It q)
Возвращает итератор на минимальный и максимальный
элемент последовательности соответственно

34.

Алгоритмы типа find. Пример
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
using namespace std;
vector<int> a;
int n = 0;
void print(int val) {
cout << val << endl;
}
int main() {
srand(time(nullptr));
n = rand() % 100; a.resize(n);
for (int i = 0; i < a.size(); ++i)
a[i] = rand() % 100;
for_each(a.begin(), a.end(), print);
int max_val = *max_element(a.begin(), a.end());
int min_val = *min_element(a.begin(), a.end());
return 0;
}

35.

Алгоритмы, не модифицирующие контейнер
Прототип
Описание
size_t count
(It p, It q, const T &x)
Возвращает,
сколько раз
элемент со
значением x
входит в
последовательно
сть, заданную
итераторами p и
q
size_t count_if
(It p, It q, Pr pred)
Возвращает, для
какого количества
элементов
последовательно
сти, заданной
итераторами p и
q, предикат pred
возвращает
значение true.
Прототип
предиката:
Пример
#include <vector>
#include <algorithm>
#include <ctime>
using namespace std;
vector<int> a;
int n = 0;
bool is_even(int val) {
return val % 2 == 0;
}
int main() {
srand(time(nullptr));
n = rand() % 1000;
for (int i = 0; i < a.size(); ++i)
a[i] = rand() % 100;
int ten_count = count(a.begin(), a.end(), 10);
int even_count = count_if(a.begin(), a.end(), is_even);
bool (*Pred)(T val)
return 0;
}

36.

Модифицирующие алгоритмы
Прототип
Описание
fill (It p, It q, const T &x)
Заполняeт последовательность значениями, равными
значению x
generate (It p, It q, F gen)
Заполняет последовательность значениями,
сгенерированными функтором gen (например,
генератором случайных чисел)
copy (It p, It q, Itr out)
Копирует значения элементов последовательности,
заданной итераторами p и q, в последовательность,
начинающуюся с итератора out
reverse (It p, It q)
Переставляет элементы в обратном порядке
transform (It p, It q, Itr out, F func)
К каждому элементу входящей последовательности
применяет функтор func и записывает результат в
последовательность, начинающуюся с итератора out
accumulate (It p, It q, T i, F func)
Последовательно применяет бинарный функтор func к
парам (i, *p++), где i - некоторое начальное значение,
которое затем каждый раз заменяется значением,
которое возвращает функтор. Функтор должен
возвращать значение типа T
sort (It p, It q)
Сортирует элементы последовательности в порядке
возрастания

37.

Модифицирующие алгоритмы. Пример
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <ctime>
using namespace std;
vector<int> a, b;
int n = 0;
void print(int val) { cout << val << endl; }
int fun1(int val) { return val % 100; }
int main() {
srand(time(nullptr));
n = rand() % 100;
a.resize(n); b.resize(n);
generate(a.begin(), a.end(), rand);
copy(a.begin(), a.end(), b.begin());
transform(a.begin(), a.end(), a.begin(), fun1);
reverse(b.begin(), b.end());
sort(a.begin(), a.end());
int sum = accumulate(a.begin(), a.end(), 0);
return 0;
}

38.

Принципы создания обобщенного алгоритма
template<
class InputIteratorType,
class ValueType,
class Pred
>
ValueType accumulate_if(InputIteratorType start, InputIteratorType end, ValueType init, Pred p)
{
ValueType result = init;
for (auto it = start; it != end; ++it)
{
if (p(*it)) result += *it;
}
return result;
}
vector<int> a;
list<int> b;
int vector_sum = accumulate_if(a.begin(), a.end(), 0, is_even);
int list_sum = accumulate_if(b.begin(), b.end(), 0, is_even);

39.

Функциональные объекты (функторы)
Функциональный объект – это любой объект для которого определён оператор
вызова функции operator(). C++ предоставляет множество встроенных
функциональных объектов, а также поддерживает создание и манипуляцию
новыми функциональными объектами.
Встроенные функторы
Функтор
Описание
plus, minus, multiplies, divides,
modulus, negate
Функторы, реализующие арифметические операции
(сложение, вычитание, умножение, деление, остаток от
деления, отрицание)
equal_to, not_equal_to, greater,
less, greater_equal, less_equal
Функторы, реализующие операции сравнения (равно, не
равно, больше, меньше, больше или равно, меньше или
равно)
logical_and, logical_or, logical_no
Функторы, реализующие логические операции (И, ИЛИ.
НЕ)
bit_and, bit_or, bit_xor
Функторы, реализующие побитовые операции (И, ИЛИ.
ИСКЛЮЧАЮЩЕЕ ИЛИ)

40.

Пример использования функторов
#include <vector>
#include <algorithm>
#include <numeric>
#include <ctime>
#include <functional>
using namespace std;
vector<int> a;
int n = 0;
int main() {
srand(time(nullptr));
a.resize(rand() % 100);
generate(a.begin(), a.end(), rand);
int mul_a = accumulate(a.begin(), a.end(), 1, multiplies<int>());
return 0;
}

41.

Адаптеры
Адаптеры — это не новые понятия или реализации, а адаптация уже
существующих понятий библиотеки под конкретные, часто использующиеся цели.
Часто такая адаптация делается посредством ограничения функциональности
базового понятия под запросы адаптера.
Виды адаптеров
Адаптеры контейнеров (stack, queue)
Адаптеры итераторов (reverse_iterator, insert_iterator)
Адаптеры функций (bind-функторы)

42.

Адаптеры контейнеров. Стек
stack – это адаптер контейнера deque, реализующий структуру данных «стек».
Реализует принцип LIFO (Last In First Out).
Может быть построен так же на основе любого другого базового контейнера.
Метод
Описание
pop()
Удаление элемента с
вершины стека
push()
Добавление элемента
на вершину стека
top()
Чтение значения
элемента на вершине
стека
Пример использования
#include <stack>
#include <ctime>
#include <vector>
using namespace std;
stack<int, vector<int>> st;
int main() {
srand(time(nullptr));
// Добавление десяти элементов в стек
for (int i = 0; i < 10; ++i)
st.push(rand() % 100);
// Удаление некоторого количества элементов с вершины стека
for (int i = 0; i < rand() % st.size(); ++i)
st.pop();
size()
int st_top = -1;
if (!st.empty())
st_top = st.top(); // Просмотр значения на вершине стека
return 0;
Получение размера
стека
}

43.

Адаптеры контейнеров. Очередь
queue – это адаптер контейнера deque, реализующий структуру данных «очередь».
Реализует принцип FIFO (First In First Out).
Может быть построен так же на основе любого другого базового контейнера.
Метод
Описание
pop()
Удаление элемента
из очереди
Пример использования
#include <queue>
#include <ctime>
using namespace std;
push()
front()
back()
size()
Добавление
элемента в очередь
Чтение значения в
начале очереди
queue<int> q;
int main() {
srand(time(nullptr));
// Добавление десяти элементов в очередь
for (int i = 0; i < 10; ++i)
q.push(rand() % 100);
// Удаление некоторого количества элементов из очереди
for (int i = 0; i < rand() % q.size(); ++i)
Чтение значения в
конце очереди
q.pop();
int q_front = -1;
if (!q.empty())
q_front = q.front(); // Просмотр значения в начале очереди
return 0;
Получение размера
очереди
}

44.

Адаптеры итераторов. Обратные итераторы
Двунаправленные итераторы и итераторы произвольного доступа имеют
соответствующие адаптеры обратных итераторов, которые выполняют итерации
через структуру данных в противоположном направлении. Они имеют те же самые
сигнатуры, как и соответствующие итераторы.
#include <vector>
#include <algorithm>
#include <ctime>
using namespace std;
vector<int> a;
int main() {
srand(time(nullptr));
for (int i = 0; i < rand() % 100; ++i)
a.push_back(rand() % 100);
sort(a.rbegin(), a.rend());
return 0;
}

45.

Адаптеры итераторов. Итераторы вставки
Итератор вставки создаётся из контейнера и, возможно, одного из его итераторов,
указывающих, где вставка происходит, если это ни в начале, ни в конце
контейнера. Итераторы вставки удовлетворяют требованиям итераторов вывода.
Виды итераторов вставки
Итератор вставки в начало (front_inserter)
Итератор вставки в конец (back_inserter)
Итератор вставки в произвольную позицию (inserter)

46.

Адаптеры итераторов. Итераторы вставки. Пример
#include <vector>
#include <algorithm>
#include <iterator>
#include <ctime>
using namespace std;
vector<int> a, b;
int main() {
srand(time(nullptr));
for (int i = 0; i < rand() % 100; ++i) {
a.push_back(rand() % 100); b.push_back(rand() % 100);
}
copy(a.begin(), a.end(),
back_inserter(b)
// Добавит a в конец b
);
copy(a.begin(), a.end(),
front_inserter(b)
// Добавит a в начало b
);
copy(a.begin(), a.end(),
inserter(b, b.begin() + b.size() / 2)
);
return 0;
}
// Добавит a в середину b

47.

Адаптеры функций. Bind-функторы
Функциональные адаптеры работают только с классами функциональных
объектов с определёнными типами параметров и типом результата.
Bind-функторы bind1st и bind2nd берут функциональный объект f двух
параметров, некоторое значение x и возвращают функциональный объект одного
параметра, созданный из f с первым или вторым параметром соответственно,
связанным с х.
#include <vector>
#include <algorithm>
#include <ctime>
#include <functional>
using namespace std;
vector<int> a;
int main() {
srand(time(nullptr));
for (int i = 0; i < rand() % 100; ++i) a.push_back(rand() % 100);
// Найдем в векторе позицию первого числа, большего 50
int pos = find_if(a.begin(), a.end(), bind2nd(greater<int>(), 50)) - a.begin();
return 0;
}

48.

Лямбда-выражения
Лямбда-выражение (или просто лямбда) – это удобный способ
определения анонимного объекта-функции непосредственно в месте его
вызова или передачи в функцию в качестве аргумента.
Обычно лямбда-выражения используются для инкапсуляции нескольких
строк кода, передаваемых алгоритмам или асинхронным методам.
1
2
3
1. Область захвата объектов внешней
области видимости
2. Список параметров (необязательно)
4
3. Возвращаемый тип (необязательно)
4. Тело лямбды

49.

Лямбда-выражения. Область захвата
Лямбда-выражения могут использовать, или захватывать, переменные
из внешней области видимости. Лямбда-выражение начинается с области
захвата, в которой указываются захватываемые переменные и способ
захвата: по значению (=) или по ссылке (&).
Пример
Описание
[]
Пустая область захвата – лямбда не осуществляет доступ ко
внешним переменным
[&]
Все внешние переменные захватываются по ссылке
[=]
Все внешние переменные захватываются по значению
[&a, b]
Явный захват внешней переменной a по ссылке и внешней
переменной b по значению
[&, b]
Все внешние переменные захватываются по ссылке, но
внешняя переменная b захватывается по значению
[=, &b]
Все внешние переменные захватываются по значению, но
внешняя переменная b захватывается по ссылке
[&, &b] или [=, b]
Приведет к ошибке

50.

Лямбда-выражения.
Список параметров, возвращаемый тип и тело лямбды
Лямбда-выражения могут принимать входные параметры. Список
параметров лямбды, по большей части, походит на список параметров
функции.
Возвращаемый тип лямбда-выражения выводится автоматически.
Можно опустить часть возвращаемого типа лямбда-выражения, если
тело лямбда-выражения содержит только один оператор return или
лямбда-выражение не возвращает значение.
Если тело лямбда-выражения содержит один оператор return,
компилятор выводит тип возвращаемого значения из типа
возвращаемого выражения. В противном случае компилятор выводит
следующий тип возвращаемого значения: void.
Часть лямбда-выражения, содержащая его тело, может содержать те же
элементы, что и тело обычной функции. Тело лямбда-выражения
может осуществлять доступ к следующим типам переменных:
захваченные переменные из внешней области видимости; параметры;
локально объявленные переменные; любые статические переменные.

51.

Лямбда-выражения. Примеры использования
int main() {
vector<int> a(10);
int max_val = 100;
ofstream fout("output.txt");
srand(time(nullptr));
generate(a.begin(), a.end(), rand);
transform(a.begin(), a.end(), a.begin(), [max_val](int
return cur_val / max_val;
});
for_each(a.begin(), a.end(), [](int cur_val)
{
cout << cur_val << " ";
});
for_each(a.begin(), a.end(), [&fout](int cur_val) {
fout << cur_val << " ";
});
return 0;
}
cur_val) {