Библиотека STL. Тип vector

1.

Библиотека STL
Тип vector
ГАОУ «Лицей Иннополис»
Учитель информатики Беляева Ольга Семеновна

2.

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

3.

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

4.

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

5.

6.

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

7.

Методы для контейнера в STL
метод
Назначение
Push_back()
Вставляет значение аргумента в конец вектора
Pop_back()
Удаляет последний элемент вектора
Back()
Возвращает значение последнего элемента вектора
Empty()
Возвращает true, если вектор пуст
Insert()
Вставляет элемент на указанную позицию
Erase()
Удаляет элемент из указанной позиции
Size()
Возвращает количество элементов в контейнере
Resize()
Изменение размера массива
Clear()
Очищает вектор (удаляет все элементы)

8.

9.

10.

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

11.

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

12.

13.

14.

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

15.

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

16.

Итераторы
It = a.begin();
*it=100;
Cout << *it;

17.

18.

19.

20.

Методы для контейнера в STL
метод
Назначение
Size()
Возвращает число элементов в контейнере
Max()
Возвращает максимальное из двух значений
Min()
Возвращает минимальное из двух значений
Max_size()
Возвращает максимально допустимый размер контейнера
Begin()
Возвращает итератор начала контейнера (в прямом направлении)
End()
Возвращает итератор на последнюю позицию в контейнере
Rbegin()
Возвращает рекурсивный итератор на конец контейнера (в обратном
направлении)
Rend()
Возвращает рекурсивный итератор на начало контейнера (в обратном
направлении)

21.

Алгоритмы для контейнера в STL
метод
Назначение
Find()
Возвращает первый элемент с указанным значением
Count()
Считает количество элементов, имеющих указанное значение
Equal()
Сравнивает содержимое двух контейнеров и возвращает true, если все
соответствующие элементы эквивалентны
Sort()
Сортирует значения в соответствующем порядке
Search()
Ищет последовательность значений в одном контейнере, которая
соответствует такой же последовательности в другой
Merge()
Комбинирует два сортированных диапазона значений для получения
наибольшего диапазона
For_each()
Выполняет указанную функцию для каждого элемента контейнера
Transform()
Выполняет указанную функцию для каждого элемента контейнера и
помещает результат в другой или тот же контейнер
Accumulate()
Возвращает сумму элементов в заданном диапазоне

22.

Алгоритмы для контейнера в STL
метод
Назначение
Copy()
Копирует последовательность значений из одного контейнера в другой
Swap()
Обменивает значения, находящихся в разных местах
Itter_swap()
Обменивает последовательность значений, находящихся в разных местах
Fill()
Копирует значение в последовательность значений

23.

24.

СТРУКТУРА PAIR

25.

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

26.

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

27.

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

28.

29.

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

30.

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

31.

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

32.

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

33.

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

34.

КОНТЕЙНЕР SET

35.

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

36.

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

37.

set <int> s1;
set <string> 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<< ' ';

38.

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.

39.

Работа с памятью:
• S.size() - размер контейнера
• S.max_size() - максимальный
размер контейнера
• S.begin() - указатель на начало
контейнера
• S.end() - указатель на конец
контейнера
• S.rbegin() - реверсивный указатель
на конец контейнера
• S.rend() - реверсивный указатель на
начало контейнера

40.

КАК ВЫВЕСТИ СОДЕРЖИМОЕ SET В ЦИКЛЕ?

41.

#include <iostream>
#include <set>
#include <string>
#include <iterator>
using namespace std;
int main() {
set<int> 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<int>::iterator p = data_set.begin(); p != data_set.end(); p++)
cout << *p << " ";
int min_element = *data_set.begin();
cout << endl << min_element;
return 0;
}

42.

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

43.

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

44.

КОНТЕЙНЕР MAP

45.

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

46.

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

47.

48.

49.

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

50.

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

51.

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

52.

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

53.

54.

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

55.

Методы
Назначение
begin()
- итератор на первый элемент;
end()
- итератор на элемент идущий после последнего;
rbegin()
- итератор на последний элемент (для обратных алгоритмов);
rend()
- итератор на позицию перед первым элементом (для обратных алгоритмов).
empty()
- возвращает истину, если размер отображения 0;
size()
- возвращает число элементов;
max_size()
- максимально возможный размер отображения.
count(key)
- число элементов соответствующих указанному ключу. Для класса map
значения 1 или 0;
find(key)
- итератор на первый элемент с указанным ключом;
clear()
- удалить все элементы.

56.

Методы
Назначение
lower_bound(key)
- итератор на первый элемент, чей ключ больше или равен указанному ключу;
upper_bound(key)
- итератор на первый элемент, чей ключ больше указанного ключа;
equal_range(key)
- диапазон элементов, чей ключ равен указанному ключу;
[]
- операция индексации по ключу.
swap(map& m)
- обмен значениями с другим отображением;
insert(el)
- вставка элемента, возвращается его позиция;
insert(beg,end)
- вставка элементов из указанного диапазона;
erase(key)
- удалить указанный элемент;
erase(it),
- удаляет элемент с заданным итератором или между заданными
erase(start,end)

57.

58.

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

59.

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

60.

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

61.

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

62.

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

63.

Ресурсы
• http://cppstudio.com/post/9535/
• http://cppstudio.com/post/9691/
• http://cppstudio.com/post/9833/
• http://kpolyakov.spb.ru/school
• https://proginfo.ru/
• https://codelessons.ru/cplusplus/set-i-multiset-v-c-chto-etotakoe-i-kak-s-nimi-rabotat.html
• https://codelessons.ru/cplusplus/map-v-c-chto-eto-i-kak-setim-rabotat.html