В то время, когда я учился, нам в рамках ни одной из дисциплин структур данных (и соответственно STL) никто не давал. Во время становления курса Андрей Логвиненко вписал в программу одну лабораторную по ассоциативным контейнерам STL, но до неё практически никто не доживал.
У меня в то время уже набрался отдельный приличный опыт кодирования различных структур данных (от простого стека до сложных B-tree деревьев различных разновидностей, как динамические так и статически реализации), поэтому структуры данных были оформлены как отдельная тема. Она оказалась хорошей подготовкой к теме STL, так как структуры данных сами по себе абстрактны и не зависят от языка реализации, а STL в значительной степени реализует большое число структур данных.
Сначала мы пробовали делать работы по реализации отдельных структур данных, однако только единицы с этим справлялись. Поэтому общий материал и произвольные структуры данных были вынесены полностью в теорию, а изучение STL делалось сразу же после разбора общей информации по структурам данных. В работах соответственно уже студенты использовали готовые контейнеры STL.
Удержание фокуса
Каждая структура данных — это объект какого-то общего класса, который описывает данный тип структур данных. Интерфейс полностью инкапсулирует внутреннее состояние структуры.
Конкретная структура данных используется и проектируется под конкретные типы действий над данными. То есть, исходя из того набора операций и требований, которые мы предъявляем множеству однотипных элементов, выбирается тип структуры данных.
Сам тип структуры данных может быть спроектирован самостоятельно в случае необходимости. Готовые протестированные структуры данных хорошо, свои велосипеды — в случае необходимости.
Подробности
Структуры данных и STL слайды.
Общие понятия любой структуры данных — множество однотипных элементов, интерфейс доступа, пользователь структуры данных. Пока что не понятно, но будем возвращаться и надеемся что прояснится.
Одну структуру данных мы уже знаем — массив. У нас в массиве всегда хранятся элементы одного типа, доступ в С++ через оператор [] по индексу, внешний пользователь использует массив не думая о том, как и где он хранится. Хотя пользователь может рассчитывать, что элементы в массиве хранятся последовательно и доступ к ним по индексу очень быстр (например в Perl массивы хранятся не последовательно, а организованы через хэш). Элементы могут быть любого, но одного типа. Взаимодействие с ними жестко определено интерфейсом. Внешний пользователь может создавать столько массивов, сколько ему захочется, и практически для любых типов (тип должен иметь фиксированный размер или гарантию того, что по размеру не выйдет за установленный предел).
Теперь переходим к другим, незнакомым структурам данных. У каждой из них мы будем рассматривать интерфейс взаимодействия и способ хранения, а также что из всего этого следует.
Стек. Имеет операции вставки и извлечения, параметры глубины и максимального размера. Обычно в памяти структура данных сама хранит указатель HEAD, чаще всего указывающий на элемент, который должен быть вставлен в последствии. Описание операций вставки и извлечения. LIFO. Две разных реализации стека — статическая и динамическая. В первом случае через массив, который мы создаем заблаговременно и работаем по нему посредством указателей. Второй случай — каждый элемент структуры данных хранит рядом с собой указатели на соседние элементы. Певый случай быстр, не требует дополнительной памяти на указатели, но съедает заданное число памяти согласно первой инициализации и имеет ограничение на размер, в то время как динамическая реализация ограничена только всей оперативной памятью.
Примеры стеков — ханойская башня (3 стека). Стек может быть использован в ряде других, не так очевидных задач, — организация сохранения данных в памяти при работе подпрограмм; пример рекурсивного разбора выражений.
Очередь. Аналогично — есть HEAD и TAIL, можно вставлять в один хвост, а извлекать только из другого. FIFO. Аналогично реализуется статически и динамически.
Списки. Как двусторонние стеки или двусторонние очереди. С каждым из хвостов можно делать операции извлечения и вставки.
Двусторонне-связанные списки. Картинка динамической реализации. Аналогично односторонне-связанные. Преимущества и недостатки.
Упорядоченные списки — делают определенные действия, чтобы сохранять упорядоченность на каждом выполнении операции.
Кольцевые списки.
Как организуется структура данных — основные правила.
Мы рассматривали линейные структуры данных. Для каждой из них характерно то, что все элементы хранятся линейно, в жестко заданной последовательности. Такое деление частично условно, так как в большинстве структур данных задается условие, что можно перебрать все элементы структуры данных в прямом или обратном порядке.
Дерево как структура данных. Каждый элемент имеет родителя и потомков. В общем случае дерево начинается с корня, каждый элемент можно отнести к какому-то уровню, связи внутри дерева не пересекаются.
Бинарное дерево — количество потомков не более 2. Это имеет свои преимущества. Например в данном случае дерево отсортировано и можно простыми операциями сравнения найти нужный элемент, ища из корня.
Сбалансированное дерево — такое дерево, в котором все кроме одного последнего уровня обязательно заполнены. Такое дерево позволяет осуществить гарантированный поиск за log2(N) операций.
Реализация деревьев также может быть статической и динамической. В первом случае отношения между элементами описываются с помощью математических формул, а во втором случае посредством указателей.
Виды проходов деревьев (pre-order, in-order, post-order, level-order).
Множества. Могут быть реализованы по-разному, как статически, так и динамически, так и через другие структуры данных. В множестве элемент встречается только один раз или не встречается вообще, а операции для него определяются из математического определения множества.
Мультимножество.
Карта (отображение, map). Мультикарта (multimap).
Хэш. Сначала разбор понятия хэш функции (функция, возвращающая элемент, который имеет конечное число состояний). Данное число состояний в хэше ассоциируется с хэш-таблицей.
Изначально хэш-таблица пуста. Во время вставки элемента вычисляется значение хэш-функции, элемент сохраняется и помечается его присутствие в хэш таблице. При последующей операции поиска вместо того, чтобы искать по всей структуре данных идет вычисление хэша. Если элемент таблицы отсутствует, то значения в хэше нет. Если присутствует, то нам нужно проверить все элементы у которых такой хэш уже напрямую.
Понятий коллизий. Коллизии это плохо. как избежать коллизий (хорошая хэш-функция и изменение размеров хэш-таблицы).
Куча (heap). Выглядит как бинарное дерево, но в нем всегда в каждой тройке нижние элементы меньше верхнего, и справа всегда меньше чем слева. Такая организация позволяет нам создать приоритетную очередь, в которой скорость вставки и извлечения высока (log N), в обычных приоритетных очередях каждый раз нужно либо искать место вставки или пересортировать. Разбор операций вставки и извлечения и почему так происходит.
Пример экзотической структуры данных — sparse array и варианта его реализации.
STL. Сначала — пример задачи, где нужно выполнять однотипные действия над разными типами данных. Если нет специального механизма, то это приводит к тому, что имеем большое число повторяющегося кода. Его сложнее читать, сложнее сопровождать, сложнее использовать. В случае с использования шаблонов можно сделать по-другому, из-за чего сокращается объем и сложность, и кроме того, появляется гибкость, так как мы можем использовать этот код для ряда других типов, о которых в данный момент ещё даже не подозреваем.
STL. Базовые (но это не все) элементы — контейнеры, итераторы, алгоритмы.
Контейнеры — это фактически те структуры данных, которые мы рассматривали ранее, но на языке С++, и они уже готовы к применению. Итераторы — специальные объекты для доступа к элементам структуры данных, близкая аналогия — указатели. Алгоритмы — готовый набор функциональных действий, позволяющий получить что-то полезное.
Каждый контейнер представляет собой упорядоченную последовательность элементов. Т.е. все элементы можно выстроить в одну цепочку друг за другом. Если мы хотим перебрать все элементы контейнера (распечатать их, найти какой-то и др.), что является типичной операцией, то это делается через итерационный перебор. Пример перебора. Понятие end-of-sequence (элемент за последним, но не последний).
Vector. Это — массив, но только в отличие от него мы можем изменять его размер во время выполнения программы. Сам вектор имеет всегда какой-то запас по размеру в памяти, и поэтому мы можем его расширять быстро.
Если этот запас заканчивается, то вектор перемещает себя в другой участок памяти, где резервирует больший объем памяти, копирует себя туда, и работа продолжается.
Пример использования с разбором подключения, инициализации, типовых операций, передачи как параметра.
List. В STL — динамический двусвязный список со всеми вытекающими. Удаление и добавление элементов в список. Пример.
Образование контейнеров из list'a в STL: стек, очередь и приоритетная очередь сделаны на основании list'a.
Deque.
Множества и мультимножества как деревья в STL.
Карты и мультикарты в STL. Пример.
Разбор характеристик контейнеров — какие особенности у каждого из них, когда какой следует применять.
Типичные методы контейнеров, характерные для всех.
Разбор алгоритмов STL. Алгоритмов много. Они безопасны, проверены и быстры. Работают как с контейнерами, так и с массивами. Нужно знать.
