05A. Множества и словари: вставка, поиск, удаление, обход, использование в задачах. Лекция

Всем привет! Это обзорная лекция об использовании таких структур данных, как множество (set) и словарь (map). Рассматривается, почему, зачем и как их использовать. Осваиваем основные операции с ними. В лекции есть примеры задач, например: Q запросов вида сколько элементов от L до R массива равны X и её решение за N log N + Q log N. Остальные задачи здесь: https://docs.google.com/document/d/1cU6aWXP2occLt_FZQCU01epzjH-eFwN_GO_8x1f3VpE/edit?usp=sharing Запасайтесь тайм-кодами, поп-корнами и рок-н-роллами! Приятного просмотра и решения задачек! 00:00:00 Способы организации данных 00:01:20 Массив 00:05:30 Связный список 00:09:40 Советы по их использованию 00:10:50 Дерево поиска (двоичное) 00:15:00 Высота дерева поиска 00:21:20 Преимущество над массивом 00:22:30 Вырождение дерева поиска (двоичного) 00:23:30 Самобалансирующиеся деревья поиска 00:25:00 Реклама задачи "Е. Новогоднее дерево" 00:27:10 Как сделать сбалансированным дерево поиска? 00:28:50 Минимальное число в дереве поиска 00:30:30 Об их реализации в плюсах 00:32:30 set (множество) в плюсах 00:34:00 Примеры вставки в множество 00:35:20 Вывод множества на экран 00:36:15 Почему нет индексации? 00:39:20 Вывод в цикле for each 00:42:30 Удаление чисел из множества 00:43:40 О поиске в множестве 00:45:00 Что такое итераторы? 00:48:10 Примеры использования итераторов 00:52:30 Поиск в множестве (find) 00:57:50 Обход множества итераторами 00:59:00 Метод count 01:00:00 Метод lower_bound 01:01:55 Метод upper_bound 01:03:20 Максимальный меньший заданного элемент 01:04:20 Функция lower_bound против метода lower_bound 01:06:28 Оговорка: функция не std::forward, а std::advance 01:07:25 Последовательный и произвольный доступ 01:08:30 erase и count в multiset 01:13:50 Запрещено удалять то, чего нет 01:18:10 Вопрос про unordered_set 01:18:40 Решение задачи "A. Абстрактные мемы" 01:26:00 Получили Accepted с set! 01:27:10 Получили TLE с unordered_set 01:29:30 Словари (map) 01:35:00 Словари (map) в плюсах 01:35:58 Функция insert 01:38:30 Оператор квадратные скобки 01:43:10 Обход элементов map (словаря) 01:47:20 Модификация значений элементов 01:49:50 Поиск ключа 01:50:40 Очень важный нюанс: создание лишних элементов при каждом обращении 01:57:40 Пример: сохранение позиций всех букв в map(char, vector(int)) 02:01:30 Сколько символов на отрезке, равных заданному? 02:04:20 О домашнем задании