Базовый курс C++ (MIPT, ILab). Lecture 23. Последовательные контейнеры.
Вставка
- Опубліковано 28 чер 2024
- Лекции в бакалавриате МФТИ по C++ на русском языке.
На этой лекции в основном рассматриваются последовательные контейнеры и контейнерные адапторы. Она скорее обзорная, хотя и содержит несколько более глубоких моментов. Мы узнаем что такое деки, какие бывают списки, зачем нам очереди с приоритетами и многое другое. Отдельный раздел посвящен не вполне контейнерам -- конкретным но удобным классам, в основном битовым маскам и строкам. В конце лекции мы начнём разговор про ассоциативные контейнеры.
Лектор: Константин Владимиров
Дата лекции: 28 марта 2022 года
Съёмка: Владислав Белов.
Звук: Дмитрий Рябцев.
Предыдущая лекция: • Базовый курс C++ (MIPT...
Следующая лекция: • Базовый курс C++ (MIPT...
Слайды ко всем лекциям: sourceforge.net/projects/cpp-...
Примеры кода ко всем лекциям: github.com/tilir/cpp-graduate
Timeline:
00:00 Начало
01:43 Деки
10:50 Списки
21:40 Адаптеры
25:40 Case study: алгоритм Прима
34:55 Ортогональность адаптеров
41:30 Маски
47:55 Строки
1:04:05 string_view и span
1:12:00 Отображения
1:19:00 Собственный ключ
1:26:14 Классы эквивалентности
Errata:
* Слайд #3: перепутаны местами LIFO и FIFO
Константин, исправьте, пожалуйста, на 3-м слайде FIFO - это очередь (queue), а LIFO - это стэк (stack). На слайде всё наоборот.
1:09:41 Константин, здесь происходит нечто странное. Относительно std::array, он же просто агрегат, аналогичный int[4], и никакого копирования быть не должно. Относительно std::span, он не имеет ни конструктора от std::initializer_list, ни другого подходящего, так что будет ошибка компиляции. И это логично, ведь span должен указывать на какую-то область памяти, а init list в конце умер бы.
Спасибо отличное наблюдение. Я чуть позже буду проставлять errata и сюда внесу и главное учту в курсе этого года.
Протестил код с 1:31. Фишка с сравнением почему то работает исключительно на архитектуре x86_64, на арме (Mac M1, Apple clang version 15.0.0 (clang-1500.0.40.1)) чет вообще никак. А именно строка 10. Что false, что (lhs/12) < (rhs/12) дают один и тот же упорядоченный вектор от 0 до 119
тяжело
Нужно взять алгоритм хеширования для строки(набора символов) и пихнуть туда ренж который объединяет обе строки без их реальной конкатенации, готово.
Очень интересное применение ренджей. Увы, мне кажется, что специализацию std::hash для такого ещё не придумали
@@tilir шаблонный параметр Hash не обязательно должен быть специализацией std::hash, это может быть произвольный функтор, например declttype([]{ /* do smth*/ } )
Это я понимаю. Я говорю про то, что вам не удастся переиспользовать std::hash для этого без материальной конкатенации, только средствами views.
@@tilir тогда достаточно возвращать хеш одной из строк и это будет хороший хеш, а дальше уже пусть сравниваются объекты типа S
В общем случае это создаст плохие списки коллизий. Представьте всех людей с одним именем (но разными фамилиями) в одном списке.
Здравствуйте.
Спасибо за лекцию, очень полезная.
Вопрос по поводу строк: есть ли стандартные средства для переводов строк из одной кодировки в другую?
UPD.: Не уверен, что корректно поставил вопрос, судя по тому, что я вычитал про кодировки в интернете. Вопрос скорее такой: как вообще строки в Си и С++ связаны с кодировками?
Там бездны. Я раньше читал такую лекцию но записи не делалось. Надо бы когда нибудь записать такой аддон к магистерскому.
Здравствуйте, Константин. На слайде 24 наверно имелось в виду char16_t и char32_t, а не u16char_t и u32char_t?
Да действительно. Спасибо, странная опечатка =)
А при переносе win-Linux использование auto же решит проблему с unsigned типом и все такое?
Да, это один из классических аргументов за систематическое использование auto =)
@@tilir все ещё triple AAA?
а на слайде 29 лучше применить auto, я так считаю )
(предыдущие комментарии ютуб почикал, причину не понимаю)
Да, это ещё один аргумент за AAA.
Ютуб странно себя ведёт. Например с недавних пор он удаляет мои ответы (!) сделанные с акка другого моего канала. Жесть какая-то.
Кажется на 3 слайде опечатка, FIFO и LIFO надо местами поменять
Спасибо, добавлю в errata. Опечатка была тут много лет, вы первый кто заметил =)
@@tilir такие опечатки божественны 😃
@@tilir на слайде 16 ещё опечатка adgacent :)
слайд 36 - наверное, не int, а size_t ?
Формально да. Но ясно, что любой интегральный тип подойдёт. Лишь бы значения были положительными.
Слайд 16. Должно быть ```!mst[v]``` и ```mst[elt]=true;```
Цвета не настраиваются в quick bench? По лезвию бритвы ходите. Не лишайте нас удовольствия изучать С++
Не настраиваются ))
Не знаю чего так все возбудились. Вроде безобидная шутка.
@@tilir Шутка отличная !