Библиотека STL. Тип vector презентация

STL – Standard Template Library
Стандартная библиотека шаблонов
Vector
Pair (пары)
Map (Словари)
Деки
Списки
Очереди
Битовые поля
И др.

Тип vector
Объявление
#include
…
vector
A;
Или
vector
A(10);
Или
vector
A(10, 1);
Задание.
Объявите вектор и выведите его на экран.
Чем различаются эти способы?

Резервирование памяти
vector
A;
A.reserve(10);
Аналогично
int A[10]; // обычное объявление массива

Как скопировать вектор?
Vector
myVector1(10);
For (int i = 0; i <10; i++)
myVector1[i] = i;
vector
myVector2(myVector1);

Методы для контейнера в STL

Вопросы и задания:
Программист забыл удалить динамический массив, память для которого выделялась внутри функции. Какие проблемы могут возникнуть из-за этой ошибки?
Какие значения будут иметь значения массива А?
int * A = new double [5] { };
Как расширить вектор в ходе выполнения программы?

Что получим в результате?
Почему?

Практикум
Задача №112484. Реверс массива неизвестной длины

Итераторы
Итераторы (курсоры, указатели) – специальные объекты, которые позволяют перебрать все элементы контейнера.
Объявление:
Vector :: iterator it;
Итератор – специальный указатель на элемент вектора.

Итераторы
It = a.begin();
*it=100;
Cout << *it;
// то же, что a[0]=100;
// то же, что cout << a[0];

Методы для контейнера в STL

Алгоритмы для контейнера в STL

Алгоритмы для контейнера в STL

СТРУКТУРА PAIR
Структура, позволяющая обрабатывать два объекта как один объект

В программировании часто возникает необходимость обрабатывать два объекта, например, простую пару чисел, как один.
Причём типы обоих значений в паре могут быть совершенно разными – в этом и состоит особая ценность рассматриваемой структуры и на это необходимо обратить особое внимание.
Откликом на такую задачу одновременной обработки пары значений стало появление структуры pair

Применение:
Хранить 2D клетку карты.
Хранить Координаты X и Y.
Хранить тип переменной для void*.
Если нужен индекс по двойному ключу. (имя-фамилия)

int main ()
{
pair
p1 (10, 0.011); // объявляем пар
pair
p2;
p2 = make_pair (10, 0.222); // функция, обеспечивающая
// присвоение значений полям пары p2
pair
p3 (p1); // копия уже созданной p1
cout.precision (3); // назначаем точность вывода действительных чисел
cout << "Пара p1 состоит из элементов : ( " << p1.first << ", " << p1.second << " )"
<< endl;
cout << "- p2 : ( " << p2.first << ", " << p2.second << " )" << endl;
cout << "- p3 : ( " << p3.first << ", " << p3.second << " )" << endl;
return 0;
}

Преимущества

Преимущества

Функция make_pair (a1,A2);
создает объект типа, определяемых типов аргументов

Преимущества

Задание
https://ru.surveymonkey.com/r/NB975GY

КОНТЕЙНЕР SET
Множество

#include
В языке C++ контейнер set позволяет работать с различными множествами. Под множеством понимают некоторое количество отсортированных элементов.

Что получим?
Вместо insert можно использовать функцию emplace, которая перед добавлением проверяет, есть ли уже такой элемент, и если нет, то добавляет его.

set
s1;
set
s2;
s1.emplace(5);
s2.emplace("r");
s1.emplace(10);
s2.emplace("f");
s1.emplace(15);
s2.emplace("q"); for (auto a: s1)
cout << a<< ' ';
for (auto a: s2)
cout << a<< ' ';

Set - контейнер, имеет все стандартные для контейнера функции:
S.swap(S2) - меняет содержимое контейнеров местами,
S.insert(a) - вставка элемента a,
S.erase(S2) - удаляет последовательность элементов,
S.clear() - очистка контейнера set,
S.count() - количество элементов в контейнере,
S.find(a) - найти элемент a в контейнере,
S.lower_bound(a) - первый элемент, не меньший чем a,
S.upper_bound(a) - первый элемент, больший чем a,
S.equal_range(a) - пара элементов, первый - нижняя граница элементов с, такими же значениями, что и a, второй - верхняя граница элементов с такими же значениями, что и a.

Работа с памятью:
S.size() - размер контейнера
S.max_size() - максимальный размер контейнера
S.begin() - указатель на начало контейнера
S.end() - указатель на конец контейнера
S.rbegin() - реверсивный указатель на конец контейнера
S.rend() - реверсивный указатель на начало контейнера
РАБОТА С КОНТЕЙНЕРОМ:

КАК ВЫВЕСТИ СОДЕРЖИМОЕ SET В ЦИКЛЕ?
for (auto a: s1)
cout << a << ' ';

#include
#include
#include
#include
using namespace std;
int main() {
set
data_set;
// создается множество
data_set.insert(10);
// добавить число 10
for (int x = 1; x <= 5; x++)
data_set.insert(x * 5);
// добавить числа 5, 10, 15, 20, 25
for (set
::iterator p = data_set.begin(); p != data_set.end(); p++)
cout << *p << " ";
int min_element = *data_set.begin();
cout << endl << min_element;
return 0;
}

Плюсы и минусы использования set и multiset
Плюсы
Быстрая сортировка элементов
Минусы
Нельзя обратится к конкретной ячейке по индексу [].
Если у вас мало обращений к определенным ячейкам, то использовать однозначно нужно.
Если же вам придется очень часто обращаться к произвольным ячейкам — то использовать лучше vector или массив, если это возможно.

Задания
Используйте шаблон set для построения двух множеств целых чисел вычисления их объединения и пересечения.
Используйте шаблон multiset для подсчета числа вхождений каждого числа во множество целых чисел с повторами.

КОНТЕЙНЕР MAP
Ассоциативный словарь

Задача
В файле находится список слов, среди которых есть повторяющиеся. Каждое слово записано в отдельной строке. Построить алфавитно-частотный словарь: список слов в алфавитном порядке, справа от каждого слова должно быть указано, сколько раз оно встречается в исходном файле.
Список – это упорядоченный набор элементов одного типа, для которого введены операции вставки (включения) и удаления (исключения).
B C++ : Map («отображение») – это словарь (ассоциативный массив). Индексы элементов – любые данные.

Объявляются сразу два типа переменных
(первый тип – string, второй тип — int)

Обратите внимание!
map можно использовать в виде ассоциативного массива. Массива который позволяет в себе хранить пару вида («ключ», «значение»), а так-же добавлять и удалять пары по ключу.
У нас в роли ключа выступает тип string, а в роли значения тип int.
вывод осуществляется в алфавитном порядке, а заполнение map нет.
Контейнер map сам выполняет сортировку по алфавиту

Обратите внимание!
осуществляется вывод с помощью итератора it.
Итератор it сначала указывает на начало map и с каждой новой итерацией увеличивается, пока не достигнет конца map.
Запись вида it->first означает, что it при первой итерации указывает на строку Mother, потом на Father и так далее до конца цикла,
соответственно, запись вида it->second означает, что it при первой итерации указывает на число 37, потом на 40 и так далее.

Строка 22 содержит функцию map::insert(), которая вставляет элементы в map.
Запись вида pair
(c,i) означает, что в map помещаются две переменные типа char и int (первая – char, вторая — int),
где типу char соответствует переменная c, а типу int соответствует переменная i.
В строке 20 при каждой новой итерации наши переменные будут увеличиваться, т. е. сначала i=0, c=a, при следующей итерации i=1, c=b и т. д.

В строке 28 показан альтернативный вывод map с помощью указателей.
map не может содержать два одинаковых значения, но multimap решает эту проблему
Multimap ничем не отличается от map, за исключением того, что в нем можно хранить повторяющиеся элементы

Про работу с итераторами:
Для обращения к элементу в строках и векторах достаточно было перед именем контейнера поставить *, но в map так не получится, т.к. в каждом элементе хранится 2 значения (ключ и данные).
Поэтому надо писать так:
(*iter).first - для обращения к ключу и
(*iter).second -для обращения к данным,
где iter - итератор элемента
Вместо громоздкой записи
(*it).first
и
(*it).second
можно использовать более компактный оператор доступа к полю через указатель “->”:
it->first
it->second

Повторим
Для чего нужны словари?
Как объявить?
Как вывести?
В чем отличие MAP от MULTYMAP?

Плюсы и минусы: использования map
Плюсы:
Ключом может быть любая переменная. Это огромный плюс, например если придется делать словарь.
Минусы:
Долгое добавление нового элемента.
Долгое обращение к элементу.
Долгое удаление нового элемента.
Также слишком затратный по памяти
Все эти операции происходят за — log n (n — это размер контейнера).

ИТОГ
Если вам требуется быстрый отклик программы, то если возможно оперировать вектором либо массивом лучше использовать именно их.
Если же время не стоит на первом месте, то можно им пренебречь и использовать map.

Когда нужно использовать словари
Подсчет числа каких-то объектов. В этом случае нужно завести словарь, в котором ключами являются объекты, а значениями — их количество.
Хранение каких-либо данных, связанных с объектом. Ключи — объекты, значения — связанные с ними данные. Например, если нужно по названию месяца определить его порядковый номер, то это можно сделать при помощи словаря
Num["January"] = 1;
Num["February"] = 2;
….
Установка соответствия между объектами (например, “родитель—потомок”). Ключ — объект, значение — соответствующий ему объект.

Задание
1) Создайте программу «Страна – столица».
2) Создайте программу для определения по названию месяца его порядкового номера.
3) Создайте программу в которой пользователь сможет использовать данные операции:
Добавлять новое слова — [английское — русское].
Удалять их.
Изменять значение уже существующего слова (...->second).