Презентация - Словари и множества. Стандартные алгоритмы STL


Словари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STLСловари и множества. Стандартные алгоритмы STL
На весь экран

Слайды и текст этой презентации

Слайд 1

Программирование Лекция 7. Словари и множества. Стандартные алгоритмы STL

Слайд 2

Множества Множества — это математические структуры, которые могут хранить в себе уникальные элементы (то есть, каждый элемент может входить в множество только один раз). #include

Слайд 3

Множества Множества создаются по аналогии с векторами. Пишем ключевое слово set, за ним — название типа каждого из элементов множества (в треугольных скобках), а после этого указываем имя для нового множества. Так мы получаем пустое множество. Добавление элементов в него происходит с помощью метода insert. Чтобы проверить, входит ли элемент во множество, используется метод find. Если элемент в множестве не нашелся, то он выдает то же значение, что и метод end. Удаление отдельного элемента из множества выполняется с помощью метода erase.

Слайд 4

Решим следующую задачу Даны N запросов трёх типов: добавить элемент во множество; проверить, входит ли элемент во множество; удалить элемент из множества. Сначала задается число N, а затем сами запросы. Каждый из них состоит из двух чисел. Первое обозначает тип запроса, а второе — элемент, с которым нужно произвести операцию.

Слайд 5

Число n – ск-ко запросов Если элемент не нашелся, то вернется указатель на конец множ-ва В строке метод find() возвращал позицию подстроки, «-1» - если не найдено

Слайд 6

Ввод элементов множества

Слайд 7

Вывод всех элементов множества Первый способ : Второй способ позволяет выводить элементы множества аналогично выводу всех элементов в векторе: Если ввести одинаковые элементы, то каждый из них окажется во множестве (и будет выведен) только один раз! В данном случае now — это не очередной элемент, а указатель на него. Метод begin возвращает указатель на самый маленький элемент множества, end — это конец множества (он идёт после самого большого элемента), а операция осуществляет переход к указателю на следующий элемент. Чтобы посмотреть, что за элемент хранится по указателю, нужно перед его именем написать символ . В обоих случаях вывод по возрастанию!

Слайд 8

Сортировка с помощью множества Поскольку проход по элементам множества осуществляется в возрастающем порядке, то велик соблазн использовать его для сортировки последовательностей. Увы, всё портит тот факт, что с одинаковыми элементами множество работает иначе. Тем не менее, задачу сортировки решить можно и с их помощью. В C есть структура multiset , которая может хранить в себе одинаковые элементы. Multiset умеет все то же самое, что и обычный set, и лежит в той же библиотеке. Если в предыдущей программе вывода всех элементов заменить set на multiset, то мы как раз и получим элементы по возрастанию (с учетом повторяющихся).

Слайд 9

Количество разных элементов С помощью set очень легко подсчитать число различных элементов в последовательности. Для этого нужно просто добавить все элементы последовательности во множество, а затем посмотреть на его размер. При обработке очередного элемента последовательности нужно сначала проверить, есть ли элемент во множестве. Если его там нет — увеличиваем счётчик на единицу, а затем добавляем элемент во множество. Но есть и более простой способ. У set есть метод size() , который возвращает количество элементов во множестве. Достаточно просто добавить в него все элементы подряд, а затем вывести size() от этого множества.

Слайд 10

Подсчет количества вхождений элемента в последовательность Поскольку во множестве все элементы упорядочены, с его помощью легко подсчитать количество вхождений элемента в последовательность. Например, мы хотим посчитать, сколько раз встречается единица. Для решения этой задачи мы будем использовать multiset.

Слайд 11

multiset s; int n; cin n; for (int i 0; i n; i ) int x; cin x; s.insert(x); int cnt 0; for (auto now s.lower bound(1); now ! s.upper bound(1); now ) cnt ; cout 2 новых метода: lower bound и upper bound . l ower bound возвращает указатель на первый элемент, значение которого больше либо равно переданному параметру. u pper bound — на первый элемент, который строго больше. Так мы пробежим от первой единицы до первого элемента (или end а нашего set а), на каждом шаге увеличивая значение счётчика вхождений. Если ни одной единицы в последовательности нет, оба метода вернут указатели на больший элемент; будет выполнено 0 шагов.

Слайд 12

Задача 1 Дан список целых чисел, который может содержать до 100000 чисел. Определите, сколько в нем встречается различных чисел. Входные данные Вводится число N - количество элементов списка, а затем N чисел. Выходные данные Выведите ответ на задачу. Sample Input: 5 1 2 3 2 1 Sample Output: 3

Слайд 13

Задача 2 Во входной строке записана последовательность чисел через пробел. Для каждого числа выведите слово YES (в отдельной строке), если это число ранее встречалось в последовательности или NO, если не встречалось. Входные данные Вводится число N - количество элементов списка, а затем N чисел. Выходные данные Выведите ответ на задачу. Sample Input: 6 1 2 3 2 3 4 Sample Output: NO NO NO YES YES NO

Слайд 14

Задача 3 Даны два списка чисел, которые могут содержать до 100000 чисел каждый. Посчитайте, сколько чисел содержится одновременно как в первом списке, так и во втором. Входные данные Вводится число N – количество элементов первого списка, а затем N чисел первого списка. Затем вводится число M - количество элементов второго списка, а затем M чисел второго списка. Выходные данные Выведите ответ на задачу. Sample Input: 3 1 3 2 3 4 3 2 Sample Output: 2

Слайд 15

Задача 4 Даны два списка чисел, которые могут содержать до 100000 чисел каждый. Выведите все числа, которые входят как в первый, так и во второй список в порядке возрастания. Входные данные Вводится число N – количество элементов первого списка, а затем N чисел первого списка. Затем вводится число M – количество элементов второго списка, а затем M чисел второго списка. Выходные данные Выведите ответ на задачу. Sample Input: 3 1 3 2 3 4 3 2 Sample Output: 2 3

Слайд 16

Словари В C есть ещё одна структура, похожая на множество, которая называется «словарь». Она ставит в соответствие ключу значение, совсем как в обычном словаре, где каждому русскому слову ставится в соответствие иностранное. Словарь в C называется map (карта). Чтобы пользоваться словарями, нужно подключить библиотеку map. Чтобы создать словарь, мы пишем map , затем в треугольных скобках через запятую указываем тип ключа и значения . После этого идёт имя нового словаря. Создавать элементы в словаре очень просто. Достаточно написать имя словаря, а затем в квадратных скобках указать ключ. Нужно сразу приравнять этот элемент к какому-либо значению. Тогда к нему можно будет обращаться, просто указав имя словаря и ключ в квадратных скобках. Проверка существования элемента делается с помощью метода find , как и во множествах.

Слайд 17

Словари Рассмотрим такую задачу: на телефон поступает входящий звонок с известного номера телефона. Нужно проверить, есть ли он в телефонной книге. Для этого понадобится словарь, в котором числу (номеру) соответствует строка (имя абонента).

Слайд 18

#include #include #include using namespace std; int main() map s; s 112 "sos"; if (s.find(112) ! s.end()) cout return 0; В соответствие числу ставится строка

Слайд 19

Проход по элементам словаря Проход по всем элементам в словаре делается почти так же, как и во множестве. map s; s 112 "sos"; s 102 "emergency"; for (auto now : s) cout В отличие от множества, в словаре на место now подставляются пары «ключ-значение». Пара — это особый тип данных, состоящий из двух элементов. Обратиться к первому из них можно как к now.first (где now — название пары), а ко второму — now.second . Это обращение к полям очень похоже на вызов метода, но после него не нужно писать скобок . Отдельные элементы пары также можно менять как обычные переменные. Как и во множестве, ключи в словаре упорядочены по возрастанию . Для поиска ключей можно также пользоваться методами find, lower bound и upper bound.

Слайд 20

Сопоставление нескольких значений Часто требуется сопоставить одному ключу несколько значений. Например, в словаре иностранных слов может быть несколько переводов для одного слова, а в телефонной книге — несколько номеров у одного и того же человека. Чтобы решить задачу такого сопоставления, мы будем использовать в качестве значения вектор. Вернёмся к примеру с телефонной книгой. Допустим, нам нужно сохранить для одного абонента все телефонные номера (их мы тоже будем хранить в строке).

Слайд 21

#include #include #include #include using namespace std; int main() map s; s "Vasya" "112133", "12341" ; for (auto now : s "Vasya" ) cout return 0; Имя и номера телефонов Подключим библиотеку для векторов

Слайд 22

В этой программе мы сразу инициализировали вектор конкретными значениями, используя фигурные скобки. В принципе, можно создать пустой вектор и добавлять в него элементы с помощью метода push back. Это удобно в том случае, если мы не знаем заранее, сколько номеров в нашей телефонной книге может быть сопоставлено человеку. Если ключ ещё не встречался, нужно создать пустой вектор, а при каждом его обнаружении просто добавлять элемент в вектор.

Слайд 23

Стандартные алгоритмы STL Сегодня мы будем изучать разные алгоритмы, которые есть в стандартной библиотеке C . Они помогают быстрее писать программы. В основном мы будем использовать библиотеку algorithm.

Слайд 24

Сортировка #include #include #include using namespace std; int main() int n; cin n; vector a(n); for (int i 0; i n; i ) cin a i ; sort(a.begin(), a.end()); for (auto now : a) cout return 0; Возьмём последовательность чисел, которую нужно считать, упорядочить и вывести. Функция sort принимает на вход два параметра: начало и конец сортируемой области. В нашем случае это начало вектора (begin) и его конец (end).

Слайд 25

Структуры Чтобы описывать объекты, которые характеризуются несколькими разными значениями, нужны структуры . Фактически, структура — это новый тип переменных. Сначала нужно описать структуру, а после этого можно создавать переменные, вектора и прочие элементы такого типа. Описание структуры должно следовать сразу после using namespace std и находиться вне функций. Например, мы хотим описать человека при помощи двух характеристик: рост и имя. struct man int height; string name; ; Обратите внимание на точку с запятой после фигурной скобки — она обязательно нужна.

Слайд 26

Слайд 27

Устойчивая сортировка Сортировка называется устойчивой, если она сохраняет взаимный порядок одинаковых элементов. Если Вася и Петя одного роста, но в исходной последовательности Вася стоял раньше Пети, то после устойчивой сортировки Вася также должен идти перед Петей. При использовании sort взаимный порядок одинаковых элементов может нарушиться (Петя окажется перед Васей). Чтобы этого не произошло, нужно использовать функцию устойчивой сортировки stable sort . Она принимает те же параметры, что и sort, но работает немного медленнее.

Слайд 28

Задача 5 Отсортируйте массив. Входные данные Первая строка входных данных содержит количество элементов в массиве N 10 5 . Далее идет N целых чисел, не превосходящих по абсолютной величине 10 9 . Выходные данные Выведите эти числа в порядке неубывания. Sample Input: 5 5 4 3 2 1 Sample Output: 1 2 3 4 5

Слайд 29

Ответ на задачу 1 #include #include using namespace std; int main() set s; int n; cin n; for (int i 0; i n; i ) int x; cin x; s.insert(x); cout return 0;

Слайд 30

Ответ на задачу 2 int main() set s; int n; cin n; for (int i 0; i n; i ) int x; cin x; if (s.find(x) s.end()) cout else cout s.insert(x); return 0;

Слайд 31

Ответ на задачу 3 set s; set s1; set s2; int n1; cin n1; for (int i 0; i n1; i ) int x; cin x; s1.insert(x); s.insert(x); int n2; cin n2; for (int i 0; i n2; i ) int x; cin x; s2.insert(x); s.insert(x); cout

Слайд 32

Ответ на задачу 4 set s1; set s2; set s; int n1; cin n1; for (int i 0; i n1; i ) int x; cin x; s1.insert(x); int n2; cin n2; for (int i 0; i n2; i ) int x; cin x; s2.insert(x); if (s1.find(x) ! s1.end()) s.insert(x); for (auto now : s) cout

Слайд 33

Ответ на задачу 5 set s1; set s2; set s; int n1; cin n1; for (int i 0; i n1; i ) int x; cin x; s1.insert(x); int n2; cin n2; for (int i 0; i n2; i ) int x; cin x; s2.insert(x); if (s1.find(x) ! s1.end()) s.insert(x); for (auto now : s) cout

Слайд 34

Ответ на задачу 4 set s1; set s2; set s; int n1; cin n1; for (int i 0; i n1; i ) int x; cin x; s1.insert(x); int n2; cin n2; for (int i 0; i n2; i ) int x; cin x; s2.insert(x); if (s1.find(x) ! s1.end()) s.insert(x); for (auto now : s) cout

Слайд 35

Ответ на задачу 4 set s1; set s2; set s; int n1; cin n1; for (int i 0; i n1; i ) int x; cin x; s1.insert(x); int n2; cin n2; for (int i 0; i n2; i ) int x; cin x; s2.insert(x); if (s1.find(x) ! s1.end()) s.insert(x); for (auto now : s) cout

Слайд 36

Ответ на задачу 5 #include #include #include using namespace std; int main() int n; cin n; vector a(n); for (int i 0; i n; i ) cin a i ; sort(a.begin(), a.end()); for (auto now : a) cout return 0;