Словари и множества в C++
В этом занятии мы разбираем контейнеры и итераторы в C++, а также работу с ассоциативными структурами данных: std::map, std::set и std::multiset. По ходу занятия объясняем, чем отличаются методы контейнеров от общих алгоритмов STL, как связаны структуры данных с асимптотикой и почему std::map работает быстро. Отдельно рассматриваем бинарные деревья поиска, сбалансированные деревья и возможности __gnu_pbds::tree для порядковых статистик. В конце разбираем несколько задач, где все эти идеи применяются на практике. Тайм-коды: 00:00:00 Обзор списка задач 00:00:20 Введение в тему занятия 00:04:10 Что такое словарь 00:10:10 Применение словаря 00:11:30 Что такое контейнер в С++ 00:12:30 Что такое итераторы 00:15:45 Обход контейнера 00:18:10 Пример: поиск максимума в контейнере 00:21:35 Какие бывают итераторы 00:22:00 lower_bound в vector и list 00:27:35 Как работать со словарём std::map в C++ 00:40:10 Поиск в map, разница между map.find и std::find 00:44:26 map.lower_bound против std::lower_bound 00:45:30 Пример: подсчёт частот чисел 00:46:50 Как устроена std::map. Бинарные деревья поиска 00:57:30 Асимптотика операций в бинарном дереве поиска 01:00:50 Сбалансированные бинарные деревья поиска 01:04:00 Пример сбалансированных деревьев: 2-3-дерево 01:05:40 __gnu_pbds::tree: порядковые статистики 01:12:12 Параметр tree_order_statistics_node_update 01:16:00 Как устроен std::set в C++ 01:21:50 Как устроен std::multiset в C++ 01:23:30 Проблема с временем работы multiset::count 01:26:18 Решение через order_of_key в __gnu_pbds::tree 01:27:48 Разбор задачи "A. Не смешите мои подковы" 01:29:20 Разбор задачи "B. Лекция" 01:33:40 Разбор задачи "C. A и B и ошибки компиляции" 01:34:40 Алгоритм std::set_difference 01:39:00 Решение задачи через std::map 01:42:30 Решение через std::multiset и std::set_difference 01:45:10 Заключение и планы на будущее
В этом занятии мы разбираем контейнеры и итераторы в C++, а также работу с ассоциативными структурами данных: std::map, std::set и std::multiset. По ходу занятия объясняем, чем отличаются методы контейнеров от общих алгоритмов STL, как связаны структуры данных с асимптотикой и почему std::map работает быстро. Отдельно рассматриваем бинарные деревья поиска, сбалансированные деревья и возможности __gnu_pbds::tree для порядковых статистик. В конце разбираем несколько задач, где все эти идеи применяются на практике. Тайм-коды: 00:00:00 Обзор списка задач 00:00:20 Введение в тему занятия 00:04:10 Что такое словарь 00:10:10 Применение словаря 00:11:30 Что такое контейнер в С++ 00:12:30 Что такое итераторы 00:15:45 Обход контейнера 00:18:10 Пример: поиск максимума в контейнере 00:21:35 Какие бывают итераторы 00:22:00 lower_bound в vector и list 00:27:35 Как работать со словарём std::map в C++ 00:40:10 Поиск в map, разница между map.find и std::find 00:44:26 map.lower_bound против std::lower_bound 00:45:30 Пример: подсчёт частот чисел 00:46:50 Как устроена std::map. Бинарные деревья поиска 00:57:30 Асимптотика операций в бинарном дереве поиска 01:00:50 Сбалансированные бинарные деревья поиска 01:04:00 Пример сбалансированных деревьев: 2-3-дерево 01:05:40 __gnu_pbds::tree: порядковые статистики 01:12:12 Параметр tree_order_statistics_node_update 01:16:00 Как устроен std::set в C++ 01:21:50 Как устроен std::multiset в C++ 01:23:30 Проблема с временем работы multiset::count 01:26:18 Решение через order_of_key в __gnu_pbds::tree 01:27:48 Разбор задачи "A. Не смешите мои подковы" 01:29:20 Разбор задачи "B. Лекция" 01:33:40 Разбор задачи "C. A и B и ошибки компиляции" 01:34:40 Алгоритм std::set_difference 01:39:00 Решение задачи через std::map 01:42:30 Решение через std::multiset и std::set_difference 01:45:10 Заключение и планы на будущее