Словари и множества

Август 23, 2022

Главная
Информатика
Словари и множества

Содержание

2. математические структуры, которые могут хранить в себе уникальные элементы (то есть, каждый элемент может входить в
3. Решим следующую задачу: даны N запросов трёх типов: добавить элемент во множество; проверить, входит ли элемент
4. Решение
5. При объявлении получаем пустое множество Добавление элементов в него происходит с помощью метода insert. Чтобы проверить,
6. Заполним N элементов множества целыми числами
7. 1 способ now — это не очередной элемент, а указатель на него begin возвращает указатель на
8. 2 способ for (auto now : s) { cout } Вывод всех элементов множества
9. Поскольку проход по элементам множества осуществляется в возрастающем порядке, то можно использовать его для сортировки последовательностей.
10. В C++ есть структура multiset, которая может хранить в себе одинаковые элементы. Multiset умеет все то
11. С помощью set очень легко подсчитать число различных элементов в последовательности. Для этого нужно просто добавить
12. 1 способ при добавлении элемента во множества, если его нет увеличить счетчик 2 способ У set
13. посчитать, сколько раз встречается единица в последовательности Подсчет количества вхождений элемента в последовательность
14. lower_bound возвращает указатель на первый элемент, значение которого больше либо равно переданному параметру. upper_bound — на
15. Структура, похожая на множество. Ставит в соответствие ключу значение, совсем как в обычном словаре, где каждому
16. map s; Создания элемента словаря s[112] = "sos"; Проверка существования элемента делается с помощью метода find,
17. Пример
18. 1 способ Проход по элементам словаря
19. В словаре на место now подставляются пары «ключ-значение» Обратиться к первому из них можно как к
20. Часто требуется сопоставить одному ключу несколько значений. в телефонной книге — несколько номеров у одного и
21. Пример
22. В этой программе мы сразу инициализировали вектор конкретными значениями, используя фигурные скобки. В принципе, можно создать
23. Дан список целых чисел, который может содержать до 100000 чисел. Определите, сколько в нем встречается различных
25. Скачать презентацию

Слайд 2

математические структуры, которые могут хранить в себе уникальные элементы (то есть, каждый

элемент может входить в множество только один раз).

Множества

Слайд 3

Решим следующую задачу: даны N запросов трёх типов:
добавить элемент во множество;
проверить,

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

Работа с элементами множества

Слайд 4

Решение

Слайд 5

При объявлении получаем пустое множество
Добавление элементов в него происходит с помощью

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

Пояснение

Слайд 6

Заполним N элементов множества целыми числами

Слайд 7

1 способ
now — это не очередной элемент, а указатель на него
begin

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

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

Слайд 8

2 способ
for (auto now : s) {
cout << now

<< ' ';
}

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

Слайд 9

Поскольку проход по элементам множества осуществляется в возрастающем порядке, то можно

использовать его для сортировки последовательностей.
НО всё портит тот факт, что с одинаковыми элементами множество работает иначе.

Сортировка с помощью множества

Слайд 10

В C++ есть структура multiset, которая может хранить в себе одинаковые

элементы.
Multiset умеет все то же самое, что и обычный set, и лежит в той же библиотеке.
Если в предыдущей программе вывода всех элементов заменить set на multiset, то мы как раз и получим элементы по возрастанию.

Сортировка с помощью множества

Слайд 11

С помощью set очень легко подсчитать число различных элементов в последовательности.

Для этого нужно просто добавить все элементы последовательности во множество, а затем посмотреть на его размер.

Количество разных элементов

Слайд 12

1 способ
при добавлении элемента во множества, если его нет

увеличить счетчик
2 способ
У set есть метод size(), который возвращает количество элементов во множестве. Добавить в него все элементы подряд, вывести size() от этого множества.

Количество разных элементов

Слайд 13

посчитать, сколько раз встречается единица в последовательности
Подсчет количества вхождений элемента

в последовательность

Слайд 14

lower_bound возвращает указатель на первый элемент, значение которого больше либо равно

переданному параметру.
upper_bound — на первый элемент, который строго больше
Так мы пробежим от первой единицы до первого элемента (или end’а нашего set’а), на каждом шаге увеличивая значение счётчика вхождений. Если ни одной единицы в последовательности нет, оба метода вернут указатели на больший элемент; будет выполнено 0 шагов.

Пояснение

Слайд 15

Структура, похожая на множество.
Ставит в соответствие ключу значение, совсем как в

обычном словаре, где каждому русскому слову ставится в соответствие иностранное.
Словарь в C++ называется map (карта).
Чтобы пользоваться словарями, нужно подключить библиотеку map.

Словари

Слайд 16

map s;
Создания элемента словаря
s[112] = "sos";
Проверка существования элемента

делается с помощью метода find, как и во множествах.

Пример описания словаря(карты)

Слайд 17

Пример

Слайд 18

1 способ
Проход по элементам словаря

Слайд 19

В словаре на место now подставляются пары «ключ-значение»
Обратиться к первому из

них можно как к now.first (где now — название пары), а ко второму — now.second.
Отдельные элементы пары также можно менять как обычные переменные.
Как и во множестве, ключи в словаре упорядочены по возрастанию. Для поиска ключей можно также пользоваться методами find, lower_bound и upper_bound.

Особенности словаря

Слайд 20

Часто требуется сопоставить одному ключу несколько значений.
в телефонной книге — несколько

номеров у одного и того же человека.
Чтобы решить задачу такого сопоставления, мы будем использовать в качестве значения вектор.

Сопоставление нескольких значений

Слайд 21

Пример

Слайд 22

В этой программе мы сразу инициализировали вектор конкретными значениями, используя фигурные

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

Пояснения

Слайд 23

Дан список целых чисел, который может содержать до 100000 чисел. Определите,

сколько в нем встречается различных чисел.

Задача №1

Словари и множества

Содержание

математические структуры, которые могут хранить в себе уникальные элементы (то есть, каждый

Решим следующую задачу: даны N запросов трёх типов:добавить элемент во множество; проверить,

Решение

При объявлении получаем пустое множествоДобавление элементов в него происходит с помощью

Заполним N элементов множества целыми числами

1 способnow — это не очередной элемент, а указатель на негоbegin

2 способfor (auto now : s) { cout << now

Поскольку проход по элементам множества осуществляется в возрастающем порядке, то можно

В C++ есть структура multiset, которая может хранить в себе одинаковые

С помощью set очень легко подсчитать число различных элементов в последовательности.

1 способ при добавлении элемента во множества, если его нет

посчитать, сколько раз встречается единица в последовательности Подсчет количества вхождений элемента

lower_bound возвращает указатель на первый элемент, значение которого больше либо равно

Структура, похожая на множество. Ставит в соответствие ключу значение, совсем как в

map s;Создания элемента словаря s[112] = "sos";Проверка существования элемента

Пример

1 способПроход по элементам словаря

В словаре на место now подставляются пары «ключ-значение»Обратиться к первому из

Часто требуется сопоставить одному ключу несколько значений.в телефонной книге — несколько

Пример

В этой программе мы сразу инициализировали вектор конкретными значениями, используя фигурные

Дан список целых чисел, который может содержать до 100000 чисел. Определите,

Похожие презентации

Решим следующую задачу: даны N запросов трёх типов:
добавить элемент во множество;
проверить,

При объявлении получаем пустое множество
Добавление элементов в него происходит с помощью

1 способ
now — это не очередной элемент, а указатель на него
begin

2 способ
for (auto now : s) {
cout << now

1 способ
при добавлении элемента во множества, если его нет

посчитать, сколько раз встречается единица в последовательности
Подсчет количества вхождений элемента

Структура, похожая на множество.
Ставит в соответствие ключу значение, совсем как в

map s;
Создания элемента словаря
s[112] = "sos";
Проверка существования элемента

1 способ
Проход по элементам словаря

В словаре на место now подставляются пары «ключ-значение»
Обратиться к первому из

Часто требуется сопоставить одному ключу несколько значений.
в телефонной книге — несколько