20. Внутреннее устройство deque, list, map

• Обсуждение устройства вектора буль, который работает по-особому, используя один бит для каждого буля.  

• Вектор буль имеет специальный подвид, который называется вектор буль.  

• В векторе буль обращение по индексу реализовано хитро, возвращая специальный тип бит-референс.  

• Бит-референс хранит ссылку на ячейку памяти, где хранится номер бита, за который мы ответственные.  

• Оператор присваивания бит-референса работает с оператором каста буль, который возвращает бит-референс.  

• Оператор присваивания возвращает бит-референс, но не ссылку на бит-референс.  

• Присвоение в векторе буль является контрпримером к утверждению, что присваивать можно только лв величинам.  

• Вектор буль возвращает не ссылку, а значение, что считается рв.  

• Обсуждение векторов и деков, их особенностей и различий.  

• Вектор имеет квадратные скобки, гарантированную завод единицу, пуш бэк и поп бэк, а также редном аксетератора.  

• Дек имеет квадратные скобки, гарантированную завод единицу, пуш бэк и поп фронт, а также редном аксетератора.  

• Дек устроен сложнее, чем вектор, и имеет массив указателей на другие массивы.  

• При расширении дека, внешний массив расширяется, а указатели на старые массивы провинциализируются.  

• Дек не требует перекладывания объектов, в отличие от вектора.  

• Указатели и ссылки на элементы деков не инвалидируются после модификации контейнера.  

• Дек - это контейнер, который хранит элементы в порядке, обратном к обычному.  

• В случае с деком, вы можете пользоваться указателями и ссылками на элементы после того, как поменяли дек.  

• Итераторы на элементы дека после изменения не могут быть использованы.  

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

• Дек не поддерживает операцию "резерв", так как непонятно, что означает "резерв тысяча".  

• Дек сложнее устроен, чем вектор, так как обращение по индексу требует разменования двух указателей.  

• Дек безопаснее вектора относительно разменований, так как не перекладывает элементы.  

• Дек может использоваться с типами, которые не позволяют себя копировать или перемещать.  

• Итераторы, указатели и ссылки на элементы дека остаются валидными после изменения.  

• В связанном списке должны быть реализованы операции вставки и удаления элементов в произвольное место.  

• Итераторы должны быть двунаправленными и поддерживать операции инкремента и декремента.  

• Внутри связанного списка хранятся указатели на вершины, которые провязаны указателями на следующую и предыдущую вершины.  

• Для хранения значений используется структура "ноут", которая содержит значение и два указателя.  

• Для реализации итераторов используется зацикленный список с фиктивной вершиной, которая указывает на себя.  

• В связанном списке есть операции доступа к первому и последнему элементу, итераторы, инсерт, и рейс для вставки и удаления элементов.  

• Операция сорт в связанном списке реализована отдельно, так как она полагается на реператор и требует обращения по индексу.  

• В видео обсуждается, как сортировать листы с помощью мерч-сорта, который требует лишь формы итераторов.  

• Обсуждаются функции сплайс, ремуф, реверс и юник, которые позволяют удалять, переворачивать и удалять последовательные элементы из листа.  

• Упоминается, что у форвард-листа нет метода сайз, но сплайс работает за константу.  

• Обсуждаются требования к контейнерам, которые позволяют добавлять, удалять и находить элементы за гарантированный логарифм, а также предоставляют дирекшн итераторы.  

• Обсуждается, что внутри мэп - это сбалансированное двоичное дерево поиска, обычно красное-черное дерево.  

• Обсуждаются различия между сет и мэп, где сет хранит только ключи, а мэп хранит пары ключ-значение.  

• В видео обсуждается структура данных Map, которая хранит пары ключ-значение.  

• Обсуждается, что Map также содержит ноды, как и лист, но в нодах хранятся ключи, значения, указатели на левого и правого сына, указатель на родителя и флажок красной вершины.  

• Итераторы в Map хранят указатель на базовую ноду и инкремент итератора может занимать логарифм операций.  

• В среднем, инкремент итератора занимает единицы операций, так как обход всего Map слева направо занимает не логарифм, а линейное время.  

• При разыменовании итератора, возвращается пара, содержащая ключ и значение.  

• Пара - это структура, состоящая из двух полей: ферст и секонд.  

• В контейнерах, таких как вектор и лист, хранятся внутренние типы данных, которые могут быть изменены.  

• В случае с вектором, это тип "буль", а в случае с листом - "тай".  

• В случае с мэпом, хранятся пары, состоящие из константного ключа и значения.  

• Это важно, так как изменение ключа может нарушить структуру дерева поиска.  

• Вопрос о возможности удаления элементов из мэпа сводится к возможности вызова деструктора для константного типа.  

• Если бы это было невозможно, то как бы константные типы уничтожались в принципе?  

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